ZOJ Problem Set - 2922
A building has N*M rooms ( N rows and M columns 1<=N,M<=1000 ) . And there are bombs in some of these rooms. Each bomb has a power K which means when the bomb explodes, the K (K<1000) rooms on its left will all be destroyed, and the bombs in these rooms will explode automatically. The bomb has a special property, when a bomb exploded, the rooms above it will be destroyed and the bombs in these rooms will also explode automatically.
A E I Q B F J R C G L S D H P T
When the bomb in room L explodes, and the power of that bomb is 1.Then the bombs in G and J and I will explode.
Now you task is to count at least how many bombs should be exploded by bomb expert so that all the bombs will explode.
There are multiple test cases. There are two integers N and M on the first line of each case. In the next N lines followed, each line has M non-negative integers: K1 K2 ... KM, in which Ki is the power of the ith bomb. Ki=0 means there is no bomb in that room.
Process to the end of file.
For each case, output the answer in a line, at least how many bombs should be exploded by bomb expert.
Author: CHEN, Ximing
Source: ZOJ Monthly, February 2008