#include #include #include #include #include #include using namespace std; const int maxCount = 1001; int r, c; char arr[maxCount][maxCount]; int visit[maxCount][maxCount]; int visitFire[maxCount][maxCount]; int resultValue = 0; vector> startFire; int startY = 0, startX = 0; int dy[4] = {-1, 0, 1, 0}; int dx[4] = {0, 1, 0, -1}; void BFSFire() { if (startFire.empty()) { return; } queue > q; for (int i = 0; i < startFire.size(); i++) { q.push(make_pair(startFire[i].first, startFire[i].second)); } while (!q.empty()) { int y = q.front().first; int x = q.front().second; for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if ( ny < 0 || ny >= r || nx < 0 || nx >= c ) { continue; } if (visitFire[ny][nx] == 0 && arr[ny][nx] != '#') { visitFire[ny][nx] += visitFire[y][x] + 1; q.push(make_pair(ny, nx)); } } q.pop(); } } bool DFSMove(int y, int x, int depth = 1) { bool result = false; for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if ( ny < 0 || ny >= r || nx < 0 || nx >= c) { resultValue = depth; return true; } if (arr[ny][nx] == '#') { continue; } if (visit[ny][nx] > visitFire[y][x] + 1 && (visitFire[ny][nx] > depth + 1 || visitFire[ny][nx] == 0)) { visit[ny][nx] = visitFire[y][x] + 1; result = DFSMove(ny, nx, depth + 1); } } return result; } int main() { cin >> r >> c; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cin >> arr[i][j]; if (arr[i][j] == 'F') { startFire.push_back(make_pair(i, j)); visitFire[i][j] = 1; } else if (arr[i][j] == 'J') { startY = i; startX = j; } } } BFSFire(); visit[startY][startX] = true; if (DFSMove(startY, startX)) { cout << resultValue; } else { cout << "IMPOSSIBLE"; } return 0; }

제출 #90885

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: