题意简述
一个机器人从指定位置进入一个每格都指向一个确定方向的矩阵。它会顺着格子给定的方向运动。
若机器人能走出矩阵，则输出其经过的格子数量。
若机器人会陷入一个环，则输出经过多少格后，机器人进入了一个格数为多少的环。
算法分析
与POJ-2632类似。直接模拟。
建立一个等大的累加矩阵，存储机器人经过的次数。当机器人碰墙时则认为机器人走出矩阵。计算此时累加矩阵内1的个数。即为经过格子数量。
当机器人到达的点的累加值已经达到2，则说明机器人已经过一个环两次。此时计算累加矩阵内1的个数，即进入环前经过的格子数；计算矩阵内2的个数，即环所占格子数。
Problem Status: AC。时间0ms，内存120k
——————————————————————分割线——————————————————————
优化：
没想到。POJ排名第一仍然是0ms 4k的恐怖数据……
程序样例
#include<stdio.h>
void out(int map[][20], int n, int r, int c) {
int i, j, ans1 = 0, ans2 = 0;
for (i = 0; i < r; i++)
for (j = 0; j < c; j++) {
if (map[i][j] == 1) ans1++;
if (map[i][j] == 2) ans2++;
}
if (n == 1)
printf("%d step(s) to exit\n", ans1);
if (n == 2)
printf("%d step(s) before a loop of %d step(s)\n", ans1, ans2);
}
int main() {
int r, c, i, j, pos[2], b[20][20], flag;
char map[20][20], tem[20];
while (scanf("%d%d%d", & r, & c, & pos[1]), !(r == 0 && c == 0 && pos[1] == 0)) {
pos[0] = 0;
pos[1]--;
for (i = 0; i < r; i++) {
scanf("%s", tem);
for (j = 0; j < c; j++) {
b[i][j] = 0;
map[i][j] = tem[j];
}
}
flag = 1;
while (flag) {
b[pos[0]][pos[1]]++;
switch (map[pos[0]][pos[1]]) {
case 'N':
pos[0]--;
break;
case 'W':
pos[1]--;
break;
case 'S':
pos[0]++;
break;
case 'E':
pos[1]++;
break;
}
if (pos[0] >= 0 && pos[0] < r && pos[1] >= 0 && pos[1] < c) {
if (b[pos[0]][pos[1]] == 2) {
out(b, 2, r, c);
flag = 0;
}
} else {
out(b, 1, r, c);
flag = 0;
}
}
}
}