[백준 4179] 불!

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

4179번: 불!

#include <cstdio>
#include <queue>
int R, C;
char board[1000 + 2][1000 + 2];

struct _st
{
	int x, y;
	int time;
};

std::queue<_st> Fr;
int fire[1000 + 2][1000 + 2];
std::queue<_st> Jh;
int jihoon[1000 + 2][1000 + 2];

int dir_x[4] = { 0, 0 ,1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };


void input()
{
	scanf("%d %d", &R, &C);

	
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			fire[i][j] = 0x7ffffff;
		}
	}

	for (int i = 0; i < R; i++) {
		scanf("%s", &board[i]);
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 'F') {
				Fr.push({ i, j, 1 });
				fire[i][j] = 1;
			}
			else if (board[i][j] == 'J') {
				Jh.push({ i, j, 1 });
				jihoon[i][j] = 1;
			}
		}
	}
	//debug();
}


void get_fire_time()
{
	while (!Fr.empty()) {
		_st data = Fr.front();
		Fr.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (board[nx][ny] == '#') continue;
			if (fire[nx][ny] <= data.time + 1) continue;
			Fr.push({ nx ,ny, data.time + 1 });
			fire[nx][ny] = fire[data.x][data.y] + 1;
		}
	}
}


int BFS()
{
	while (!Jh.empty()) {
		_st data = Jh.front();
		Jh.pop();

		if (data.x == 0 || data.x == R - 1 || data.y == 0 || data.y == C - 1) return data.time;

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (board[nx][ny] == '#') continue;
			if (jihoon[nx][ny]) continue;
			if (fire[nx][ny] <= data.time + 1) continue;
			Jh.push({ nx ,ny, data.time + 1 });
			jihoon[nx][ny] = jihoon[data.x][data.y] + 1;
		}
	}
	return -1;
}



int main()
{
	input();
	get_fire_time();
	int ans = BFS();
	if (ans == -1) printf("IMPOSSIBLE\n");
	else printf("%d\n", ans);
	return 0;
}

1. 영역 밖으로 나가면 리턴이 아니라 가장자리에 도달하면 리턴해야 한다. 

2. 불이 퍼진 시간과 별개로 지훈이의 방문 체크를 해줘야 한다. 

3. 지훈이가 탈출할 수 없으면 IMPOSSIBLE을 출력해야 한다. 

4. 불이 안날 수 도 있다 (???? 이런거는 말해줘야 하는거 아니냐고)

 

부산 해적한테 조져지고 화풀이하려다가 된통 당해버림..