Submission #1046846

#TimeUsernameProblemLanguageResultExecution timeMemory
10468461L1YAMaze (JOI23_ho_t3)C++17
62 / 100
279 ms63792 KiB
#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; const ll MOD = 1e9 + 7; const int MXN = 2e5 + 23; const int LOG = 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...