#include using namespace std; char a[1004][1004]; int visited[1004][1004]; vector> fires; int dy[] = {-1, 0, 1, 0}; int dx[] = {0, 1, 0, -1}; int n, m; void print_visited() { cout << "--------\n"; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cout << visited[i][j] << " "; } cout << "\n"; } } void print_a() { cout << "--------\n"; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cout << a[i][j] << " "; } cout << "\n"; } } void spread_out() { int size = fires.size(); for (int f = 0; f < size; ++f) { for (int i = 0; i < 4; i++) { int ny = dy[i] + fires[f].first; int nx = dx[i] + fires[f].second; if (nx < 0 || ny < 0 || ny >= n || nx >= m) { continue; } if (a[ny][nx] != '.' || visited[ny][nx]) { continue; } a[ny][nx] = 'F'; fires.push_back({ny, nx}); } } } void bfs(int y, int x) { visited[y][x] == 1; queue> q; q.push({y, x}); while (q.size()) { tie(y, x) = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int ny = dy[i] + y; int nx = dx[i] + x; if (nx < 0 || ny < 0 || ny >= n || nx >= m) { continue; } if (visited[ny][nx]) { continue; } if (a[ny][nx] != '.') { continue; } // print_a(); visited[ny][nx] = visited[y][x] + 1; spread_out(); // print_visited(); // print_a(); q.push({ny, nx}); } } return; } bool is_exit(int y, int x) { if (y == 0 || x == 0 || y == n - 1 || x == m - 1) { return true; } return false; } int main() { cin >> n >> m; int j_y; int j_x; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; if (a[i][j] == 'J') { j_y = i; j_x = j; } else if (a[i][j] == 'F') { fires.push_back({i, j}); } } } if (is_exit(j_y, j_x)) { cout << 1; return 0; } bfs(j_y, j_x); int ret = 1000; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (visited[i][j] && is_exit(i, j)) { ret = min(ret, visited[i][j]); } } } if (ret == 1000) { cout << "IMPOSSIBLE" << "\n"; } else { cout << ret + 1 << "\n"; } return 0; }

제출 #52948

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: