[BOJ] 4179번 : 불!

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std; 

#define X first 
#define Y second 
int rows, cols; 
string board[1005];
int minutes_f[1005][1005];
int minutes_j[1005][1005];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

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

	cin >> rows >> cols; 
	// board 값 채우기 
	for (int i = 0; i < rows; i++) {
		cin >> board[i];
	}
	// minutes 값 채우기 
	for (int i = 0; i < rows; i++) fill(minutes_f[i], minutes_f[i] + cols, -1);
	for (int i = 0; i < rows; i++) fill(minutes_j[i], minutes_j[i] + cols, -1);
	
	// 초기 'F'값을 Queue에 추가  
	queue<pair<int, int>> Q; 
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			if (board[i][j] == 'F') {
				Q.push({ i,j }); 
				minutes_f[i][j] = 0;
			}
		}
	}
	// 불이 번지는 시간을 minutes에 기록 
	while (!Q.empty()) {
		pair<int, int> current_fire = Q.front(); Q.pop(); 
		for (int dir = 0; dir < 4; dir++) {
			int nx = current_fire.X + dx[dir];
			int ny = current_fire.Y + dy[dir]; 
			if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue; 
			if (board[nx][ny] == '#' || minutes_f[nx][ny] >= 0) continue; 
			minutes_f[nx][ny] = 1 + minutes_f[current_fire.X][current_fire.Y]; 
			Q.push({ nx,ny }); 
		}
	}
	// 초기 'J'값을 추가 
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			if (board[i][j] == 'J') {
				if (minutes_f[i][j] == 0) {
					cout << "IMPOSSIBLE" << '\n';
					return 0;
				}
				Q.push({ i,j });
				minutes_j[i][j] = 0;
			}
		}
	}
	// 지훈이가 불보다 빨리 도착하는지 여부 
	while (!Q.empty()) {
		pair<int, int> current_j = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = current_j.X + dx[dir];
			int ny = current_j.Y + dy[dir]; 
			if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) {
				cout << minutes_j[current_j.X][current_j.Y] + 1 << '\n';
				return 0;
			}
			if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue;
			if (board[nx][ny] == '#' || minutes_j[nx][ny] >= 0 || (minutes_f[nx][ny] != -1 && minutes_f[nx][ny] <= minutes_j[current_j.X][current_j.Y] +1)) continue;
			minutes_j[nx][ny] = 1 + minutes_j[current_j.X][current_j.Y]; 
			Q.push({ nx,ny });
		}	
	}
	
	cout << "IMPOSSIBLE" << '\n';
	return 0;
}