AOJ2640 Prowler
問題ページ
Prowler | Aizu Online Judge
解法
右手法をする。右に進めれば右、前に進めれば前、左に進めれば左、全て無理ならUターンして後ろに進むをゴールにたどり着くまで繰り返す。ループ回数が大きくなりすぎているときはたどり着けないので-1を出力する。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) // 下、右、上、左 int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int h, w; cin >> h >> w; h += 2, w += 2; // 番兵として周りを壁で囲む vector<string> s(h); s[0] = s[h-1] = string(w, '#'); FOR(i, 1, h-1) { cin >> s[i]; s[i] = "#" + s[i] + "#"; } int sx=-1, sy=-1, sdir=-1, gx=-1, gy=-1; REP(i, h) REP(j, w) { if(s[i][j] == 'v') { sdir = 0, sx = j, sy = i; } else if(s[i][j] == '>') { sdir = 1, sx = j, sy = i; } else if(s[i][j] == '^') { sdir = 2, sx = j, sy = i; } else if(s[i][j] == '<') { sdir = 3, sx = j, sy = i; } else if(s[i][j] == 'G') { gx = j, gy = i; } } VVI used(h, VI(w, 0)); int x = sx, y = sy, dir = sdir, cnt = 0; while(x!=gx||y!=gy) { used[y][x] = 1; // 右、前、左に壁があるか int tmpx = x + dx[(dir+3)%4], tmpy = y + dy[(dir+3)%4]; bool right = s[tmpy][tmpx]=='#'; tmpx = x + dx[dir], tmpy = y + dy[dir]; bool front = s[tmpy][tmpx]=='#'; tmpx = x + dx[(dir+1)%4], tmpy = y + dy[(dir+1)%4]; bool left = s[tmpy][tmpx]=='#'; // 進む方向を決定 if(!right) { dir = (dir+3)%4, x += dx[dir], y += dy[dir]; } else if(!front) { x += dx[dir], y += dy[dir]; } else if(!left) { dir = (dir+1)%4, x += dx[dir], y += dy[dir]; } else { dir = (dir+2)%4, x += dx[dir], y += dy[dir]; } cnt++; if(cnt > 20000) { cout << -1 << endl; return 0; } } int ans = 1; REP(i, h) REP(j, w) ans += used[i][j]; cout << ans << endl; return 0; }