Submission #806826

#	Time	Username	Problem	Language	Result	Execution time	Memory
806826		someone	Maze (JOI23_ho_t3)	C++14	100 / 100	760 ms	269340 KiB

Main

#include <bits/stdc++.h>
//#define int long long
#define x first
#define y second
using namespace std;

const int N = 6e6 + 42, INF = 1e9 + 42;

int dl[] = {0, 0, 1, -1},
    dc[] = {1, -1, 0, 0},
    trans[] = {0, 0, 0, 0};

bool etat[N], vu[N];
int row, col, n, ldeb, cdeb, lfin, cfin, ans = INF, dist[N], lhor[N], rhor[N], lver[N], rver[N];

inline bool valid(int l, int c) {
    return -1 < l && l < row && -1 < c && c < col;
}

void BFS() {
    deque<pair<int, int>> dq;
    dist[ldeb * col + cdeb] = 0;
    dq.push_front({ldeb, cdeb});
    while(!dq.empty()) {
        auto act = dq[0];
        dq.pop_front();
        int id = act.x * col + act.y;
        if(!vu[id]) {
            vu[id] = true;
            int dx = abs(lfin - act.x), dy = abs(cfin - act.y);
            if(dx <= n && dy <= n && dx + dy != 2*n)
                ans = min(ans, dist[id]+1);
            for(int i = 0; i < 4; i++) {
                int x = act.x + dl[i], y = act.y + dc[i], j = id + trans[i];
                if(valid(x, y) && etat[j] && !vu[j]) {
                    dq.push_front({x, y});
                    dist[j] = dist[id];
                }
            }
			/*
            //(act.x - n, act.y - n + 1) - (act.x - n, act.y + n - 1)
            //(act.x + n, act.y - n + 1) - (act.x + n, act.y + n - 1)
            for(int j = act.y - n + 1; j <= act.y + n - 1; j++) {
                if(valid(act.x - n, j)) {
                    dq.push_back({act.x - n, j});
                    dist[(act.x - n) * col + j] = min(dist[(act.x - n) * col + j], dist[id]+1);
                }
                if(valid(act.x + n, j)) {
                    dq.push_back({act.x + n, j});
                    dist[(act.x + n) * col + j] = min(dist[(act.x + n) * col + j], dist[id]+1);
                }
            }
            //(act.x - n + 1, act.y - n) - (act.x + n - 1, act.y - n)
            //(act.x - n + 1, act.y + n) - (act.x + n - 1, act.y + n)
            for(int i = act.x - n + 1; i <= act.x + n - 1; i++) {
                if(valid(i, act.y - n)) {
                    dq.push_back({i, act.y - n});
                    dist[i * col + act.y - n] = min(dist[i * col + act.y - n], dist[id]+1);
                }
                if(valid(i, act.y + n)) {
                    dq.push_back({i, act.y + n});
                    dist[i * col + act.y + n] = min(dist[i * col + act.y + n], dist[id]+1);
                }
            }*/

            //(act.x - n, act.y - n + 1) - (act.x - n, act.y + n - 1)
            int l = (act.y + n) / (2 * n - 1) - 1;
            if(act.x >= n) {
                int i = (act.x - n) * col + l;
                if(l != -1) {
                    int pos = (act.x - n) * col + rhor[i],
                        sup = max(lhor[i], act.y - n + 1);
                    while(rhor[i] >= sup) {
                        dist[pos] = min(dist[pos], dist[id]+1);
                        dq.push_back({act.x - n, rhor[i]});
                        pos--;
                        rhor[i]--;
                    }
                }
                i++;
                if((2 * n - 1) * (l+1) < col) {
                    int pos = (act.x - n) * col + lhor[i],
                        inf = min(rhor[i], act.y + n - 1);
                    while(lhor[i] <= inf) {
                        dist[pos] = min(dist[pos], dist[id]+1);
                        dq.push_back({act.x - n, lhor[i]});
                        pos++;
                        lhor[i]++;
                    }
                }
            }
            //(act.x + n, act.y - n + 1) - (act.x + n, act.y + n - 1)
            if(act.x + n < row) {
                int i = (act.x + n) * col + l;
                if(l != -1) {
                    int pos = (act.x + n) * col + rhor[i],
                        sup = max(lhor[i], act.y - n + 1);
                    while(rhor[i] >= sup) {
                        dist[pos] = min(dist[pos], dist[id]+1);
                        dq.push_back({act.x + n, rhor[i]});
                        pos--;
                        rhor[i]--;
                    }
                }
                i++;
                if((2 * n - 1) * (l+1) < col) {
                    int pos = (act.x + n) * col + lhor[i],
                        inf = min(rhor[i], act.y + n - 1);
                    while(lhor[i] <= inf) {
                        dist[pos] = min(dist[pos], dist[id]+1);
                        dq.push_back({act.x + n, lhor[i]});
                        pos++;
                        lhor[i]++;
                    }
                }
            }


            //(act.x - n + 1, act.y - n) - (act.x + n - 1, act.y - n)
            int h = (act.x + n) / (2 * n - 1) - 1;
            if(act.y >= n) {
                int i = h * col + (act.y - n);
                if(h != -1) {
                    int pos = rver[i] * col + act.y - n,
                        sup = max(lver[i], act.x - n + 1);
                    while(rver[i] >= sup) {
                        dist[pos] = min(dist[pos], dist[id]+1);
                        dq.push_back({rver[i], act.y - n});
                        pos -= col;
                        rver[i]--;
                    }
                }
                i += col;
                if((2 * n - 1) * (h+1) < row) {
                    int pos = lver[i] * col + act.y - n,
                        inf = min(rver[i], act.x + n - 1);
                    while(lver[i] <= inf) {
                        dist[pos] = min(dist[pos], dist[id]+1);
                        dq.push_back({lver[i], act.y - n});
                        pos += col;
                        lver[i]++;
                    }
                }
            }
            //(act.x - n + 1, act.y + n) - (act.x + n - 1, act.y + n)
            if(act.y + n < col) {
                int i = h * col + (act.y + n);
                if(h != -1) {
                    int pos = rver[i] * col + act.y + n,
                        sup = max(lver[i], act.x - n + 1);
                    while(rver[i] >= sup) {
                        dist[pos] = min(dist[pos], dist[id]+1);
                        dq.push_back({rver[i], act.y + n});
                        pos -= col;
                        rver[i]--;
                    }
                }
                i += col;
                if((2 * n - 1) * (h+1) < row) {
                    int pos = lver[i] * col + act.y + n,
                        inf = min(rver[i], act.x + n - 1);
                    while(lver[i] <= inf) {
                        dist[pos] = min(dist[pos], dist[id]+1);
                        dq.push_back({lver[i], act.y + n});
                        pos += col;
                        lver[i]++;
                    }
                }
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> row >> col >> n >> ldeb >> cdeb >> lfin >> cfin;
    ldeb--, cdeb--, lfin--, cfin--;

    for(int i = 0; i < 4; i++)
        trans[i] = dl[i] * col + dc[i];
    for(int i = 0; i < row*col; i++)
        dist[i] = INF;
    for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++) {
            char c; cin >> c;
            etat[i * col + j] = (c == '.');
        }
    
    for(int i = 0; i < row; i++)
        for(int j = 0; (2*n-1)*j < col; j++) {
            lhor[i * col + j] = (2*n-1)*j;
            rhor[i * col + j] = min((2*n-1)*(j+1), col)-1;
        }
    for(int i = 0; (2*n-1)*i < row; i++)
        for(int j = 0; j < col; j++) {
            lver[i * col + j] = (2*n-1)*i;
            rver[i * col + j] = min((2*n-1)*(i+1), row)-1;
        }
    BFS();
    ans = min(ans, dist[lfin * col + cfin]);
    cout << ans << '\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6