[UVA] 556 - Amazing
556 - Amazing
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;
}