#BOJ 5427ドル
火.
尚根は空空間と壁からなる建物に閉じ込められている.建物の一部が火事になり、尚根は出口に向かって走っていた.
毎秒、火は東、西、南、北に隣接する空き地に広がっている.壁に火がつかない.上根は東西南北に隣接する格子に移動でき、1秒かかります.尚根は壁を通ることもできず、移火された部屋や今点火する部屋に移動することもできません.上根のある格子では、火が動くにつれて別の格子に移動できます.
ビルの地図をあげたとき、どれだけ早くビルを脱出できるかを求めるプログラムを作ってください.
入力
最初の行は、テスト例の数を示します.最大100のテストケース.
各テストケースの最初の行は、ビル地図の幅と高さwとhを与える.(1 ≤ w,h ≤ 1000)
次のh行はw文字、ビルの地図を与えます.
".":空白
"#":壁
"@":尚根の開始位置
"*":火
1枚あたりの地図上の@の個数は1つです.
しゅつりょく
各テストボックスは、ビルから脱出する最も速い時間を出力します.ビルから脱出できない場合は「IMPOSIBLE」を出力します.
入力例1
2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
インプリメンテーション
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 256 MB 24021 6068 3859 23.174%
質問する尚根は空空間と壁からなる建物に閉じ込められている.建物の一部が火事になり、尚根は出口に向かって走っていた.
毎秒、火は東、西、南、北に隣接する空き地に広がっている.壁に火がつかない.上根は東西南北に隣接する格子に移動でき、1秒かかります.尚根は壁を通ることもできず、移火された部屋や今点火する部屋に移動することもできません.上根のある格子では、火が動くにつれて別の格子に移動できます.
ビルの地図をあげたとき、どれだけ早くビルを脱出できるかを求めるプログラムを作ってください.
入力
最初の行は、テスト例の数を示します.最大100のテストケース.
各テストケースの最初の行は、ビル地図の幅と高さwとhを与える.(1 ≤ w,h ≤ 1000)
次のh行はw文字、ビルの地図を与えます.
".":空白
"#":壁
"@":尚根の開始位置
"*":火
1枚あたりの地図上の@の個数は1つです.
しゅつりょく
各テストボックスは、ビルから脱出する最も速い時間を出力します.ビルから脱出できない場合は「IMPOSIBLE」を出力します.
入力例1
5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###
サンプル出力12
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
インプリメンテーション
#include <bits/stdc++.h>
using namespace std;
int testcase;
int w, h;
string graph[1000];
int fire_propagate[1002][1002];
int escape_time[1002][1002];
int dx[]{ -1,1,0,0 };
int dy[]{ 0,0,-1,1};
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> testcase;
while (testcase--)
{
cin >> w >> h; //너비와 높이 입력받음
for (int i = 0; i < h; i++)
{
fill(fire_propagate[i], fire_propagate[i] + w, -1);
fill(escape_time[i], escape_time[i] + w, -1);
}
for (int i = 0; i < h; i++)
{
cin >> graph[i];
}
queue<pair<int, int>> fire_Q;
queue<pair<int, int>> escape_Q;
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
if (graph[i][j] == '*') { fire_Q.push({ i,j }); fire_propagate[i][j] = 0; }
if (graph[i][j] == '@') { escape_Q.push({ i,j }); escape_time[i][j] = 0; }
// 불(*) 위치를 큐에 넣고 방문처리
// 사람위치를 큐에 넣고 방문처리
}
}
// 1st bfs : 불 전파
while (!fire_Q.empty())
{
auto cur = fire_Q.front(); fire_Q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue; // 다음이동위치가 맵 밖이면 방문안할거임
if (graph[nx][ny] == '#' || fire_propagate[nx][ny] >= 0) continue;
fire_Q.push({ nx,ny });
fire_propagate[nx][ny] = fire_propagate[cur.first][cur.second] + 1;
}
}
//2st bfs : 사람 탈출
bool isesacpe = false;
while ((!escape_Q.empty())&&(!isesacpe))
{
auto cur = escape_Q.front(); escape_Q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (nx < 0 || nx >= h || ny < 0 || ny >= w)
{
// 맵 밖으로 나가면 탈출 성공인거지.
cout << escape_time[cur.first][cur.second] + 1<< '\n';
isesacpe = true;
break;
}
if (graph[nx][ny] == '#' || escape_time[nx][ny] >= 0) continue;
if (fire_propagate[nx][ny]!=-1 && fire_propagate[nx][ny] <= escape_time[cur.first][cur.second]+1) continue;
escape_Q.push({ nx,ny });
escape_time[nx][ny] = escape_time[cur.first][cur.second] + 1;
}
}
if(!isesacpe)cout << "IMPOSSIBLE\n";
}
return 0;
}
Reference
この問題について(#BOJ 5427ドル), 我々は、より多くの情報をここで見つけました https://velog.io/@versatile0010/BOJ-5427-불テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol