556 - Amazing

Amazing

One of the apparently intelligent tricks that enthousiastic psychologists persuade mice to perform is solving a maze. There is still some controversy as to the exact strategies employed by the mice when engaged in such a task, but it has been claimed that the animal keepers eavesdropping on conversations between the mice have heard them say things like "I have finally got Dr. Schmidt trained. Everytime I get through the maze he gives me food".

Thus when autonomous robots were first being built, it was decided that solving such mazes would be a good test of the 'intelligence' built into such machines by their designers. However, to their chagrin, the first contest was won by a robot that placed a sensor on the right-hand wall of the maze and sped through the maze maintaining contact with the right-hand wall at all times. This led to a change in the design of mazes, and also to the interest in the behaviour of such robots. To test this behaviour the mazes were modified to become closed boxes with internal walls. The robot was placed in the south west corner and set of pointing east. The robot then moved through the maze, keeping a wall on its right at all times. If it can not proceed, it will turn left until it can proceed. All turns are exact right angles. The robot stops when it returns to the starting square. The mazes were always set up so that the robot could move to at least one other square before returning. The researchers then determined how many squares were not visited and how many were visited one, twice, thrice and four times. A square is visited if a robot moves into and out of it. Thus for the following maze, the values (in order) are: 2, 3, 5, 1, 0.

Write a program to simulate the behaviour of such a robot and collect the desired values.

Input 

Input will consist of a series of maze descriptions. Each maze description will start with a line containing the size of the maze (b and w), This will be followed by b lines, each consisting of w characters, either '0' or '1'. Ones represent closed squares, zeroes represent open squares. Since the maze is enclosed, the outer wall is not specified. The file will be terminated by a line containing two zeroes.

Output 

Output will consist of a series of lines, one for each maze. Each line will consist of 5 integer values representing the desired values, each value right justified in a field of width 3.

Sample Input 

3 5
01010
01010
00000
0 0

Sample Output 

  2  3  5  1  0

---

Miguel A. Revilla
1998-03-10

模擬右手定則走迷宮, 在回到原先出發點後停止。
問每格的走訪次數。

右手定則簡單的說就是逆時針走訪

#include <stdio.h>
char g[105][105];
int main() {
    int n, m;
    int i, j;
    while(scanf("%d %d", &n, &m) == 2 && n) {
        for(i = 0; i < n; i++)
            scanf("%s", g[i]);
        int used[105][105] = {}, cnt[105][105] = {};
        int x, y, tx, ty, d;
        int dx[] = {-1,0,1,0};
        int dy[] = {0,-1,0,1};
        x = n-1, y = 0, d = 3;
        used[x][y] = 0;
        while(true) {
            for(i = d-1+4, j = 0; j < 4; j++, i++) {
                i %= 4;
                tx = x+dx[i];
                ty = y+dy[i];
                if(tx < 0 || ty < 0 || tx >= n || ty >= m)
                    continue;
                if(g[tx][ty] == '1')
                    continue;
                x = tx, y = ty;
                d = i;
                break;
            }
            cnt[x][y]++;
            if(x == n-1 && y == 0)    break;
        }
        int ret[5] = {};
        for(i = 0; i < n; i++) {
            for(j = 0; j < m; j++) {
                if(g[i][j] == '0')
                    ret[cnt[i][j]]++;
            }
        }
        for(i = 0; i < 5; i++)
            printf("%3d", ret[i]);
        puts("");
    }
    return 0;
}