#include #include #include struct GraphType{ bool Value; bool IsVisited; }; struct PosType{ int X, Y; }; struct BufferType{ bool Type; int X, Y; int Depth; }; int bfs(std::vector>&, std::vector&, struct PosType); int main(int argc, char* argv[]){ int N, M; scanf("%d %d\n", &M, &N); std::vector> graph(N, std::vector(M, {0, false})); struct PosType start; std::vector fireList; for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++){ char temp; scanf("%c", &temp); if(temp == '#'){ graph[i][j].Value = true; continue; } graph[i][j].Value = false; if(temp == '.'){ continue; } if(temp == 'F'){ fireList.push_back({i, j}); continue; } if(temp == 'J'){ start = {i, j}; } } scanf("\n"); } int result = bfs(graph, fireList, start); if(result == -1){ printf("IMPOSSIBLE\n"); return 0; } printf("%d\n", result); return 0; } int bfs(std::vector>& graph, std::vector& fireList, struct PosType start){ int N = graph.size(), M = graph[0].size(); std::queue buffer; for(struct PosType s : fireList){ buffer.push({true, s.X, s.Y, 0}); } buffer.push({false, start.X, start.Y, 0}); while(!buffer.empty()){ struct BufferType current = buffer.front(); buffer.pop(); if(current.X < 0 || current.Y < 0 || current.X >= N || current.Y >= M){ if(!current.Type){ return current.Depth; } continue; } if(graph[current.X][current.Y].Value){ continue; } if(current.Type){ graph[current.X][current.Y].Value = true; buffer.push({true, current.X+1, current.Y, 0}); buffer.push({true, current.X-1, current.Y, 0}); buffer.push({true, current.X, current.Y+1, 0}); buffer.push({true, current.X, current.Y-1, 0}); continue; } if(graph[current.X][current.Y].IsVisited){ continue; } graph[current.X][current.Y].IsVisited = true; buffer.push({false, current.X+1, current.Y, current.Depth+1}); buffer.push({false, current.X-1, current.Y, current.Depth+1}); buffer.push({false, current.X, current.Y+1, current.Depth+1}); buffer.push({false, current.X, current.Y-1, current.Depth+1}); } return -1; }

제출 #26414

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: