fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <utility>
  4. #include <string.h>
  5. #include <algorithm>
  6. #include <fstream>
  7.  
  8. using namespace std;
  9. const int dy[4] = {-1, 1, 0, 0};
  10. const int dx[4] = {0, 0, -1, 1};
  11. int checkfire[1001][1001];
  12. int checkperson[1001][1001];
  13. char map[1001][1001];
  14.  
  15. queue<pair<int, int>> fq;
  16. queue<pair<int, int>> pq;
  17.  
  18. int fire(int m, int n)
  19. {
  20.     while(!fq.empty())
  21.     {
  22.         int y = fq.front().first;
  23.         int x = fq.front().second;
  24.         fq.pop();
  25.         if(y == 0 || x == 0 || y == m - 1 || x == n - 1){
  26.             return checkfire[y][x];
  27.         }
  28.         for(int i = 0; i < 4; i++){
  29.             int yy = y + dy[i];
  30.             int xx = x + dx[i];
  31.             if(yy >= 0 && yy < m && xx >= 0 && xx < n){
  32.                 if(map[yy][xx] == '.' && checkfire[yy][xx] == 0){
  33.                     checkfire[yy][xx] = checkfire[y][x] + 1;
  34.                     fq.push(make_pair(yy, xx));
  35.                 }
  36.             }
  37.         }
  38.     }
  39.     return 1e9; // 불이 벽에 도달하지 못하면 큰 값을 반환
  40. }
  41.  
  42. int person( int m, int n)
  43. {
  44.     while(!pq.empty())
  45.     {
  46.         int y = pq.front().first;
  47.         int x = pq.front().second;
  48.         pq.pop();
  49.         if(y == 0 || x == 0 || y == m - 1 || x == n - 1){
  50.             return checkperson[y][x];
  51.         }
  52.         for(int i = 0; i < 4; i++){
  53.             int yy = y + dy[i];
  54.             int xx = x + dx[i];
  55.             if(yy >= 0 && yy < m && xx >= 0 && xx < n){
  56.                 if(map[yy][xx] == '.' && checkperson[yy][xx] == 0){
  57.                     checkperson[yy][xx] = checkperson[y][x] + 1;
  58.                     pq.push(make_pair(yy, xx));
  59.                 }
  60.             }
  61.         }
  62.     }
  63.     return 1e9; // 사람이 도달하지 못하는 경우 큰 값을 반환
  64. }
  65.  
  66. int main(){
  67.     ios_base::sync_with_stdio(false);
  68.     cin.tie(NULL);
  69. #ifdef JH_DEBUG
  70.     static ifstream in( "5427_input.txt");
  71.     cin.rdbuf( in.rdbuf());
  72. #endif
  73.  
  74.     int t;
  75.     cin >> t;
  76.     while(t--){
  77.         int n, m;
  78.         int mf = 1e9, mp = 1e9;
  79.  
  80.         cin >> n >> m;
  81.  
  82.         memset(checkfire, 0, sizeof(checkfire)); // 불이 여러개 있을 경우 초기화
  83.         memset(checkperson, 0, sizeof(checkperson));
  84.         while( !fq.empty()) fq.pop();
  85.         while( !pq.empty()) pq.pop();
  86.  
  87.         for(int i = 0; i < m; i++){
  88.             for(int j = 0; j < n; j++){
  89.                 cin >> map[i][j];
  90.                 if (map[i][j] == '*')
  91.                 {
  92.                     fq.push(make_pair(i, j));
  93.                     checkfire[i][j] = 1;
  94.                 }
  95.                 else if (map[i][j] == '@')
  96.                 {
  97.                     pq.push(make_pair(i, j));
  98.                     checkperson[i][j] = 1;
  99.  
  100.                 }
  101.             }
  102.         }
  103.  
  104.         mf = fire(m, n);
  105.         mp = person(m, n);
  106.  
  107.         if(mf <= mp)
  108.             if(mf == 1 && mp == 1){ // 불과 사람이 벽에서 시작한 경우 예외처리
  109.                 cout << mp << '\n';
  110.             }else{
  111.                 cout << "IMPOSSIBLE" << '\n';
  112.             }
  113.         else
  114.             cout << mp << '\n';
  115.     }
  116. }
Success #stdin #stdout 0s 24048KB
comments (?)
stdin
copy 
1
100 100
##################################################.#################################################
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#..................................................................................................#
#*************************************************@************************************************#
####################################################################################################
stdout
copy 
99
https://ideone.com/VtPkbj
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!