fork download
copy 
  1. #include <stdio.h>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. #define MAX 55
  6. #define INF 987654321
  7.  
  8. int map[MAX][MAX];
  9. int visited1[MAX][MAX];
  10. int visited2[MAX][MAX];
  11. int dcount[MAX][MAX];
  12. int position[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
  13. int R, C;
  14. int result = INF;
  15. int target_x, target_y;
  16.  
  17. queue<pair<pair<int, int>, int>>q;
  18.  
  19. void bfs()
  20. {
  21.     int i;
  22.     int dx, dy, dq, dw, dop;
  23.     while (q.size())
  24.     {
  25.         dx = q.front().first.first;
  26.         dy = q.front().first.second;
  27.         dop = q.front().second;
  28.         q.pop();
  29.  
  30.         if (dx == target_x && dy == target_y)
  31.         {
  32.             result = dcount[dx][dy];
  33.             return;
  34.         }
  35.         for (i = 0; i < 4; i++)
  36.         {
  37.             dq = dx + position[i][0];
  38.             dw = dy + position[i][1];
  39.  
  40.             if (dq < 0 || dw < 0 || dq >= R || dw >= C)
  41.             {
  42.                 continue;
  43.             }
  44.  
  45.             if (dop == 0)
  46.             {
  47.                 if (map[dq][dw] == 'X' || map[dq][dw] == 'D')
  48.                 {
  49.                     continue;
  50.                 }
  51.                 if (visited1[dq][dw])
  52.                 {
  53.                     visited1[dq][dw] = 0;
  54.                     map[dq][dw] = '*';
  55.                     q.push({ { dq, dw }, dop });
  56.                 }
  57.             }
  58.             if (dop == 1)
  59.             {
  60.                 if (map[dq][dw] == '*' || map[dq][dw] == 'X')
  61.                 {
  62.                     continue;
  63.                 }
  64.                 if (visited2[dq][dw] && (map[dq][dw] == '.' || map[dq][dw] == 'D'))
  65.                 {
  66.                     dcount[dq][dw] = dcount[dx][dy] + 1;
  67.                     visited2[dq][dw] = 0;
  68.                     q.push({ { dq, dw }, dop });
  69.                 }
  70.             }
  71.  
  72.         }
  73.     }
  74. }
  75.  
  76. int main()
  77. {
  78.     //freopen("input.txt", "r", stdin);
  79.  
  80.     scanf("%d %d", &R, &C);
  81.  
  82.     int i, j;
  83.  
  84.     for (i = 0; i < R; i++)
  85.     {
  86.         for (j = 0; j < C; j++)
  87.         {
  88.             scanf(" %1c", &map[i][j]);
  89.             visited1[i][j] = 1;
  90.             visited2[i][j] = 1;
  91.             if (map[i][j] == '*')
  92.             {
  93.                 q.push({ { i, j }, 0 });
  94.                 visited1[i][j] = 0;
  95.             }
  96.             if (map[i][j] == 'S')
  97.             {
  98.                 q.push({ { i, j }, 1 });
  99.                 visited2[i][j] = 0;
  100.             }
  101.             if (map[i][j] == 'D')
  102.             {
  103.                 target_x = i;
  104.                 target_y = j;
  105.             }
  106.         }
  107.     }
  108.  
  109.     bfs();
  110.  
  111.     if (result == INF)
  112.     {
  113.         printf("KAKTUS");
  114.     }
  115.     else
  116.     {
  117.         printf("%d", result);
  118.     }
  119.     return 0;
  120. }
Success #stdin #stdout 0s 5348KB
comments (?)
stdin
copy 
3 3
S.*
...
XDX
stdout
copy 
3
https://ideone.com/mGCCwV
language:
C++14 (gcc 8.3)
created:
2 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!