Szczegółowe omówienie zadania Mapa gęstości:

Link do powyższego omówienia zadania Mapa gęstości:
https://youtu.be/-aUZwinXSqQ?t=1653

Link do treści zadania Mapa gęstości:
https://szkopul.edu.pl/problemset/problem/0QusZwo2JAyvhPj1JIKRc8H7/site/

–
Zadanie Mapa gęstości jest szkoleniowym zadaniem pokazującym użycie sum prefiksowych w algorytmice:
https://youtu.be/-aUZwinXSqQ?t=2332

Sumy prefiksowe pozwalają błyskawicznie obliczyć pole dowolnego prostokąta:
https://youtu.be/-aUZwinXSqQ?t=3503

Zastosowania sum prefiksowych:
https://youtu.be/-aUZwinXSqQ?t=19
Jak rozmazujemy obraz?
https://youtu.be/-aUZwinXSqQ?t=4545

–
Zadanie Mapa gęstości pochodzi z I etapu VIII Olimpiady Informatycznej.
Link do wszystkich zadań Olimpiady Informatycznej:
https://szkopul.edu.pl/task_archive/oi/

Zadanie omawia Tomek Kwiatkowski:
https://youtu.be/YWhVqyMjtjE?t=115

——–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625

–
Kod C++ programu Mapa gęstości, który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 250 + 7; // maksymalne wymiary talibcy

int tab[MAXN][MAXN]; // tablica z wejscia
int pref[MAXN][MAXN]; // sumy prefiksowe, pref[i][j] = suma na prostokacie od (1, 1) do (i, j)

// poniewaz tablice sa zadeklarowane globalnie (a nie w main), sa one wypelnione zerami!

int suma(int i1, int j1, int i2, int j2) // suma na prost. lewy gorny - (i1, j1), prawy dolny - (i2, j2)
{
	return pref[i2][j2] - pref[i1 - 1][j2] - pref[i2][j1 - 1] + pref[i1 - 1][j1 - 1];
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int n, r;
	cin >> n >> r; // odpowiednio: rozmiar tablicy i promien
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			cin >> tab[i][j];
			// wczytujemy zaczynajac od i = 1, j = 1
		}
	}

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + tab[i][j];
			// poniewaz wczytywalismy od indeksu 1 (a nie 0), nie musimy sie martwic o to,
			// ze wyjdziemy poza tablice - na indeksie 0 sa zera
		}
	}

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			cout << suma(max(1, i - r), max(1, j - r), min(n, i + r), min(n, j + r)) << ' ';
			// max i min sa po to, aby nie wychodzic poza tablice
		}
		cout << '\n';
	}
	return 0;
}