백준 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;
}