5427 불

5427 불

처음에는 1초마다에 대한 시뮬레이션으로 풀려고했는데, 코드를 너무 어렵게 짜기도 했고, 시간초과가 났다. 그래서 그다음 생각해본게 다음 설명하는 방법이다.

코드는 테스트케이스 하나당 bfs 두번으로 끝낸다.

burn 함수와, bfs 함수는 종료조건, 출력조건의 차이랑 탐색조건이 아주살짝 다르다는거 말고는 동일하다.

1. 불이 퍼지는 시간을 d 배열에 기록한다.

2. 시작점으로부터 더 먼저 도착할 수 있으면서 출구까지 갈 수 있으면 그때까지의 시간 출력

3. 도착할 수 없으면 "IMPOSSIBLE" 출력

#include <iostream>
#include <vector>
#include <queue>
#define P pair<int,int>
using namespace std;
 
char buf[1001];
int t, n, m, sx, sy;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int map[1000][1000];
int d[1000][1000];
 
//불 번지기
void burn(int a,int b) {
    queue<P> q;
    q.push(P(a, b));
    d[a][b] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int ax = x + dx[i];
            int ay = y + dy[i];
            if (ax >= 0 && ay >= 0 && ax < n&&ay < m) {
                if (map[ax][ay] == '.' || map[ax][ay] == '@') {
                    if (d[ax][ay] == 0 || d[ax][ay] > d[x][y] + 1) {
                        d[ax][ay] = d[x][y] + 1;
                        q.push(P(ax, ay));
                    }
                }
            }
        }
    }
}
 
// 출구찾기
void bfs(int a, int b) {
    queue<P> q;
    q.push(P(a, b));
    d[a][b] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        if (x == 0 || y == 0 || x == n - 1 || y == m - 1) {
            printf("%d\n", d[x][y]);
            return;
        }
        
        for (int i = 0; i < 4; i++) {
            int ax = x + dx[i];
            int ay = y + dy[i];
            if (ax >= 0 && ay >= 0 && ax < n&&ay < m) {
                if (map[ax][ay] == '.') {
                    if (d[ax][ay] == 0 || d[ax][ay] > d[x][y] + 1) {
                        d[ax][ay] = d[x][y] + 1;
                        q.push(P(ax, ay));
                    }
                }
            }
        }
    }
    printf("IMPOSSIBLE\n");
}
 
int main() {
    scanf("%d", &t);
    for (int tc = 1; tc <= t; tc++) {
        scanf("%d%d", &m, &n);
        vector<P> fire;
 
        for (int i = 0; i < n; i++) {
            scanf("%s", &buf);
            for (int j = 0; j < m; j++) {
                map[i][j] = buf[j];
                d[i][j] = 0;
                if (map[i][j] == '*') fire.push_back(P(i, j));
                if (map[i][j] == '@') {
                    sx = i;
                    sy = j;
                }
            }
        }
 
        for (P p : fire) {
            burn(p.first, p.second);
        }
 
        bfs(sx, sy);
    }
}