bfs 응용문제이다.
"불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. " -> 불이 먼저 이동한다는 말이다.
불을 먼저 이동시킨다음에 상근이가 배열을 벗어날 수 있다면 탈출!
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int t, w, h;
int src_x, src_y;
char arr[1001][1001];
int person_visited[1001][1001];
int drow[4] = {1, -1, 0, 0};
int dcol[4] = {0, 0, 1, -1};
struct st
{
int row, col;
bool fire;
};
queue<st> q;
int BFS(int row, int col);
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
for (int i = 0; i < t; i++)
{
cin >> w >> h;
memset(person_visited, 0, sizeof(person_visited));
for (int j = 0; j < h; j++)
{
string ws;
cin >> ws;
for (int k = 0; k < w; k++)
{
arr[j][k] = ws[k];
if (arr[j][k] == '@')
{
src_x = k;
src_y = j;
}
if (arr[j][k] == '*')
{
q.push({j, k, true});
}
}
}
int result = BFS(src_y, src_x);
if (result == -1)
{
cout << "IMPOSSIBLE\n";
}
else
{
cout << result << "\n";
}
while (!q.empty())
{
q.pop();
}
}
return 0;
}
bool isValid(int row, int col)
{
if (row < 0 || col < 0 || row > h - 1 || col > w - 1)
{
return false;
}
return true;
}
int BFS(int row, int col)
{
q.push({row, col, false});
while (!q.empty())
{
st front = q.front();
q.pop();
if (front.fire)
{
for (int i = 0; i < 4; i++)
{
int next_row = front.row + drow[i];
int next_col = front.col + dcol[i];
if (!isValid(next_row, next_col))
{
continue;
}
if (arr[next_row][next_col] != '#' && arr[next_row][next_col] != '*')
{
arr[next_row][next_col] = '*';
q.push({next_row, next_col, true});
}
}
}
else
{
for (int i = 0; i < 4; i++)
{
int next_row = front.row + drow[i];
int next_col = front.col + dcol[i];
if (!isValid(next_row, next_col))
{
return person_visited[front.row][front.col] + 1;
}
if (arr[next_row][next_col] == '.' &&
person_visited[next_row][next_col] == 0)
{
person_visited[next_row][next_col] = person_visited[front.row][front.col] + 1;
q.push({next_row, next_col, false});
}
}
}
}
return -1;
}
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 4179] 불! (0) | 2020.12.10 |
---|---|
[백준 11967] 불켜기 (0) | 2020.12.10 |
[백준 9466] 텀 프로젝트 (0) | 2020.12.03 |
[백준 2493] 탑 (0) | 2020.11.30 |
[백준 6198] 옥상 정원 꾸미기 (0) | 2020.11.30 |
댓글