Submission #97490

#	Time	Username	Problem	Language	Result	Execution time	Memory
97490		easrui	Dangerous Skating (JOI16_skating)	C++14	78 / 100	3034 ms	71056 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,v1,v2;
    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;
        v1 = l[y][x]+1;
        v2 = x-1;
        cnt = 1;
        while(v1<=v2){
            if(cnt%2){
                if(dis[y][v1]>D+cnt){
                    dis[y][v1] = D+cnt;
                    PQ.push(ppi(-D-cnt,pii(y,v1)));
                }
                v1++;
            }
            else{
                if(dis[y][v2]>D+cnt){
                    dis[y][v2] = D+cnt;
                    PQ.push(ppi(-D-cnt,pii(y,v2)));
                }
                v2--;
            }
            cnt++;
        }
        v1 = x+1;
        v2 = r[y][x]-1;
        cnt = 1;
        while(v1<=v2){
            if(cnt%2){
                if(dis[y][v2]>D+cnt){
                    dis[y][v2] = D+cnt;
                    PQ.push(ppi(-D-cnt,pii(y,v2)));
                }
                v2--;
            }
            else{
                if(dis[y][v1]>D+cnt){
                    dis[y][v1] = D+cnt;
                    PQ.push(ppi(-D-cnt,pii(y,v1)));
                }
                v1++;
            }
            cnt++;
        }
        v1 = u[y][x]+1;
        v2 = y-1;
        cnt = 1;
        while(v1<=v2){
            if(cnt%2){
                if(dis[v1][x]>D+cnt){
                    dis[v1][x] = D+cnt;
                    PQ.push(ppi(-D-cnt,pii(v1,x)));
                }
                v1++;
            }
            else{
                if(dis[v2][x]>D+cnt){
                    dis[v2][x] = D+cnt;
                    PQ.push(ppi(-D-cnt,pii(v2,x)));
                }
                v2--;
            }
            cnt++;
        }
        v1 = y+1;
        v2 = d[y][x]-1;
        cnt = 1;
        while(v1<=v2){
            if(cnt%2){
                if(dis[v2][x]>D+cnt){
                    dis[v2][x] = D+cnt;
                    PQ.push(ppi(-D-cnt,pii(v2,x)));
                }
                v2--;
            }
            else{
                if(dis[v1][x]>D+cnt){
                    dis[v1][x] = D+cnt;
                    PQ.push(ppi(-D-cnt,pii(v1,x)));
                }
                v1++;
            }
            cnt++;
        }
    }
    if(dis[ey][ex]==1e6) cout << -1;
    else cout << dis[ey][ex];
}

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