[백준] 5427. 불(c++)

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

불!의 형제 문제다.

불을 먼저 bfs를 돌린 후, 상근이가 지나갈 때 해당 칸에 불이 지나갔을 때의 value보다 상근이의 valuer가 낮을 때 진행할 수 있는 방식으로 풀었다.

 

---

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <limits.h>
#include <queue>
#include <set>
#include <math.h>
#include <stack>
#include <deque>

using namespace std;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

// int arr[1001][1001] = {0};
// int fire_visited[1001][1001] = {0};
// int visited[1001][1001] = {0};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;

    pair<int, int> fire;
    pair<int, int> sangn;

    int t;

    cin >> t;

    while (t--) {
        cin >> m >> n;
        cin.ignore();

        int ans = 99999999;
        queue<pair<int, int> > q;
        vector<string> arr_str(n);
        vector<vector<int> > arr(n, vector<int>(m));
        vector<vector<int> > fire_visited(n, vector<int>(m));
        vector<vector<int> > visited(n, vector<int>(m));

        for (int i = 0; i < n; i++) {
            getline(cin, arr_str[i]);
            for (int j = 0; j < m; j++) {
                if (arr_str[i][j] == '#') {
                    arr[i][j] = -1;
                } else if (arr_str[i][j] == '.') {
                    arr[i][j] = 0;
                } else if (arr_str[i][j] == '@') {
                    arr[i][j] = 1;
                    sangn = {i, j};
                } else {
                    arr[i][j] = 2;
                    q.push({i, j});
                    fire_visited[i][j] = 1;
                }
            }
        }

        while (!q.empty()) {
            int y = q.front().first;
            int x = q.front().second;
            q.pop();

            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];

                if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                if (fire_visited[ny][nx] || arr[ny][nx] == -1) continue;

                fire_visited[ny][nx] = fire_visited[y][x] + 1;
                q.push({ny, nx});
            }
        }

        q.push(sangn);
        visited[sangn.first][sangn.second] = 1;

        while (!q.empty()) {
            int y = q.front().first;
            int x = q.front().second;
            q.pop();

            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (ny < 0 || ny >= n || nx < 0 || nx >= m) {
                    ans = min(ans, visited[y][x] + 1);
                    continue;
                }
                if (visited[ny][nx] || arr[ny][nx] == -1 || arr[ny][nx] == 2)
                    continue;
                if (fire_visited[ny][nx] > visited[y][x] + 1 || !fire_visited[ny][nx]) {
                    visited[ny][nx] = visited[y][x] + 1;
                    q.push({ny, nx});
                }
            }
        }

        if (ans != 99999999)
            cout << ans - 1 << '\n';
        else
            cout << "IMPOSSIBLE" << '\n';
    }
    return 0;
}