ZOJ Problem Set - 3755
As a small-game fan, Flandre loves playing the Mine-sweeping very much. He spends 23 hours playing the lowest level of Mine-sweeping every day. One day, when Flandre is playing Mine-sweeping, a strange idea comes to him: "Can I just calculate the minimum number of the mine in current state of the game ?"
To simplify this problem, we suppose the map is a N*(M*2+1) matrix and there are some mines in the grids of odd columns. You have got all the messages about the even columns which are represented as a N * M number matrix. For example: N = 3, M = 2(# represent the mines, number means how many mines around it) # 2 1 2 # 2 4 # 3 0 # 3 # 2 0 the messages about the even columns are: 2 2 4 3 3 2 Your task is to calculate the minimum number of mines with the messages matrix.
There are multiple test cases. For each test case: The first line contains two integers N(1≤ N≤ 10), M(1≤ M≤ 10) Then followed by N lines, each line contain M integers represent the messages matrix. Process to the end of input.
For each the case, print the minimum number of mines.
3 2 2 2 4 3 3 2
Author: LUO, Jiewei
Source: ZOJ Monthly, January 2014