题意简述

一个机器人从指定位置进入一个每格都指向一个确定方向的矩阵。它会顺着格子给定的方向运动。

若机器人能走出矩阵，则输出其经过的格子数量。

若机器人会陷入一个环，则输出经过多少格后，机器人进入了一个格数为多少的环。

算法分析

与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;
      }
    }
  }
}