Rezolvare PBinfo #3681

Se consideră un tablou bidimensional format din N linii și N coloane, care conține celule libere codificate cu valoarea 0 și celule blocate, codificate cu valoarea 1. M jucători sunt poziționați în celule diferite ale matricei. Un jucător poate fi poziționat într-o celulă liberă sau într-o celulă blocată. Începând cu momentul t0 = 0, la fiecare moment întreg de timp t, fiecare jucător colorează celulele libere aflate la distanța t de poziția în care se află.

Definim distanța dintre două celule (i1, j1) și (i2, j2) ca fiind egală cu max(|i1 - i2|, |j1 - j2|), unde i1 și i2 corespund indicilor liniilor pe care se află cele două celule, iar j1 și j2 corespund coloanelor.

Cerința

Scrieți un program care citește un număr natural N, valorile matricei și pozițiile inițiale ale jucătorilor și afișează la ieșire răspunsul la Q întrebări de forma: “Care este primul moment de timp după care avem cel puțin P celule colorate în matrice?”. În cazul în care pentru o întrebare nu se vor putea colora P celule libere (după oricât de mult timp), se va afișa ca răspuns pentru acea întrebare valoarea -1.

Date de intrare

Prima linie conține numărul N, iar fiecare din următoarele N linii, câte N numere separate prin câte un spațiu, corespunzând tipului celulelor de pe linia corespunzătoare din matrice.

Linia N + 2 conține numărul de jucători M, iar fiecare din următoarele M linii câte două numere naturale, separate prin spațiu, reprezentând numărul liniei, respectiv, numărul coloanei în care se află fiecare din cei M jucători.

Linia M + N + 3 conține numărul natural Q, reprezentând numărul de întrebări, iar ultima linie conține Q numere naturale separate prin câte un spațiu, reprezentând valorile lui P, pentru fiecare dintre cele Q interogări.

Întrucât volumul datelor de intrare este foarte mare, vă recomandăm, în cazul în care folosiți pentru citire biblioteca iostream din standardul C++, să adăaugați la începutul funcției main următoarele instrucțiuni:

std :: ios_base :: sync_with_stdio(false);
std :: cin.tie(0);

Date de ieșire

Ieșirea constă într-o singură linie, care va conține Q numere, separate prin câte un spațiu, corespunzătoare răspunsurilor la întrebările date, în ordinea în care au fost citite.

Restricții și precizări

• 3 ≤ N ≤ 1500
• \( 1 ≤ M, Q ≤ {N}^{2} \)
• \( 1 ≤ P ≤ {10}^{9} \)
• liniile și coloanele sunt indexate începând cu 1.

Subtask 1(12 puncte)

• 3 ≤ N ≤ 20

Subtask 2(33 de puncte)

• 1 ≤ M ≤ 10

Subtask 3(21 de puncte)

• 3 ≤ N ≤ 600

Subtask 4(34 de puncte)

• fără restricții suplimentare.

Exemplu:

Intrare

8
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
2
3 3
6 6
3
35 16 1000

Ieșire

2 1 -1

Explicație

După momentul de timp t = 0, se va colora doar celula (3, 3). (Total: 1)

După momentul de timp t = 1, se vor mai colora în plus celulele (2, 2), (2, 3), (2, 4), (3, 2), (3, 4), (4, 2), (4, 3), (4, 4), (5, 6), (5, 7), (6, 5), (6, 7), (7, 5), (7, 6), (7, 7). (Total: 16)

După momentul de timp t = 2, vom avea în total colorate 40 de celule.

Pentru prima interogare, primul moment de timp după care avem cel puțin 35 de celule colorate este 2.

Analog, pentru a doua interogare, răspunsul este 1.

Nu se vor putea colora niciodată 1000 de celule, răspunsul fiind -1.