Submission #30708736

---

Source Code Expand

// #include <atcoder/all>
// using namespace atcoder;
// using mint = modint998244353;
// using mint = modint1000000007;
#include <bits/stdc++.h>
#include <queue>
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,k,n) for (int i = (k); i < (n); ++i)
using namespace std;
using ll = long long;
// using P = pair<ll,ll>;
using P = pair<int,int>;
using vint = vector<int>;
using vll = vector<ll>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<ll>>;

// const ll INF = (ll)2e18+9;
const int INF = (int)2e9+7;
// const ll MOD = (ll)1e9+9;
template<typename T>
void chmin(T &a, T b) { a = min(a, b); }
template<typename T>
void chmax(T &a, T b) { a = max(a, b); }

template<typename T>
void print(vector<T> v) {
    int n = v.size();
    rep(i,n) {
        if (i == 0) cout << v[i];
        else cout << ' ' << v[i];
    }
    cout << endl;
}

int di[] = {-1, -1, 1, 1};
int dj[] = {-1, 1, -1, 1};

struct Point {
    int i, j, dir, cost;
};

bool operator>(const Point &a, const Point &b) {
    return a.cost > b.cost;
}

void solve() {
    int n;
    cin >> n;
    int ax, ay, bx, by;
    cin >> ax >> ay >> bx >> by;
    ax--, ay--, bx--; by--;

    vector<string> board(n);
    rep(i,n) cin >> board[i];

    vvint dist(n, vint(n, INF));
    dist[ax][ay] = 0;

    priority_queue<Point, vector<Point>, greater<Point>> pq;
    pq.push({ax, ay, 4, 0});
    vector<vvint> done(n, vvint(n, vint(5)));

    while (pq.size()) {
        auto [x, y, dir, cost] = pq.top();
        pq.pop();

        if (done[x][y][dir]) continue;
        done[x][y][dir] = 1;

        rep(d,4) {
            int nx = x + di[d], ny = y + dj[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (board[nx][ny] == '#') continue;
            int inc = (dir == d) ? 0 : 1;
            if (dist[nx][ny] >= cost+inc) {
                dist[nx][ny] = cost + inc;
                pq.push({nx, ny, d, cost+inc});
            }
        }
    }

    if (dist[bx][by] == INF) cout << -1 << endl;
    else cout << dist[bx][by] << endl;
}

int main() {
    solve();
    return 0;
}

Submission Info

Judge Result