Elicop

elicop

== include(page="template/taskheader" task_id="elicop") ==

p<>. Considerăm o matrice cu $L$ linii (numerotate de sus în jos de la $1$ la $L$) şi $C$ coloane (numerotate de la stânga la dreapta de la $1$ la $C$) care memorează doar valori $0$ şi $1$. Mai mult, valorile egale cu $1$ sunt grupate în mai multe dreptunghiuri pline, care nu se învecinează nici pe linii, nici pe coloane, nici pe diagonale. În exemplul din $fig. 1$ matricea este corectă deoarece cele $4$ dreptunghiuri de $1$ nu se învecinează. În schimb în $fig. 2$ există $2$ dreptunghiuri de $1$ învecinate pe coloană şi două învecinate pe diagonală, deci matricea este incorectă.
 
!problema/acces?p1.jpg!
 
p<>. În această matrice se pot face deplasări doar pe direcţiile Vest şi Nord în elemente egale cu $0$, deci din poziţia $(i, j)$ se poate ajunge doar într-una dintre poziţiile $(i, j-1)$ şi $(i-1, j)$, marcate cu $0$. În acest fel, pornind de la o anumită poziţie, prin deplasări succesive, pot fi accesate un anumit număr de elemente ale matricei egale cu $0$. De exemplu, în $fig. 1$, din poziţia $(2, 4)$ pot fi accesate $5$ componente egale cu $0$, iar din poziţia $(5, 4)$ pot fi accesate $14$ componente egale cu $0$.
 Trebuie să răspundeţi la $Q$ întrebări, fiecare întrebare fiind de forma: “Câte din elementele egale cu zero ale matricei pot fi accesate din poziţia $(i, j)$?”
 
h2. Cerinţă
 
Scrieţi un program care să determine, pentru fiecare întrebare, câte elemente egale cu $0$ din matrice pot fi accesate din poziţia precizată în cadrul întrebării.

Poveste şi cerinţă...

h2. Date de intrare

p<>. Pe prima linie a fişierului $acces.in$ se află două numere naturale $L$ şi $C$ separate printr-un spaţiu, reprezentând numărul liniilor, respectiv numărul coloanelor matricei. Pe următoarele $L$ linii se găsesc câte $C$ cifre binare, separate prin câte un spaţiu, reprezentând elementele matricei. Pe linia următoare se află numărul natural $Q$, reprezentând numărul întrebărilor. Pe următoarele $Q$ linii se găsesc câte două numere naturale $i$ şi $j$, separate prin câte un spaţiu, reprezentând poziţia corespunzătoare unei întrebări.

Fişierul de intrare $elicop.in$ ...

h2. Date de ieşire

Fişierul $acces.out$ conţine $Q$ linii. Pe linia $p (1 ≤ p ≤ Q)$ se află un număr natural $k$~$p$~ reprezentând răspunsul la cea de-a $p$-a întrebare.

În fişierul de ieşire $elicop.out$ ...

h2. Restricţii

* $4 ≤ L, C ≤ 1 000$
* $3 ≤ Q ≤ 500 000$
* Pentru orice întrebare $i j$ se garantează că valoarea corespunzătoare din matrice este $0$
* Pentru toate testele, dreptunghiurile formate din valori de 1 nu se învecinează

* $... ≤ ... ≤ ...$

h2. Exemplu

table(example). |_. acces.in |_. acces.out |_. Explicaţie |
| 5 7
0 0 0 0 1 1 1
0 1 1 0 1 1 1
0 1 1 0 0 0 0
0 1 1 0 1 0 0
0 0 0 0 1 0 1
4
2 4
5 4
4 7
3 1
| 5
14
11
3
|Pentru prima întrebare, cele 5 componente egale cu 0 care pot fi accesate sunt cele din
poziţiile $(1, 1), (1, 2), (1, 3), (1, 4), (2, 4).$
|

table(example). |_. elicop.in |_. elicop.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="elicop") ==