Submission #153527

#	Time	Username	Problem	Language	Result	Execution time	Memory
153527		onjo0127	Dangerous Skating (JOI16_skating)	C++11	100 / 100	887 ms	23664 KiB

skating

#include <bits/stdc++.h>
using namespace std;
using tiii = tuple<int, int, int>;

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

char A[1009][1009];
int L[1009][1009], RR[1009][1009], U[1009][1009], D[1009][1009], S[1009][1009];

int main() {
    int R, C; scanf("%d%d",&R,&C);
    for(int i=1; i<=R; i++) {
        for(int j=1; j<=C; j++) {
            scanf(" %c", &A[i][j]);
            S[i][j] = 1e9;
        }
    }
    int xs, ys, xe, ye; scanf("%d%d%d%d",&xs,&ys,&xe,&ye);
    for(int i=1; i<=R; i++) {
        int ls = -1;
        for(int j=1; j<=C; j++) {
            if(A[i][j] == '#') ls = j+1;
            L[i][j] = ls;
        }
        for(int j=C; j>=1; j--) {
            if(A[i][j] == '#') ls = j-1;
            RR[i][j] = ls;
        }
    }
    for(int i=1; i<=C; i++) {
        int ls = -1;
        for(int j=1; j<=R; j++) {
            if(A[j][i] == '#') ls = j+1;
            U[j][i] = ls;
        }
        for(int j=R; j>=1; j--) {
            if(A[j][i] == '#') ls = j-1;
            D[j][i] = ls;
        }
    }
    S[xs][ys] = 0;
    priority_queue<tiii> pq; pq.push((tiii){0, xs, ys});
    while(pq.size()) {
        int d, x, y; tie(d, x, y) = pq.top(); d = -d; pq.pop();
        if(S[x][y] != d) continue;
        vector<tiii> nx;
        nx.push_back((tiii){d+1, x, L[x][y]});
        nx.push_back((tiii){d+1, x, RR[x][y]});
        nx.push_back((tiii){d+1, U[x][y], y});
        nx.push_back((tiii){d+1, D[x][y], y});
        for(int k=0; k<4; k++) {
            int X = x+dx[k], Y = y+dy[k];
            if(A[X][Y] != '#') nx.push_back((tiii){d+2, X, Y});
        }
        for(auto& it: nx) {
            int dd, xx, yy; tie(dd, xx, yy) = it;
            if(S[xx][yy] > dd) {
                S[xx][yy] = dd;
                pq.push((tiii){-dd, xx, yy});
            }
        }
    }
    if(S[xe][ye] == 1e9) puts("-1");
    else printf("%d", S[xe][ye]);
    return 0;
}

Compilation message (stderr)

skating.cpp: In function 'int main()':
skating.cpp:12:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int R, C; scanf("%d%d",&R,&C);
               ~~~~~^~~~~~~~~~~~~~
skating.cpp:15:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &A[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~
skating.cpp:19:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int xs, ys, xe, ye; scanf("%d%d%d%d",&xs,&ys,&xe,&ye);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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