Submission #1220907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220907		duckindog	Dangerous Skating (JOI16_skating)	C++20	100 / 100	250 ms	25788 KiB

skating

#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 10;
int r, c;
int a[N][N];
int stX, stY, edX, edY;

const int dX[] = {1, 0, -1, 0},
            dY[] = {0, 1, 0, -1};
int dir[N][N][4];

int f[N][N];

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> r >> c;
    for (int i = 1; i <= r; ++i) { 
        for (int j = 1; j <= c; ++j) { 
            char ch; cin >> ch;
            a[i][j] = (ch == '#');
        }
    }
    cin >> stX >> stY;
    cin >> edX >> edY;


    for (int i = 1; i <= r; ++i) { 
        for (int j = 1; j <= c; ++j) { 
            for (int w = 2; w <= 3; ++w) { 
                dir[i][j][w] = dir[i + dX[w]][j + dY[w]][w];
                if (a[i][j]) dir[i][j][w] = (w == 2 ? i - dX[w] : j - dY[w]);
            }
        }
    }
    for (int i = r; i >= 1; --i) { 
        for (int j = c; j >= 1; --j) { 
            for (int w = 0; w <= 1; ++w) { 
                dir[i][j][w] = dir[i + dX[w]][j + dY[w]][w];
                if (a[i][j]) dir[i][j][w] = (w == 0 ? i - dX[w] : j - dY[w]);
            }
        }
    }

    { // dijsktra
        memset(f, 63, sizeof f);
        using T = tuple<int, int, int>;
        priority_queue<T, vector<T>, greater<>> q;
        q.push({f[stX][stY] = 0, stX, stY});
        while (q.size()) { 
            auto [d, x, y] = q.top(); q.pop();

            for (int w = 0; w <= 3; ++w) { 
                int nX = (w % 2 == 0 ? dir[x][y][w] : x),
                    nY = (w % 2 == 1 ? dir[x][y][w] : y);
                if (f[nX][nY] > d + 1) { 
                    q.push({f[nX][nY] = d + 1, nX, nY});
                }
            }
            for (int w = 0; w <= 3; ++w) {
                int nX = x + dX[w], nY = y + dY[w];
                if (a[nX][nY]) continue;
                if (f[nX][nY] > d + 2) { 
                    q.push({f[nX][nY] = d + 2, nX, nY});
                }
            }
        }
    }

    cout << (f[edX][edY] == f[0][0] ? -1 : f[edX][edY]) << "\n";
}

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