Submission #843946

#	Time	Username	Problem	Language	Result	Execution time	Memory
843946		mickey080929	Dangerous Skating (JOI16_skating)	C++17	13 / 100	3044 ms	21528 KiB

skating

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int inf = 1e9;

int n, m;
int sx, sy, ex, ey;
int A[1010][1010];
pii L[1010][1010], R[1010][1010], U[1010][1010], D[1010][1010];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int dist[1010][1010];

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);
            if (c == '#') A[i][j] = 0;
            else A[i][j] = 1;
        }
    }
    scanf("%d %d", &sx, &sy);
    scanf("%d %d", &ex, &ey);
    for (int i=1; i<=n; i++) {
        int p = 1;
        for (int j=2; j<=m; j++) {
            if (!A[i][j]) p = j;
            else L[i][j] = {i, p+1};
        }
        p = m;
        for (int j=m-1; j>=1; j--) {
            if (!A[i][j]) p = j;
            else R[i][j] = {i, p-1};
        }
    }
    for (int j=1; j<=m; j++) {
        int p = 1;
        for (int i=2; i<=n; i++) {
            if (!A[i][j]) p = i;
            else U[i][j] = {p+1, j};
        }
        p = n;
        for (int i=n-1; i>=1; i--) {
            if (!A[i][j]) p = i;
            else D[i][j] = {p-1, j};
        }
    }
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) dist[i][j] = inf;
    priority_queue<tuple<int,int,int>> pq;
    pq.push({0, sx, sy});
    dist[sx][sy] = 0;
    while (!pq.empty()) {
        auto [c, x, y] = pq.top();
        assert(1 <= x && x <= n && 1 <= y && y <= m);
        pq.pop();
        if (dist[x][y] < c) continue;
        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (!A[nx][ny]) continue;
            if (dist[nx][ny] <= c + 2) continue;
            dist[nx][ny] = c + 2;
            pq.push({c + 2, nx, ny});
        }
        for (auto &[nx, ny] : {L[x][y], R[x][y], U[x][y], D[x][y]}) {
            if (dist[nx][ny] <= c + 1) continue;
            dist[nx][ny] = c + 1;
            pq.push({c + 1, nx, ny});
        }
    }
    if (dist[ex][ey] >= inf) printf("-1\n");
    else printf("%d\n", dist[ex][ey]);
}

Compilation message (stderr)

skating.cpp: In function 'int main()':
skating.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skating.cpp:23:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |             scanf(" %c", &c);
      |             ~~~~~^~~~~~~~~~~
skating.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d %d", &sx, &sy);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
skating.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     scanf("%d %d", &ex, &ey);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

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