#include #include char graph[1000][1000]; int dis[1000][1000]; std::string str; int tc, w, h; int dy[4] = { 0,-1,0,1 }; int dx[4] = { -1,0,1,0 }; void print_dis() { for (int i = 0; i < h; i++) { for (int k = 0; k < w; k++) { std::cout << dis[i][k] << " "; } std::cout << "\n"; } } void bfs_s(std::queue>& Queue) { dis[Queue.front().first][Queue.front().second] = 0; //다시 시작 while (!Queue.empty()) { std::pair cur = Queue.front(); Queue.pop(); for (int i = 0; i < 4; i++) { int ny = cur.first + dy[i]; int nx = cur.second + dx[i]; if (ny < 0 || nx < 0 || ny >= h || nx >= w) { //탈출 std::cout << dis[cur.first][cur.second] +1; return; } if (graph[ny][nx] == '#'|| graph[ny][nx] == '*' || graph[ny][nx] == '@') continue; //만약 벽이거나, dis[ny][nx] 가 원래 이동하려던 곳 + 1보다 작거나, 불이면 그냥 pass // 위 식의 오류 -> 만약 dis[ny][nx] 값이 -1이여도 continue된다. //그렇지 않다면 바꾸기 if (dis[ny][nx] > 0) { if (dis[ny][nx] < dis[cur.first][cur.second] + 1) continue; else { dis[ny][nx] = dis[cur.first][cur.second] + 1; Queue.push({ ny,nx }); } } else { dis[ny][nx] = dis[cur.first][cur.second] + 1; Queue.push({ ny,nx }); } } } std::cout << "IMPOSSIBLE"; } void bfs_fire(std::queue>& Queue) { while (!Queue.empty()) { std::pair cur = Queue.front(); Queue.pop(); for (int i = 0; i < 4; i++) { int ny = cur.first + dy[i]; int nx = cur.second + dx[i]; if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue; if (dis[ny][nx] != -1 || graph[ny][nx] == '#') continue; //불 못가는 곳일 경우 continue dis[ny][nx] = dis[cur.first][cur.second] + 1; Queue.push({ ny,nx }); } } } int main(void) { std::ios::sync_with_stdio(0); std::cin.tie(0); std::cin >> tc; for (int i = 0; i < tc; i++) { std::cin >> w >> h; for (int k = 0; k < 100; k++) { //초기화 std::fill(graph[k], graph[k] + 1000, 0); std::fill(dis[k], dis[k] + 1000, -1); } //print_dis(); std::queue> Queue_s; std::queue> Queue_fire; for (int j = 0; j < h; j++) { std::cin >> str; for (int a = 0; a < str.size(); a++) { //graph값 채우기 graph[j][a] = str[a]; if (str[a] == '*') { //불 위치 Queue_fire.push({ j,a }); dis[j][a] = 0; //불난 곳은 0으로 기록 } if (str[a] == '@') { //상근이 위치 Queue_s.push({ j,a }); } } } bfs_fire(Queue_fire); //print_dis(); //std::cout << "\n"; bfs_s(Queue_s); //print_dis(); if (i != tc - 1) std::cout << "\n"; } return 0; }

제출 #26252

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: