Submission #1048848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048848		Hamed_Ghaffari	Maze (JOI23_ho_t3)	C++17	100 / 100	411 ms	68564 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 dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
vector<vector<int>> dis;
 
bool in(int x, int y) {
    return 0<=x&&x<R && 0<=y&&y<C;
}
 
void BFS() {
    queue<pair<pii, pii>> q1, q2;
    dis[sr][sc] = 0;
    q1.push(Mp(Mp(sr, sc), Mp(0, 0)));
    while(SZ(q1)+SZ(q2)) {
        while(SZ(q1)) {
            auto [x, y] = q1.front().X;
            q1.pop();
            for(int d=0; d<4; d++) {
                int xx = x+dx[d], yy = y+dy[d];
                if(!in(xx, yy)) continue;
                if(a[xx][yy] == '.') {
                    if(dis[xx][yy]>dis[x][y]) {
                        dis[xx][yy] = dis[x][y];
                        q1.push(Mp(Mp(xx, yy), Mp(0, 0)));
                    }
                }
                else {
                    if(dis[xx][yy]>dis[x][y]+1) {
                        dis[xx][yy] = dis[x][y]+1;
                        q2.push(Mp(Mp(xx, yy), Mp(N-1, N-1)));
                    }
                }
            }
        }
        while(SZ(q2)) {
            auto [x, y] = q2.front().X;
            auto [xd, yd] = q2.front().Y;
            q2.pop();
            if(min(xd, yd) == 0) q1.push(Mp(Mp(x, y), Mp(0, 0)));
            for(int d=0; d<4; d++) {
                int xx = x+dx[d], yy = y+dy[d];
                int xxd = xd - (dx[d]!=0), yyd = yd - (dy[d]!=0);
                if(!in(xx, yy) || xxd < 0 || yyd < 0) continue;
                if(dis[xx][yy]>dis[x][y]) {
                    dis[xx][yy] = dis[x][y];
                    q2.push(Mp(Mp(xx, yy), Mp(xxd, yyd)));
                }
            }
        }
    }
}

 
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));
    for(int r=0; r<R; r++)
        for(int c=0; c<C; c++)
            cin >> a[r][c];
    BFS();
    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: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6