
56  ZOJ Monthly, October 2006  1002
Bill is playing a game with a board of n*m grids. There are 7 types of grids, which are marked from 0 to 6, as Figure 1 shows. There are exactly 2 grids of "O" on the board, which won't be next to each other. Then a board of 4*4 grids is showed below: Bill wants to rotate the least number of grids so that the two "O" grids can be connected. But he finds it hard to do so. Therefore, he asks you to write a program for helping him. Note: In the example above, rotate the two red grids can make the two "O" grids connected. Input There are several test cases. In each test case, the first line contains 2 integers N and M (2 <= N, M <= 10), then N lines follow. In each of these lines, there are M integers, in the range of 0 to 6, denoting the type of the corresponding grid. And there is a blank line after each test case. N = M = 0 denotes the end of input. Output For each test case, output one line with the least number of grids that should be rotated to connect the "O" grids, or output 1 if they cannot be connected. Sample Input 4 4 1 0 6 3 5 1 5 6 6 3 0 2 3 4 3 6 0 0 Sample Output 2 Author: JIAN, Hengyi 