Submission #1048764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048764		Hamed_Ghaffari	Maze (JOI23_ho_t3)	C++17	62 / 100	327 ms	64436 KiB

Main

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

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;

#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define pb              push_back
#define Mp              make_pair
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)/2)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 1e9 + 23;

int R, C, N, sr, sc, er, ec;
vector<vector<char>> a;
int dx4[4] = {-1, 0, 1, 0};
int dy4[4] = {0, 1, 0, -1};
int dx8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
vector<vector<int>> dis, dis4, dis8;
vector<pii> V, U;
int D;

bool in(int x, int y) {
    return 0<=x&&x<R && 0<=y&&y<C;
}

void BFS() {
    queue<pii> q;
    for(auto p : V) {
        dis[p.X][p.Y] = D;
        q.push(p);
    }
    while(SZ(q)) {
        int x = q.front().X, y = q.front().Y;
        q.pop();
        for(int d=0; d<4; d++) {
            int xx = x+dx4[d], yy = y+dy4[d];
            if(in(xx, yy) && a[xx][yy]=='.' && dis[xx][yy] == INF) {
                dis[xx][yy] = D;
                V.pb(Mp(xx, yy));
                q.push(Mp(xx, yy));
            }
        }
    }
}

void BFS8() {
    queue<pii> q;
    for(auto p : V) {
        dis8[p.X][p.Y] = 0;
        U.pb(p);
        q.push(p);
    }
    while(SZ(q)) {
        int x = q.front().X, y = q.front().Y;
        q.pop();
        if(dis8[x][y] == N) continue;
        for(int d=0; d<8; d++) {
            int xx = x+dx8[d], yy = y+dy8[d];
            if(in(xx, yy) && dis[xx][yy] == INF && dis8[x][y]+1<dis8[xx][yy]) {
                dis8[xx][yy] = dis8[x][y]+1;
                U.pb(Mp(xx, yy));
                q.push(Mp(xx, yy));
            }
        }
    }
}

void BFS4() {
    queue<pii> q;
    for(auto p : V) {
        dis4[p.X][p.Y] = 0;
        q.push(p);
    }
    while(SZ(q)) {
        int x = q.front().X, y = q.front().Y;
        q.pop();
        for(int d=0; d<4; d++) {
            int xx = x+dx4[d], yy = y+dy4[d];
            if(in(xx, yy) && dis[xx][yy] == INF && dis8[xx][yy] != INF && dis4[x][y]+1<dis4[xx][yy]) {
                dis4[xx][yy] = dis4[x][y]+1;
                q.push(Mp(xx, yy));
            }
        }
    }
}

void Upd() {
    V.clear();
    for(auto [x, y] : U) {
        if(dis[x][y] == INF && (dis8[x][y]<N || dis4[x][y]<N+N))
            V.pb(Mp(x, y));
        dis8[x][y] = dis4[x][y] = INF;
    }
    U.clear();
}

void SP() {
    V = {{sr, sc}};
    while(1) {
        BFS();
        BFS8();
        BFS4();
        Upd();
        if(V.empty()) break;
        D++;
    }
}

void Main() {
    cin >> R >> C >> N;
    cin >> sr >> sc >> er >> ec; sr--; sc--; er--; ec--;
    a = vector<vector<char>>(R, vector<char>(C));
    dis = vector<vector<int>>(R, vector<int>(C, INF));
    dis4 = vector<vector<int>>(R, vector<int>(C, INF));
    dis8 = vector<vector<int>>(R, vector<int>(C, INF));
    for(int r=0; r<R; r++)
        for(int c=0; c<C; c++)
            cin >> a[r][c];
    SP();
    cout << dis[er][ec] << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    return 0;
}

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