ferinの競プロ帳

競プロについてのメモ

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