[COCI] 백준 3055 - 탈출

[COCI] 백준 3055 - 탈출

#pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; using pii = pair; int r, c; string forest[50]; bool visited[50][50]; bool water[50][50]; queue flood; int finr, finc; bool fin; void solve() { cin >> r >> c; queue> q; for (int i = 0; i < r; ++i) { cin >> forest[i]; } for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { if (forest[i][j] == 'D') { finr = i, finc = j; } if (forest[i][j] == 'X') { visited[i][j] = water[i][j] = 1; } if (forest[i][j] == '*') { flood.push({i, j}); visited[i][j] = water[i][j] = 1; } if (forest[i][j] == 'S') { q.push({i, j, 0}); } } } int turn = 250; int ans = -1; while (turn--) { if (fin) break; queue> nxtq; while (q.size()) { auto cur = q.front(); q.pop(); if (visited[cur[0]][cur[1]] || water[cur[0]][cur[1]]) continue; visited[cur[0]][cur[1]] = true; for (int i = 0; i < 4; ++i) { int nr = cur[0] + ("2213"[i] - '2'); int nc = cur[1] + ("1322"[i] - '2'); if (nr < 0 || nc < 0 || nr >= r || nc >= c || visited[nr][nc] || water[nr][nc]) continue; if (nr == finr && nc == finc) { fin = true; ans = cur[2] + 1; break; } nxtq.push({nr, nc, cur[2] + 1}); } } q = nxtq; queue next_flood; while (flood.size()) { auto cur = flood.front(); flood.pop(); for (int i = 0; i < 4; ++i) { int nr = cur.first + ("2213"[i] - '2'); int nc = cur.second + ("1322"[i] - '2'); if (nr < 0 || nc < 0 || nr >= r || nc >= c || water[nr][nc] || (finr == nr && finc == nc)) continue; water[nr][nc] = 1; next_flood.push({nr, nc}); } } flood = next_flood; } if (ans != -1) cout << ans; else cout << "KAKTUS"; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); }

from http://nicotina04.tistory.com/176 by ccl(A) rewrite - 2021-10-26 03:01:02