UVa 10047 - The Monocycle

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct State {
  int r, c, dir, color;
};

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

int main() {
  int R, C, Case = 1;
  bool first = true;
  while (scanf("%d%d", &R, &C) && R) {
    if (!first) {
      puts("");
    }
    printf("Case #%d\n", Case++);
    first = false;
    char map[99][99];
    int sr, sc, tr, tc;
    for (int r = 0; r < R; r++) {
      scanf("%s", map[r]);
      for (int c = 0; map[r][c]; c++) {
        if (map[r][c] == 'S') {
          sr = r;
          sc = c;
        } else if (map[r][c] == 'T') {
          tr = r;
          tc = c;
        }
      }
    }
    int dis[25][25][4][5] = {};
    dis[sr][sc][0][0] = 1;
    queue<State> q;
    q.push((State){sr, sc, 0, 0});
    bool found = false;
    while (!q.empty()) {
      int r = q.front().r, c = q.front().c;
      int dir = q.front().dir, color = q.front().color;
      q.pop();
      int len = dis[r][c][dir][color];
      if (!color && r == tr && c == tc) {
        found = true;
        printf("minimum time = %d sec\n", len - 1);
        break;
      }
      for (int i = 1; i <= 3; i += 2) {
        int nd = (dir + i) % 4;
        if (!dis[r][c][nd][color]) {
          dis[r][c][nd][color] = len + 1;
          q.push((State){r, c, nd, color});
        }
      }
      r += dr[dir];
      c += dc[dir];
      color = (color + 1) % 5;
      if (r >= 0 && r < R && c >= 0 && c < C && map[r][c] != '#' && !dis[r][c][dir][color]) {
        dis[r][c][dir][color] = len + 1;
        q.push((State){r, c, dir, color});
      }
    }
    if (!found) {
      puts("destination not reachable");
    }
  }
  return 0;
}