提出 #53420373

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <queue>
#define ll long long
#define ull unsigned long long
#define pa first
#define pb second
#define endl '\n'
#define vint vector<int>
#define vlong vector<ll>
#define pii pair<int, int>
#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define rng(i, a, b) for (int i = int(a); i <= int(b); i++)
#define per(i, a, b) for (int i = int(b - 1); i >= int(a); i--)
#define gnr(i, a, b) for (int i = int(b); i >= int(a); i--)
using namespace std;
#define ATC
#ifdef ATC
#include <atcoder/all>
using namespace atcoder;
#endif

#ifdef MT
void solve()
{
}
#endif

const int N = 510, INF = 0x3f3f3f3f;
char mp[N][N];
int n;

struct Vec {
    int i, j;
    Vec operator+(const Vec& rhs) const
    {
        return { i + rhs.i, j + rhs.j };
    }
} dir[4] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

bool isvaild(int i, int j)
{
    return i && j && i <= n && j <= n;
}

bool isvaild(Vec& v)
{
    return isvaild(v.i, v.j);
}

struct Route {
    Vec pos;
    int w;
    bool operator<(const Route& rhs) const
    {
        return w > rhs.w;
    }
};
#define cast(arr, vec) arr[(vec.i)][(vec.j)]
int dijkstra(Vec s, Vec t, char c)
{
    vector<vint> dp(n + 1, vint(n + 1, INF));
    priority_queue<Route> pq;
    cast(dp, s) = 0;
    pq.push({ s, 0 });
    while (!pq.empty()) {
        auto top = pq.top();
        pq.pop();
        for (auto d : dir) {
            Vec cur = top.pos + d;
            if (isvaild(cur) && cast(dp, cur) > top.w + (c != cast(mp, cur))) {
                cast(dp, cur) = top.w + (c != cast(mp, cur));
                pq.push({ cur, cast(dp, cur) });
            }
        }
    }
    return cast(dp, t);
}

int main(void)
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    rng(i, 1, n)
    {
        rng(j, 1, n)
        {
            cin >> mp[i][j];
        }
    }
    cout << dijkstra({ 1, 1 }, { n, n }, 'R') + dijkstra({ 1, n }, { n, 1 }, 'B');

#ifdef MT
    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
        solve();
#endif
}

提出情報

ジャッジ結果