#include using ll = long long int; using ull = unsigned long long int; using ld = long double; using point = std::pair; #define 고속입출력 \ std::ios_base::sync_with_stdio(false); \ std::cin.tie(NULL); \ std::cout.tie(NULL); std::array, 4> dir = {{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}}; class Solver { private: int n, m; std::vector> maze; public: Solver() {} ~Solver() {} void solve() { std::cin >> n >> m; maze.assign(n, std::vector(m)); std::vector> FIREEEEEEE(n, std::vector(m, INT_MAX)); point start; std::vector FIRE; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { std::cin >> maze[i][j]; if (maze[i][j] == 'J') start.first = i, start.second = j; else if (maze[i][j] == 'F') { FIRE.push_back({i, j}); FIREEEEEEE[i][j] = 0; } } } for (auto &f : FIRE) { std::queue> q; q.push({0, f}); std::vector> visited(n, std::vector(m, false)); visited[f.first][f.second] = true; while (!q.empty()) { auto [curDist, curPoint] = q.front(); q.pop(); for (auto &[dx, dy] : dir) { auto nextX = curPoint.first + dx, nextY = curPoint.second + dy; if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && maze[nextX][nextY] == '.' && !visited[nextX][nextY]) { visited[nextX][nextY] = true; q.push({curDist + 1, {nextX, nextY}}); FIREEEEEEE[nextX][nextY] = std::min(curDist + 1, FIREEEEEEE[nextX][nextY]); } } } } std::queue> q; q.push({0, start}); std::vector> distance(n, std::vector(m, -1)); distance[start.first][start.second] = 0; int ans = INT_MAX; while (!q.empty()) { auto [curDist, curPoint] = q.front(); q.pop(); for (auto &[dx, dy] : dir) { auto nextX = curPoint.first + dx, nextY = curPoint.second + dy, nextDist = curDist + 1; if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && maze[nextX][nextY] == '.' && distance[nextX][nextY] == -1 && nextDist < FIREEEEEEE[nextX][nextY]) { distance[nextX][nextY] = curDist + 1; q.push({curDist + 1, {nextX, nextY}}); } if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m) { ans = std::min(ans, nextDist); } } } std::cout << ans; } }; int main() { 고속입출력; Solver solver; solver.solve(); return 0; }

제출 #13786

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: