백준 5427 불

큰일이다. 멍청한짓을 하긴했지만 결국 됐네 싶었는데 자꾸만 틀린다. 결국 못고쳤다!!

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using namespace std;

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    int tc;
    cin>>tc;
    for(int idx = 0;idx < tc; idx++)
    {
        cin >>n>>m;
        string table[1002];
        int dist1[1002][1002];
        int dist2[1002][1002];
        //배열들 전부다 -1로 초기화
        for(int j1 = 0; j1< m; j1++)
        {
            fill(dist1[j1], dist1[j1] +n , -1);
            fill(dist2[j1], dist2[j1] +n , -1);
        }
        for(int j2 = 0; j2 < m; j2++)
            cin>> table[j2];
        queue <pair<int,int>> q1;   //사람
        queue <pair<int,int>> q2;   //불
        //불이 퍼지게 되는 시간 테이블 bfs로 일단 완성
        for(int i = 0; i < m; i++)
        {
            
            for(int j = 0; j < n; j++)
            {
                if (table[i][j] == '*')
                {
                    q2.push(make_pair(i, j));
                    dist2[i][j] = 0;
                }
                if (table[i][j] == '@')
                {
                    q1.push(make_pair(i,j));
                    dist1[i][j] = 0;
                }
            }
        }
        while(!q2.empty())
        {
            //cout<<1<<'\n';
            pair<int, int> cur = q2.front();
            q2.pop();
            for(int dir = 0; dir < 4; dir++)
            {
                int nx = cur.first + dx[dir];
                int ny = cur.second + dy[dir];
                if (nx < 0 || nx >= m || ny< 0 || ny >=n) continue;
                if (dist2[nx][ny] >= 0 || table[nx][ny] == '#') continue;
                dist2[nx][ny] = dist2[cur.first][cur.second] + 1;
                q2.push(make_pair(nx,ny));
            }
        }
        //상근이가 이동하는 시간 테이블 bfs로 완성
        int flag = 0;
        while (!q1.empty())
        {
            if (flag == 1)
                break;
            pair<int,int> cur = q1.front();
            q1.pop();
            for(int dir = 0; dir< 4; dir++)
            {
                int nx = cur.first + dx[dir];
                int ny = cur.second + dy[dir];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n)
                {
                    cout<< dist1[cur.first][cur.second] + 1<<'\n';
                    flag = 1;
                    continue;
                }
                if (dist1[nx][ny] >= 0 || table[nx][ny] == '#') continue;
                if (dist2[nx][ny] != -1 && dist2[nx][ny] <= dist1[cur.first][cur.second] + 1) continue;
                dist1[nx][ny] = dist1[cur.first][cur.second] + 1;
                q1.push(make_pair(nx,ny));
            }
        }
        if (flag != 1)
            cout<<"IMPOSSIBLE\n";
    }
    // 상근이 조건 (1) 이동하려는 테이블에 시간 넣을 때 (cur +1) 이 시간이 불 bfs 테이블이랑 같거나 크면 continue,
    //(2) 이미 방문한 위치면 continue, 0 > 이거나 n,m < 이면 continue.
    // bfs 방문 표시 꼭 하기.
}

좀 길고 더럽긴 한데 나름 ㄱㅊ았다고 생각했는데 뭐가 문젠지 모르겠다. 언젠가의 내가 해결해주면 좋겠다... 

아이디어는 간단하다. 먼저, 불의 이동시간에 대한 BFS를 먼저 다 실행해 이동할 수 있는 곳에 불이 도달하는 시간을 다 구한다.

이제 상근이란 친구의 이동 시간에 대해 BFS 를 해준다. 평상시랑 똑같이 해주되, 불이 그 지점에 이동한 시간을 비교해 만약 불이 더 빨리 도달했다면 그 경우 더 하지말고 멈춘다. 만약 모서리(경계)에 도달한 상근이가 나오면 바로 그 때의 dest값을 리턴해주면 된다.

많은 테케들을 직접 만들어서 넣어봤는데도 뭐때문인지 못찾았다. 속상하다!