Welcome to ZOJ
56 - ZOJ Monthly, October 2006 - 1002
Rotate and Connect

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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:

Figure 2

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.


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.


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


Author: JIAN, Hengyi

Submit    Status