Submission #843957

#	Time	Username	Problem	Language	Result	Execution time	Memory
843957		mickey080929	Dangerous Skating (JOI16_skating)	C++14	100 / 100	114 ms	41100 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 vis[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};
        }
    }
    vector<pii> q1, q2, q3;
    q1.push_back({sx, sy});
    vis[sx][sy] = 1;
    int t = 0;
    while (!q1.empty() || !q2.empty()) {
        for (auto &[x, y] : q1) {
            if (x == ex && y == ey) {
                printf("%d\n", t);
                return 0;
            }
            for (auto &[nx, ny] : {L[x][y], R[x][y], U[x][y], D[x][y]}) {
                if (vis[nx][ny]) continue;
                vis[nx][ny] = 1;
                q2.push_back({nx, ny});
            }
        }
        for (auto &[x, y] : q1) {
            for (int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (!A[nx][ny]) continue;
                if (vis[nx][ny]) continue;
                vis[nx][ny] = 1;
                q3.push_back({nx, ny});
            }
        }
        q1 = q2;
        q2 = q3;
        q3.clear();
        t ++;
    }
    printf("-1\n");
}

Compilation message (stderr)

skating.cpp: In function 'int main()':
skating.cpp:59:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         for (auto &[x, y] : q1) {
      |                    ^
skating.cpp:64:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |             for (auto &[nx, ny] : {L[x][y], R[x][y], U[x][y], D[x][y]}) {
      |                        ^
skating.cpp:70:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |         for (auto &[x, y] : q1) {
      |                    ^
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: 65 / 65
• Subtask 3: 22 / 22