[백준 4179] 불!

문제링크 : https://www.acmicpc.net/problem/4179

복기

1. x,y를 바꿔 썼다.
2. outOfBound를 먼저 체크해야 오버플로우가 발생하지 않는다.

문제유형 : brute force search

탐색 전략 : brute force
탐색 방법 : bfs 

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std; 
// 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.
typedef pair<int,int> pp; 
int R,C;
int visited[1004][1004]; 
char cmap[1004][1004]; 
int fmap[1004][1004]; 
int dx[4] = {0,0,1,-1}; 
int dy[4] = {-1,1,0,0};
//pp start; 
queue<pp> q; 
queue<pp> fq; 

bool outOfBound(int y, int x){
    return (y < 0 || x < 0 || y >= R || x >= C );
}

bool isExit(int y, int x){//탈출구 
    return (y == 0 || x == 0 || y == R - 1 || x == C -1); 
}

bool isWall(int y, int x){
    return cmap[y][x] == '#'; 
}

void input(){
    // 초기화 
    fill(&fmap[0][0],&fmap[0][0] + 1004 * 1004 , INT_MAX ); 
    cin >>R>>C;
    for(int i=0;i<R;i++)
    for(int j=0;j<C;j++){
        cin >> cmap[i][j];
        if(cmap[i][j] == 'F'){//fire then 
            fmap[i][j] = 1; 
            fq.push({i,j}); 
        }
        if(cmap[i][j] == 'J'){//출발 지점 
            q.push({i,j});
            visited[i][j] = 1;
        }
    } 
}

//bfs 
int solution(){
    int y,x; 
    int ny,nx; 
    //bfs fire
    while(!fq.empty()){
        tie(y,x) = fq.front(); 
        fq.pop(); 
        for(int i=0; i<4; i++){
            ny = y + dy[i]; 
            nx = x + dx[i]; 
            if( fmap[ny][nx] != INT_MAX ) continue; //visited  
            if(outOfBound(ny,nx)||isWall(ny,nx)) continue; 
            fq.push({ny,nx}); 
            fmap[ny][nx] = fmap[y][x] + 1; 
        } 
    }
    //bfs person 
    while(!q.empty()){
        tie(y,x) = q.front(); 
        q.pop(); 
        if(isExit(y,x)){
            return visited[y][x]; 
        }
        for(int i=0; i<4; i++){
            ny = y + dy[i]; 
            nx = x + dx[i];
            if(outOfBound(ny,nx) || visited[ny][nx] || isWall(ny,nx)) continue; 
            if(fmap[ny][nx] <= visited[y][x] + 1) continue; //이미 불이 있는 지역 
            q.push({ny,nx});
            visited[ny][nx] = visited[y][x] + 1;
        }
    }
    return -1; 
}

//solve
void solve(){
    input(); 
    int result = solution();
    if(result == -1) cout << "IMPOSSIBLE"; 
    else cout << result; 
}

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    solve(); 
}