#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; }
Hello, I am a CS student from Taiwan.
I am learing English and Programming.
I'll save source code of some problems or small programs without comments in this blog.
I would recommend you not to read solution from others before you solved the problem.
(這邊專門存放沒有任何註解的小程式/OJ題目程式碼)
2013年8月24日
UVa 10047 - The Monocycle
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言