백준 5427 불

/*

상근이 동서남북 이동 가능, 빈 공간으로만 갈 수 있고 불이 붙어있거나 붙으려는 칸으로 이동 불가, 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

BFS

*/

#include <cstdio>

#include <iostream>

using namespace std;

#define MAX 1010

int T, W, H, fireCnt, humanCnt, timeCnt = 0, fire_start = 0, fire_end = 0, human_start = 0, human_end = 0, ans = 2e9, check = 1;

char arr[MAX][MAX];

int fire_pos[MAX*MAX][2], human_pos[MAX*MAX][2];

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

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

void init()

{

fireCnt = 0, humanCnt = 0, timeCnt = 0, fire_start = 0, fire_end = 0, human_start = 0, human_end = 0, ans = 2e9, check = 1;

for (int i = 0; i < MAX; i++) {

for (int j = 0; j < MAX; j++) {

arr[i][j] = 0;

}

}

for (int i = 0; i < MAX*MAX; i++) {

for (int j = 0; j < 2; j++) {

fire_pos[i][j] = 0;

human_pos[i][j] = 0;

}

}

}

//재귀로 하지 말고 반복으로,, 사람이 탈출하거나 죽으면 종료

void solve() {

while (1) {

++timeCnt; //시간 1초씩 증가

/*

다음 사람으로 넘어갈 때

*/

human_end = humanCnt;

for (int k = human_start; k < human_end; k++) {

int fail_escape = 0;

if (arr[human_pos[k][0]][human_pos[k][1]] == '*') { continue; }

else {

for (int i = 0; i < 4; i++) {

int nextX = human_pos[k][0] + dx[i], nextY = human_pos[k][1] + dy[i];

//벽에 붙어있는 빈 공간, 즉 탈출할 수 있는 공간에 도달하면 종료

if (arr[human_pos[k][0]][human_pos[k][1]] == '@' && (nextX == -1 || nextX == H || nextY == -1 || nextY == W)) {

printf("%d\n", timeCnt);

return;

}

//맵 밖으로 나가는 경우라면 다음 반복으로 넘어간다.

if (nextX < 0 || nextY < 0 || nextX >= H || nextY >= W) {

continue;

}

else {

//빈 공간이면 이동한다

if (arr[nextX][nextY] == '.') {

arr[nextX][nextY] = '@';

++check;

human_pos[humanCnt][0] = nextX; human_pos[humanCnt++][1] = nextY;

}

}

}

}

}

human_start = human_end;

/*

불이 더이상 갈 곳이 없을 때 처리 안됨

*/

fire_end = fireCnt;

for (int k = fire_start; k < fire_end; k++) {

for (int i = 0; i < 4; i++) {

int nextX = fire_pos[k][0] + dx[i], nextY = fire_pos[k][1] + dy[i];

//맵 밖으로 나가는 경우라면 다음 반복으로 넘어간다.

if (nextX < 0 || nextY < 0 || nextX >= H || nextY >= W) {

continue;

}

else {

if (arr[nextX][nextY] == '#' || arr[nextX][nextY] == '*') {

continue;

//벽이거나 불이면 아무것도 하지 않는다.

}

//사람이 탈출하기 전에 불이 출구를 막으면 탈출 실패

else if (arr[nextX][nextY] == '.' && check == 0) {

printf("IMPOSSIBLE\n");

return;

}

//사람이 있거나 빈 공간이면 불을 붙인다.

else if (arr[nextX][nextY] == '.' || arr[nextX][nextY] == '@') {

if (arr[nextX][nextY] == '@') {

check--;

}

arr[nextX][nextY] = '*';

fire_pos[fireCnt][0] = nextX; fire_pos[fireCnt++][1] = nextY;

}

}

}

}

fire_start = fire_end;

//사방이 막혀서 사람이나 불이 입구로 가지 못하여 끝나지 못하는 경우

f (human_start == humanCnt && fire_start == fireCnt) {

if (human_start == humanCnt) {

printf("IMPOSSIBLE\n");

return;

}

}

}

int main()

{

scanf("%d", &T);

for (int tc = 1; tc <= T; tc++) {

scanf("%d %d", &W, &H);

init();

for (int i = 0; i < H; i++) {

for (int j = 0; j < W; j++) {

scanf(" %c", &arr[i][j]);

if (arr[i][j] == '@') {

human_pos[humanCnt][0] = i; human_pos[humanCnt++][1] = j;

}

else if (arr[i][j] == '*') {

fire_pos[fireCnt][0] = i; fire_pos[fireCnt++][1] = j;

}

}

}

if (human_pos[0][0] == 0 || human_pos[0][0] == H - 1 || human_pos[0][1] == 0 || human_pos[0][1] == W - 1) {

printf("1 \n");

}

else { solve(); }

}

return 0;

}