Submission #97506

#	Time	Username	Problem	Language	Result	Execution time	Memory
97506		easrui	Dangerous Skating (JOI16_skating)	C++14	100 / 100	632 ms	23660 KiB

skating

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
const int MAX = 1005;
typedef pair<int,int> pii;
typedef pair<int,pii> ppi;
int R,C,sx,sy,ex,ey,cnt,dis[MAX][MAX],l[MAX][MAX],r[MAX][MAX],u[MAX][MAX],d[MAX][MAX];
bool init[MAX][MAX];
char c;
priority_queue<ppi> PQ;
int main()
{
    cin >> R >> C;
    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            cin >> c;
            if(c=='.') init[i][j] = 1;
            dis[i][j] = 1e6;
        }
    }
    cin >> sy >> sx >> ey >> ex;
    for(int i=1; i<=R; i++){
        for(int j=1; j<=C; j++){
            if(init[i][j]) l[i][j] = cnt;
            else cnt = j;
        }
        for(int j=C; j>=1; j--){
            if(init[i][j]) r[i][j] = cnt;
            else cnt = j;
        }
    }
    for(int j=1; j<=C; j++){
        for(int i=1; i<=R; i++){
            if(init[i][j]) u[i][j] = cnt;
            else cnt = i;
        }
        for(int i=R; i>=1; i--){
            if(init[i][j]) d[i][j] = cnt;
            else cnt = i;
        }
    }
    dis[sy][sx] = 0;
    int D,y,x,val;
    PQ.push(ppi(0,pii(sy,sx)));
    while(!PQ.empty()){
        D = -PQ.top().va;
        y = PQ.top().vb.va;
        x = PQ.top().vb.vb;
        PQ.pop();
        if(D>dis[y][x]) continue;
        val = l[y][x]+1;
        if(dis[y][val]>D+1){
            dis[y][val] = D+1;
            PQ.push(ppi(-D-1,pii(y,val)));
        }
        val = r[y][x]-1;
        if(dis[y][val]>D+1){
            dis[y][val] = D+1;
            PQ.push(ppi(-D-1,pii(y,val)));
        }
        val = u[y][x]+1;
        if(dis[val][x]>D+1){
            dis[val][x] = D+1;
            PQ.push(ppi(-D-1,pii(val,x)));
        }
        val = d[y][x]-1;
        if(dis[val][x]>D+1){
            dis[val][x] = D+1;
            PQ.push(ppi(-D-1,pii(val,x)));
        }
        val = x+1;
        if(init[y][val] && dis[y][val]>D+2){
            dis[y][val] = D+2;
            PQ.push(ppi(-D-2,pii(y,val)));
        }
        val = x-1;
        if(init[y][val] && dis[y][val]>D+2){
            dis[y][val] = D+2;
            PQ.push(ppi(-D-2,pii(y,val)));
        }
        val = y+1;
        if(init[val][x] && dis[val][x]>D+2){
            dis[val][x] = D+2;
            PQ.push(ppi(-D-2,pii(val,x)));
        }
        val = y-1;
        if(init[val][x] && dis[val][x]>D+2){
            dis[val][x] = D+2;
            PQ.push(ppi(-D-2,pii(val,x)));
        }
    }
    if(dis[ey][ex]==1e6) cout << -1;
    else cout << dis[ey][ex];
}

• Subtask 1: 13 / 13
• Subtask 2: 65 / 65
• Subtask 3: 22 / 22