제출 #97498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97498		easrui	Dangerous Skating (JOI16_skating)	C++14	13 / 100	9 ms	4480 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<pii,pii> ppp;
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;

queue<ppp> Q;
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;
    Q.push(ppp(pii(sy,sx),pii(sy,sx)));
    while(!Q.empty()){
        ppp cur = Q.front();
        int x = cur.va.vb, y = cur.va.va, vx = cur.vb.vb, vy = cur.vb.va, D = dis[y][x], val;
        Q.pop();
        val = l[y][x]+1;
        if(dis[y][val]>=D+1){
            dis[y][val] = D+1;
            Q.push(ppp(pii(y,val),pii(y,x)));
        }
        val = r[y][x]-1;
        if(dis[y][val]>=D+1){
            dis[y][val] = D+1;
            Q.push(ppp(pii(y,val),pii(y,x)));
        }
        val = u[y][x]+1;
        if(dis[val][x]>=D+1){
            dis[val][x] = D+1;
            Q.push(ppp(pii(val,x),pii(y,x)));
        }
        val = d[y][x]-1;
        if(dis[val][x]>=D+1){
            dis[val][x] = D+1;
            Q.push(ppp(pii(val,x),pii(y,x)));
        }
        if(vx==x && vy==y) continue;
        if(vx==x){
            if(vy<y){
                val = vy+1;
                if(dis[val][x]>=D+1){
                    dis[val][x] = D+1;
                    Q.push(ppp(pii(val,x),pii(y,x)));
                }
            }
            else{
                val = vy-1;
                if(dis[val][x]>=D+1){
                    dis[val][x] = D+1;
                    Q.push(ppp(pii(val,x),pii(y,x)));
                }
            }
        }
        if(vy==y){
            if(vx<x){
                val = vx+1;
                if(dis[y][val]>=D+1){
                    dis[y][val] = D+1;
                    Q.push(ppp(pii(y,val),pii(y,x)));
                }
            }
            else{
                val = vx-1;
                if(dis[y][val]>=D+1){
                    dis[y][val] = D+1;
                    Q.push(ppp(pii(y,val),pii(y,x)));
                }
            }
        }
    }
    if(dis[ey][ex]==1e6) cout << -1;
    else cout << dis[ey][ex];
}

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