Submission #59499999

---

Source Code Expand

#include<bits/stdc++.h>
#include"atcoder/all"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef vector<ll> vi;
constexpr ll mod = 1000000007;
typedef modint1000000007 mi;

int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int dist[4][1001][1001];

struct vertex{
    int val,dir,x,y;
};

bool operator< (const vertex &LHS,const vertex &RHS) {
    return LHS.val<RHS.val;
}

bool operator> (const vertex &LHS,const vertex &RHS) {
    return LHS.val>RHS.val;
}

int main(){
    int h,w;cin>>h>>w;
    int rs,cs,rt,ct;
    cin>>rs>>cs>>rt>>ct;
    rs--;cs--;rt--;ct--;
    vector<string>S(h);
    rep(i,h)cin>>S[i];

    rep(i,4)rep(j,h)rep(k,w)dist[i][j][k]=1e9;

    dist[0][rs][cs]=dist[1][rs][cs]=dist[2][rs][cs]=dist[3][rs][cs]=0;
    priority_queue<vertex,vector<vertex>,greater<vertex>> Q;
    Q.push({0,0,rs,cs});
    Q.push({0,1,rs,cs});
    Q.push({0,2,rs,cs});
    Q.push({0,3,rs,cs});

    while(Q.size()){
        vertex vi=Q.top();
        Q.pop();
        if(dist[vi.dir][vi.x][vi.y]<vi.val)continue;
        rep(k,4){
            int nx=vi.x+dx[k],ny=vi.y+dy[k];
            if(0<=nx&&nx<h&&0<=ny&&ny<w&&S[nx][ny]=='.'){
                if(k==vi.dir){
                    if(dist[k][nx][ny]>dist[vi.dir][vi.x][vi.y]){
                        dist[k][nx][ny]=dist[vi.dir][vi.x][vi.y];
                        Q.push({dist[k][nx][ny],k,nx,ny});
                    }
                }
                else{
                    if(dist[k][nx][ny]>dist[vi.dir][vi.x][vi.y]+1){
                        dist[k][nx][ny]=dist[vi.dir][vi.x][vi.y]+1;
                        Q.push({dist[k][nx][ny],k,nx,ny});
                    }
                }
            }
        }
    }
    cout<<min({dist[0][rt][ct],dist[1][rt][ct],dist[2][rt][ct],dist[3][rt][ct]})<<endl;
}

Submission Info

Judge Result