제출 #853240

#제출 시각아이디문제언어결과실행 시간메모리
853240NK_포탈들 (BOI14_portals)C++17
0 / 100
1 ms344 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define pb push_back #define pf push_front #define mp make_pair #define f first #define s second #define sz(x) int(x.size()) template<class T> using V = vector<T>; using pi = pair<int, int>; using vi = V<int>; using vpi = V<pi>; using ll = long long; using pl = pair<ll, ll>; using vpl = V<pl>; using vl = V<ll>; using db = long double; template<class T> using pq = priority_queue<T, V<T>, greater<T>>; const int MOD = 1e9 + 7; const ll INFL = ll(1e17); const int LG = 18; int dx[4] = {0, 0, -1, 1}; int dy[4] = {-1, 1, 0, 0}; int main() { cin.tie(0)->sync_with_stdio(0); int N, M; cin >> N >> M; N += 2, M += 2; V<string> A(N, string(M, '#')); for(int i = 1; i < N-1; i++) { string t; cin >> t; t = "#"+t+"#"; A[i] = t; } V<vi> W(N, vi(M, MOD)), vis(N, vi(M, 0)); { queue<pi> q; for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) { if (A[i][j] == '#') { W[i][j] = 0; q.push(mp(i, j)); } } while(sz(q)) { auto [r, c] = q.front(); q.pop(); if (vis[r][c]) continue; vis[r][c] = 1; for(int d = 0; d < 4; d++) { int nr = r + dx[d], nc = c + dy[d]; if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue; if (W[nr][nc] > W[r][c] + 1) { W[nr][nc] = W[r][c] + 1; q.push(mp(nr, nc)); } } } } // for(auto x : A) cout << x << nl; // for(auto v : W) { // for(auto x : v) cout << x << " "; // cout << endl; // } pi S, C; for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) { if (A[i][j] == 'S') { A[i][j] = '.'; S = mp(i, j); } if (A[i][j] == 'C') { A[i][j] = '.'; C = mp(i, j); } } V<V<vpi>> port(N, V<vpi>(M)); { pi cur; for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { if (A[i][j] == '#') continue; if (A[i][j-1] == '#') cur = mp(i, j); port[i][j].pb(cur); } } } { pi cur; for(int i = 0; i < N; i++) { for(int j = M - 1; j >= 0; j--) { if (A[i][j] == '#') continue; if (A[i][j+1] == '#') cur = mp(i, j); port[i][j].pb(cur); } } } { pi cur; for(int j = 0; j < M; j++) { for(int i = 0; i < N; i++) { if (A[i][j] == '#') continue; if (A[i-1][j] == '#') cur = mp(i, j); port[i][j].pb(cur); } } } { pi cur; for(int j = 0; j < M; j++) { for(int i = N - 1; i >= 0; i--) { if (A[i][j] == '#') continue; if (A[i+1][j] == '#') cur = mp(i, j); port[i][j].pb(cur); } } } V<vi> D(N, vi(M, MOD)); pq<array<int, 3>> q; q.push({D[S.f][S.s] = 0, S.f, S.s}); while(sz(q)) { auto [d, r, c] = q.top(); q.pop(); if (D[r][c] != d) continue; // cout << r << " " << c << " => " << d << endl; for(int dir = 0; dir < 4; dir++) { int nr = r + dx[dir], nc = c + dy[dir]; if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue; if (D[nr][nc] > D[r][c]+1) q.push({D[nr][nc] = D[r][c]+1, nr, nc}); } for(auto p : port[r][c]) { auto [nr, nc] = p; // cout << nr << ", " << nc << endl; if (D[nr][nc] > D[r][c]+W[r][c]) q.push({D[nr][nc] = D[r][c]+W[r][c], nr, nc}); } } cout << D[C.f][C.s] << nl; exit(0-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...