ARC005 C - 器物損壊！高橋君

問題ページ
C - 器物損壊！高橋君

考えたこと

• N回見た拡張dijkstra
• d[y][x][何回壊したか] = (最短距離) でdijkstraをする

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define IN(a, b, x) (a<=x&&x<b)
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

string s[505];
int d[505][505][3];
signed main(void)
{
  int h, w;
  cin >> h >> w;
  REP(i, h) cin >> s[i];

  int sy, sx, gy, gx;
  REP(i, h) REP(j, w) {
    if(s[i][j] == 's') sx = j, sy = i, s[i][j] = '.';
    if(s[i][j] == 'g') gx = j, gy = i, s[i][j] = '.';
  }

  priority_queue<VI, VVI, greater<VI>> que;
  que.push({0, sy, sx, 2});
  REP(i, h) REP(j, w) d[i][j][0] = d[i][j][1] = d[i][j][2] = INF;
  d[sy][sx][2] = 0;

  while(que.size()) {
    VI v = que.top(); que.pop();
    int x = v[2], y = v[1], num = v[3];
    if(x == gx && y == gy) break;
    // 上下左右の4方向を試す
    REP(i, 4) {
      int nx = x + dx[i], ny = y + dy[i];
      // 盤面の範囲内ならば
      if(IN(0, w, nx) && IN(0, h, ny)) {
        // 普通に移動
        if(s[ny][nx] == '.' && d[ny][nx][num] > d[y][x][num] + 1) {
          d[ny][nx][num] = d[y][x][num] + 1;
          que.push({d[ny][nx][num], ny, nx, num});
        }
        // 塀を破壊
        if(s[ny][nx] == '#' && num >= 1 && d[ny][nx][num-1] > d[y][x][num] + 1) {
          d[ny][nx][num-1] = d[y][x][num] + 1;
          que.push({d[ny][nx][num-1], ny, nx, num-1});
        }
      }
    }
  }

  // goal にたどり着けるか
  if(d[gy][gx][0] != INF || d[gy][gx][1] != INF || d[gy][gx][2] != INF) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

  return 0;
}