Submission #512249

#	Time	Username	Problem	Language	Result	Execution time	Memory
512249		79brue	Dangerous Skating (JOI16_skating)	C++14	100 / 100	1337 ms	47004 KiB

skating

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int xx[] = {1, 0, -1, 0};
const int yy[] = {0, 1, 0, -1};

struct dat{
    int x, y, d, w;
    dat(){}
    dat(int x, int y, int d, int w): x(x), y(y), d(d), w(w){}

    bool operator<(const dat &r)const{
        return w>r.w;
    }
};

int n, m;
bool arr[1005][1005];
int wallX[1005][1005][4], wallY[1005][1005][4];
bool visited[1005][1005][5];

int r1, c1;
int r2, c2;
priority_queue<dat> que;

void makeWall(){
    for(int i=1; i<=n; i++){
        for(int j=m; j>=1; j--){
            if(arr[i][j]) wallX[i][j][1] = i, wallY[i][j][1] = j-1;
            else wallX[i][j][1] = wallX[i][j+1][1], wallY[i][j][1] = wallY[i][j+1][1];
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(arr[i][j]) wallX[i][j][3] = i, wallY[i][j][3] = j+1;
            else wallX[i][j][3] = wallX[i][j-1][3], wallY[i][j][3] = wallY[i][j-1][3];
        }
    }
    for(int i=n; i>=1; i--){
        for(int j=1; j<=m; j++){
            if(arr[i][j]) wallX[i][j][0] = i-1, wallY[i][j][0] = j;
            else wallX[i][j][0] = wallX[i+1][j][0], wallY[i][j][0] = wallY[i+1][j][0];
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(arr[i][j]) wallX[i][j][2] = i+1, wallY[i][j][2] = j;
            else wallX[i][j][2] = wallX[i-1][j][2], wallY[i][j][2] = wallY[i-1][j][2];
        }
    }
}

void queueInsert(int x, int y, int d, int w){
    if(visited[x][y][d] || arr[x][y]) return;
    que.push(dat(x, y, d, w));
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            scanf(" %c", &c);
            arr[i][j] = (c == '#');
        }
    }
    scanf("%d %d %d %d", &r1, &c1, &r2, &c2);

    makeWall();

    que.push(dat(r1, c1, 4, 0));
    while(!que.empty()){
        dat tmp = que.top(); que.pop();
        int x = tmp.x, y = tmp.y, d = tmp.d, w = tmp.w;
        if(visited[tmp.x][tmp.y][tmp.d]) continue;
        visited[tmp.x][tmp.y][tmp.d] = 1;
//        printf("%d %d %d %d\n", x, y, d, w);
        if(x == r2 && y == c2){
            printf("%d", w);
            return 0;
        }

        for(int i=0; i<4; i++){
            queueInsert(wallX[x][y][i], wallY[x][y][i], i, w+1);
            queueInsert(x+xx[i], y+yy[i], i^2, w+2);
        }
    }

    printf("-1");
}

Compilation message (stderr)

skating.cpp: In function 'int main()':
skating.cpp:77:35: warning: unused variable 'd' [-Wunused-variable]
   77 |         int x = tmp.x, y = tmp.y, d = tmp.d, w = tmp.w;
      |                                   ^
skating.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skating.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |             scanf(" %c", &c);
      |             ~~~~~^~~~~~~~~~~
skating.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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