[5427] 불

https://www.acmicpc.net/problem/5427

5427번: 불

<문제>

"[4179] 불!"이랑 사실상 똑같은 문제다. bfs를 두 개 돌려주면 되는데,

첫 번째에는 불을 기준으로 해당 정점까지의 최단거리를 저장해둔다. 도달하지 못하는 정점은 INF를 넣는다.

두 번째에는 "현재까지의 턴 + 1" < "불의 최단거리"를 만족하는 조건을 추가로 달아 상근이를 이동시켜주면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;
typedef struct {
    int y, x;
} state;
int n, m, jy, jx, dp[1001][1001], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
char a[1001][1001];
bool visited[1001][1001];
int main(void) {
    int i, j, t;
    cin >> t;
    while (t--) {
        cin >> m >> n;
        queue<state> q;
        fill(&dp[0][0], &dp[1000][1000], INF);
        memset(visited, false, sizeof(visited));
        memset(a, 0, sizeof(a));
        for (i = 0; i < n; i++) {
            for (j = 0; j < m; j++) {
                cin >> a[i][j];
                if (a[i][j] == '*') {
                    q.push({i, j});
                    dp[i][j] = 0;
                } else if (a[i][j] == '@') {
                    jy = i;
                    jx = j;
                }
            }
        }
        while (!q.empty()) {
            state cur = q.front();
            q.pop();
            for (i = 0; i < 4; i++) {
                int y = cur.y + dy[i];
                int x = cur.x + dx[i];
                if (y < 0 || x < 0 || y >= n || x >= m) continue;
                if (dp[y][x] == INF && a[y][x] != '#') {
                    dp[y][x] = dp[cur.y][cur.x] + 1;
                    q.push({y, x});
                }
            }
        }
        typedef struct {
            int y, x, turn;
        } st;
        queue<st> Q;
        Q.push({jy, jx, 0});
        visited[jy][jx] = true;
        while (!Q.empty()) {
            st cur = Q.front();
            Q.pop();
            if (cur.y == 0 || cur.y == n - 1 || cur.x == 0 || cur.x == m - 1) {
                cout << cur.turn + 1 << '\n';
                goto end;
            }
            for (i = 0; i < 4; i++) {
                int y = cur.y + dy[i];
                int x = cur.x + dx[i];
                if (y < 0 || x < 0 || y >= n || x >= m) continue;
                if (visited[y][x] == false && a[y][x] != '#' &&
                    dp[y][x] > cur.turn + 1) {
                    Q.push({y, x, cur.turn + 1});
                    visited[y][x] = true;
                }
            }
        }
        cout << "IMPOSSIBLE\n";
    end:;
    }
    return 0;
}