
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. For example: 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. Input 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 nonnegative 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. Output For each case, output the answer in a line, at least how many bombs should be exploded by bomb expert. Sample Input
Sample Output
Author: CHEN, Ximing Source: ZOJ Monthly, February 2008 