Submission #8956033

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll LLINF = 1LL << 58;
const int INF = 1 << 30;
using Edge = tuple<ll, int, int>;
const int dy[] = {0, 1, 0, -1}, dx[] = {1, 0, -1, 0};

int H, W, T;
string S[10];
int sx, sy;
// コストを保持する2次元配列
ll v[10][10];

// ダイクストラ法
ll check(int cost) {
  fill_n(*v, 10 * 10, LLINF);
  priority_queue<Edge, vector<Edge>, greater<Edge>> que;
  que.emplace(0, sx, sy);
  while (!que.empty()) {
    int x, y;
    ll z;
    tie(z, x, y) = que.top();
    que.pop();
    if (S[y][x] == 'G') return z;
    // 4方向を調べる
    for (int i = 0; i < 4; i++) {
      // ny:=次のノードのy座標、nx:=次のノードのx座標
      int ny = y + dy[i], nx = x + dx[i];
      if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
      // nc:=次のノードへのコスト
      ll nc = z;
      // 黒マスならコストcostがかかる
      if (S[ny][nx] == '#') nc += cost;
      // そうでなければコスト1がかかる
      else
        nc += 1;
      // 保持しているコストのほうが今のコスト以下なら以下の処理をスキップ
      if (v[nx][ny] <= nc) continue;
      v[nx][ny] = nc;
      que.emplace(nc, nx, ny);
    }
  }
}

int main() {
  cin >> H >> W >> T;
  for (int i = 0; i < H; i++) {
    cin >> S[i];
    for (int j = 0; j < W; j++) {
      if (S[i][j] == 'S') sx = j, sy = i;
    }
  }

  // 二分探索
  // T秒以内にゴール地点に到着できる最大の正整数を探す
  int low = 1, high = INF;
  while (high - low > 0) {
    int mid = (low + high + 1) >> 1;
    if (check(mid) <= T)
      low = mid;
    else
      high = mid - 1;
  }
  cout << low << endl;
}

Submission Info

Judge Result