AtCoder Regular Contest 003 C - 暗闇帰り道

問題

　のマスが与えられ、各マスには障害物か1桁の数字が書き込まれている。各マスのコストはで与えられ、スタートからゴールまでの区間のコストの最小値がその経路のコストとなる。スタートからゴールまでのコストの最大値を求めよ。

解法

　2分探索でコストの最大値を決めていく。各コストでスタートからゴールまで行けるかどうかは幅優先探索で求まる。

反省

　ずっとダイクストラ法でやろうとしてTLEやらMLEやらを起こしていた。しばらく考えてもわからなかったので問題名でググって出てきたブログに上の解法が書かれていたのでそれを書いてAC。疲労から頭が回っていないのもあって正常な思考ができなかった。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

ll N, M;
vector<string> c;
pair<ll, ll> start, goal;


bool canGoal(double cost) {
    struct Element {
        ll x, y, time;
    };
    queue<Element> q;
    q.push({ start.second, start.first, 0 });

    vector<vector<bool>> visit(N, vector<bool>(M, false));
    visit[start.first][start.second] = true;

    auto isOK = [&](ll x, ll y, ll time) {
        return (0 <= x && x < M && 0 <= y && y < N && c[y][x] != '#'
            && !visit[y][x]
            && (c[y][x] - '0') * pow(0.99, time) >= cost);
    };

    constexpr ll dx[4] = { 1, 0, -1, 0 };
    constexpr ll dy[4] = { 0, 1, 0, -1 };

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        for (ll i = 0; i < 4; i++) {
            ll nx = curr.x + dx[i];
            ll ny = curr.y + dy[i];
            ll nt = curr.time + 1;

            if (!isOK(nx, ny, nt)) {
                continue;
            }

            if (c[ny][nx] == 'g') {
                return true;
            }

            q.push({ nx, ny, nt });
            visit[ny][nx] = true;
        }
    }

    return false;
}

int main() {
    cin >> N >> M;
    c.resize(N);
    for (ll i = 0; i < N; i++) {
        cin >> c[i];
    }

    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < M; j++) {
            if (c[i][j] == 's') {
                start = { i, j };
            } else if (c[i][j] == 'g') {
                goal = { i, j };
            }
        }
    }

    double ok = -1, ng = INT_MAX;
    for (ll i = 0; i < 100; i++) {
        double mid = (ok + ng) / 2;
        (canGoal(mid) ? ok = mid : ng = mid);
    }

    if (ok < 0) {
        cout << "-1" << endl;
    } else {
        printf("%.10f\n", ok);
    }
}