提出 #53423380

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n;
vector<vector<char>> c;

bool bfs(int mid, pair<int, int> start, pair<int, int> goal, char color) {
    vector<vector<bool>> seen(n, vector<bool>(n, false));
    seen[0][0] = true;
    int gi = goal.first, gj = goal.second;
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
    q.push({0, start});
    while (!q.empty()) {
        auto [cost, pos] = q.top(); q.pop();
        int i = pos.first, j = pos.second;
        if (i == gi && j == gj) {
            return true;
        }
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        for (auto [di, dj] : directions) {
            int ni = i + di, nj = j + dj;
            if (ni >= 0 && ni < n && nj >= 0 && nj < n && !seen[ni][nj]) {
                seen[ni][nj] = true;
                if (color == c[ni][nj]) {
                    q.push({cost, {ni, nj}});
                } else {
                    if (cost == mid) {
                        continue;
                    } else {
                        q.push({cost + 1, {ni, nj}});
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    cin >> n;
    c.resize(n, vector<char>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> c[i][j];
        }
    }

    int l = -1, r = n * n;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (bfs(mid, {0, 0}, {n - 1, n - 1}, 'R')) {
            r = mid;
        } else {
            l = mid;
        }
    }
    int ans = r;
    l = -1, r = n * 2 + 1;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (bfs(mid, {0, n - 1}, {n - 1, 0}, 'B')) {
            r = mid;
        } else {
            l = mid;
        }
    }
    ans += r;
    cout << ans << endl;

    return 0;
}

提出情報

ジャッジ結果