The Revolutionary War
All submissions for this problem are available.Mr. Hitler is in the Revolutionary war. He is the only hope to save the country from enemies as they have a new biological weapon which is so deadly that when it hits a particular area, it also wipes out the areas adjacent to it.Although if the weapon hits the water bodies, then it wont have any effect.
Given an NxM map which has NxM cells. Each cell may represent an area or a water body.
The weapon cannot penetrate a water body or the edges of the map.
You will be given a initial state of the country represented by an N x M grid consists of 0 or 1 representing water body and area respectively. Also there will be Q attacks of the biological weapon. After each query, you are to tell the number of areas still intact.Once an area is hit, the effect is directed to all the areas until it is stopped by a water body
First line of input contains 3 space separated integers N,M,Q where N x M is the size of the country. Q is the number of attacks.
N lines follow each with M values of either 0 or 1, denoting whether that particular coordinate is a area(1) or water body(0).
Q lines follow. Each line has a coordinate X,Y where the next attack takes place.
For each Q, output the number of areas still existing on a single line.
Two areas are said to be adjacent if they share an edge. Enemy can shoot the weapon at any place on the country within its domain any number of times.
Once an area is destroyed, it will continue to remain destroyed over all the forthcoming queries.
Large IO. Prefer scanf/printf(in C/C++).
1 ≤ N,M ≤ 103
1 ≤ X ≤ N
1 ≤ Y ≤ M
1 ≤ Q ≤ 106
3 3 3
0 0 0
1 0 1
0 1 1
Query 1: (1,2) No area is hit. Intact areas=4 (initial)
Query 2: (2,2) No area is hit. Still intact=4
Query 3: (3,3) is hit and it also spreads to (2,3) and (3,2) also. Thus only 1 area is left (1,2).
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions