Submission #1197946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197946		JooDdae	Dangerous Skating (JOI16_skating)	C++20	100 / 100	211 ms	35116 KiB

skating

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int INF = 1e9;

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

int n, m, sx, sy, ex, ey, d[1010][1010][4], c[1010][1010][4];
string s[1010];
vector<queue<array<int, 4>>> Q(3);

void add(int sx, int sy, int i, int p) {
    if(!d[sx][sy][i]) return;

    if(c[sx][sy][i] > p) c[sx][sy][i] = p, Q[p%3].push({p, sx, sy, i});
    int x = sx + dx[i]*d[sx][sy][i], y = sy + dy[i]*d[sx][sy][i];
    if(c[x][y][i^1] > p+1) c[x][y][i^1] = p+1, Q[(p+1)%3].push({p+1, x, y, i^1});
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0;i<n;i++) cin >> s[i];
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<4;k+=2) d[i][j][k] = s[i-1][j-1] == '#' ? -1 : d[i+dx[k]][j+dy[k]][k]+1;
    for(int i=n;i>=1;i--) for(int j=m;j>=1;j--) for(int k=1;k<4;k+=2) d[i][j][k] = s[i-1][j-1] == '#' ? -1 : d[i+dx[k]][j+dy[k]][k]+1;

    cin >> sx >> sy >> ex >> ey;
    if(sx == ex && sy == ey) return cout << 0, 0;

    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<4;k++) c[i][j][k] = INF;
    for(int i=0;i<4;i++) add(sx, sy, i, 1);

    int flag = 1;
    while(flag--) {
        for(auto &q : Q) while(!q.empty()) {
            auto [p, x, y, d] = q.front(); q.pop();
            if(c[x][y][d] < p) continue;
            if(x == ex && y == ey) return cout << p-1, 0;

            flag = 1;

            int xx = x+dx[d], yy = y+dy[d], P = p+2;
            if(s[xx-1][yy-1] != '#' && c[xx][yy][d] > P) Q[P%3].push({P, xx, yy, d}), c[xx][yy][d] = P;
            for(int i=0;i<2;i++) add(x, y, d^2^i, p);
        }
    }

    cout << -1;
}

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