[백준 3055] 탈출 (C++)

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
struct data { int y, x; } sp, ep;
queue<struct data> water, escape;
char arr[52][52];
int visited[52][52];
int n, m, x, y, qs;
void bfs() {
   while (!water.empty()) {
      qs = water.size();
 
      for (int i = 0; i < qs; i++) {
         x = water.front().x;
         y = water.front().y;
         water.pop();
 
         for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            if (0 <= nx && nx < m && 0 <= ny && ny < n) {
               if (arr[ny][nx] == '.' && visited[ny][nx] == 0) {
                  water.push({ ny,nx });
                  visited[ny][nx] = visited[y][x] + 1;
               }
            }
         }
      }
   }
 
   while (!escape.empty()) {
      qs = escape.size();
 
      for (int i = 0; i < qs; i++) {
         x = escape.front().x;
         y = escape.front().y;
         escape.pop();
 
         for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            if (0 <= nx && nx < m && 0 <= ny && ny < n) {
               if (arr[ny][nx] == '.' && (visited[ny][nx] > visited[y][x] + 1 || visited[ny][nx] == 0)) {
                  escape.push({ ny,nx });
                  visited[ny][nx] = visited[y][x] + 1;
               }
               else if (arr[ny][nx] == 'D') {
                  visited[ny][nx] = visited[y][x] + 1;
                  return;
               }
            }
         }
      }
   }
 
}
int main(void) {
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
 
   cin >> n >> m;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
         cin >> arr[i][j];
 
         if (arr[i][j] == 'S') {
            sp.y = i; sp.x = j;
            escape.push({ i,j });
         }
         else if (arr[i][j] == 'D') {
            ep.y = i; ep.x = j;
         }
         else if (arr[i][j] == '*') {
            water.push({ i,j });
         }
      }
   }
 
   bfs();
 
   if (visited[ep.y][ep.x] == 0) cout << "KAKTUS";
   else cout << visited[ep.y][ep.x];
 
   return 0;
}

반례는 기본적인 출처는 여기 : https://www.acmicpc.net/board/view/9581

이 외에 게시판에서 반례들 긁어 모았다

----------
5 5
.....
..XXD
...XX
S....
....*
->8
----------
5 5
*****
XX***
.....
S....
....D
->KAKTUS
----------
10 15
........X......
..XXXXX.X.*....
X.....X.X..*...
.X.S..X.X......
D.X...X.XXXXXXX
.X....X........
.X....X.XXXXXXX
.XXXXXX.X......
........X......
XXXXXXXXX...*..
->30
----------
1 50
S................................................D
->49
----------
1 50
S..............XD................................*
->KAKTUS
----------
5 5
*****
XXXXX
*....
S*...
....D
->KAKTUS
----------
3 4
D...
.*..
S...
->KAKTUS
----------
3 3
D..
*..
S*.
->KAKTUS
----------
3 3
DS.
*X.
...
->1
----------
3 3
DS.
.X.
*..
->1
----------
2 10
S........D
*.........
->9
----------
3 5
S....
..D..
....*
->3
----------
5 5
D...*
..XXX
.....
.....
.S...
->5
----------
5 5
*.XS.
..X..
..X..
..X..
..X.D
->5
----------
5 5
*.X..
..X..
..S..
..X..
..X.D
->4
----------
8 8
...*.....
.....***.
.....*.*.
.....DS**
.........
.........
.........
.........
->1
 

+ 대회 테스트 케이스

10 11

D..........

...........

...........

...........

...........

...........

........S..

...........

...........

...........

->14

10 15

........X......

..XXXXX.X.*....

X.....X.X..*...

.X.S..X.X......

D.X...X.XXXXX..

.X....X........

.X....X.XXXXXXX

.XXXXXX.X......

........X......

XXXXXXXXX...*..

->KAKTUS

10 15

........X......

..XXXXX.X.*....

X.....X.X..*...

.X.S..X.X......

D.X...X.XXXXXXX

.X....X........

.X....X.XXXXXXX

.XXXXXX.X......

........X......

XXXXXXXXX...*..

->30

20 30

..............................

..............................

.............XXXXXXXXXXX......

.............X...S.....X......

.............X.XXXXXXX.X......

.....XXXXXXXXX.X.....X.X......

........*......X.*...X.X......

.....XXXXXXXXX.X.....X.X......

.............X.X...*.X.X......

.............XDX.....X.X......

.............X.X.....X.X......

.............X.X.....X.X......

.............X.X..*..X.X......

.............X.X.....X.X......

.............X.X.....X.X......

.............X.XXXXXXX.X......

.............X.........X......

.............XXXXXXXXXXX......

..............................

..............................

->33

50 50

X.X...X.....X..X.X.X....X.X.......XXXX.......X....

....X.........X....X........X...XX...X....X.X.X...

.XXX....X.....XX....XX....XX..X.........X...X.X.X.

.SX.X..........X.X.X.X...XX..X.X......X.X...XX....

.......X....XXXX.X.X.X....X...X..X...X..X...X....X

.........XX.XX..X.X.X........X.....XXX.XX...X.X.X.

..X.X.XX.....X.X.X...X.......XXX.....XX.X...XX.X..

.XX..............XX.X.X.X.X........X...X.XX.X..XX.

X....XX.X...X.X.X.X...X.X.......X..X...X.X..X.....

X.....X......X..XX.X...X........X.X..X.XX...X.X..X

X..X...XX...X..X..X.X....X.X..X....XX....X.XXX...X

..........X...........X.X....XX.X..X...X..........

.XXX.........X....XX..X...X.X..X..X...XX.X.X.X....

X.........X.XXXX....XX..X.X.X.XX.XX...X.........X.

....X....................X......XX..........X.....

......XXX...X.XXX.X....XX..X......XX.X...X.X.XX...

...X......X..X....X..X..X.........XXX....XXXX.....

..X.......X....X........XXX......X.XX...........X.

.X.X..........X...X...X....XX.X....X.X.....XX..XXX

X.XX....X..........XX..XXX..X.X...........X..X.X.X

X.X.XXX.XX.X....X.X.X....X....X..X....X.X..X..X...

.X..XX.X..X..XX.X...X..X.XX.........XX..XX.X..X.X.

.X.X........XX....XX...XX.....X.X...XXXX....X..X.X

.XX...X...X.......X.......X.....X.X..X.....X.XX..X

..XX..XX.......X...X.XX.X..........XXX.XX..XX..X.X

..X.X..X...X........XX.X.X.XX.X.....X.X..XX...XX.X

.X...X..X.....X..X..XX....XX....XX.....X..XX...X..

.X.X..X..X..X.X.X.......X.XX.X..XXX....X...X.X..X.

X..X.........X..X..X.........X.....XXX...X........

...XX..X....X....X..X.X...XX..XXX....XX.X.XXXX.XX.

.X....X.X...XX....X....X.X.....XX....XXX..X....X..

....XX..X.......X..XX.X.........X.......X..X.XX...

X....XX.....XX....X.X.X.XXX.X.X.....X........X....

..X..X..XX.X....XXX.X..X..X.X...XX....X.....XX....

.......XXXXX.X...X.X...XXX.....X.XXX..XX..........

.......X...X.......X.........XX..X.X...XXX..XX....

...XX.......X.X..X..X........X.X.X.X.X....X....X.X

.XX...X........XX..X.X.XX.....XX........X..X....XX

.X.X.....X.X.X..XXX...X...X..........X..XX....X...

...X...XX..X.X..X......X...XX..XX..X..XXXX.X.XXX..

..XX.XX.XXX...X...X........X.X.X....X.XX.....XX...

X.X.X..XX.......X...XX.....X...X.X..X..X...XX.....

...X.X.X...........X.XXX....XX..X.XXX.XXX......X..

...XX.....XX..XX.....X..X.XX.X..X....X.X.X..X....X

X.XX...........X.....XXXX.X.......XX.......D.X....

X..X.X.X........X.............X.X..X.....X...X.X..

...XX..X.XX.....X.X.X....X..X..XX.....XX...X.X....

.....X.X.....XXXXXX...X.X.X.XX..............X.XX.X

.........XX............XXXX.X..X..X..X..X.X......X

......XX..X..XX.....XX.X..XX.....X....X......X..X.

->83

50 50

...SXX...XX...X...XX.XX....X.......X....X.X....*X.

.XX.X..XX.X.X..X.X.X...XX.X.....X....X...X.XX....X

..X..X....X.X.X.X.XX....XX...X..XX....X...XXX...XX

X.....X..XXX.XX..X.X.X........XXX....X.X..XX..X...

X..X.....X......X.......X..X......X.....X.X..X....

......XXX..X..XX.X.......X..X......X.X.XXX.X..X...

...X...XX.X..X.........X..XX..XX.X..X.X....X..X..X

XX.........XX.XXX.XXX...X..X..XXX.XX.X..X...X.X.X.

.....X...X..X.X.X.....X.X.X...XX........XX..X..X..

XXXX..XX..X..X..X..XXX..X...X..X.X...X..XX.XX.X...

......X..X....X.........XX..X..X........X.XX...X.X

X..XX...X........X........XXXX.XX.........X.X.XXX.

.....XXX...X.XXX....X...XX........X...XXXX...X....

.X.XX....XXX...X...X...X.X...XXX...X...X..XX.XX...

...XXX....XXX.....X.X...XX...X.X.XXX.X.XX..X......

.......X..XX.X.X..........X.XX..X..X.XX.XXXX...XX.

X...X.X.X.XXX.X..X.XXX..X...X....X.X..X...X..XX..X

..X..X.XX..X.XXX..X...X..X..X..X.X....X..........X

XX....X.X.X.XX.....X..XXXX.XX..X....X.....X.....X.

.XX.....X.X..X..X.X...X......X....X..X.XX.XX.XX.X.

.....X.........X..X.X...X....XX.X...X..X..XX.XX...

.X........X..XX..X...X....XX.XXX.XX.X..X...X...XXX

...X.X.XX...X......XX.X.XXX..X.X.XX....XXX.X...X..

....X.....XX..XX.X.X...X..X.X....X.....XX.XX..XXX.

....X........XXXXXX.........XX..X....XX.XXXX......

..XX.XXX.X...X.X.X.X..XXXX....X.X.X...XX.X..X..X..

XX..XX.X...X....XX....X.......X..X.X......XXXXX...

XX..XX.XX.X..X...XX....XX.X..X...X.X....X.........

..X.....X...X..X.........X......X...XX.XX...X.....

X.X..XX.X.X.X.XXXX.X...X..X...XX..X.....X.X.XXX...

..X....X.X.X......X..X...XX..X...X.X.XXX.X....XX.X

X.....X.X...XXXXX.....X..XX...X....X...XXX....X...

.XXX...XXXX.X....X...XX.XX..X.X........X...X....X.

..XXX.XX....X.XX.X..X...X.X.X.....X...X....X.XXXXX

.XX...X.X....XXX......X.....X....X.X..X..X....XX.X

XX..XX.X....X...XXX....X..XXX.XXX.X.X....X.X......

XX....X.X....X..X.XX...X..X.X....X..XX...XX...X...

X.X...X...X..X....X.X.........X...X...X....X..X...

.X...X...X.X....X.....XX......XXX..XX.XX.X.....X..

..X.X..XX.X..X..........X.X.XX..X..X.X.XXXX.......

..X...XX.X.X..XX..XXXXX...X........XX...X.X..X..XX

.....X..XXX....X.XX....XX.XX..XX.X....XX.XX..X.XXX

X..X.XX.X.X.......X.X.X..X......X..XX....X.XXX.XXX

X..XXXX.........X..X..X............X.X..X..X...X..

X...XX.XX...X........X....X....X.X...X..XD...X..X.

......X.......XXXX..XXX.....X.X.X.X..........X....

X.....XX.XX.XXX.XX.X.X..X.X.......XXXX.....X...XXX

.X..XX..X.....XX...XX..X.....XX...X..X....X..X..XX

X....XX....XX.....XX.X.XXX....X.......X..X....X..X

X.....XX..XX.X.....XX....X..X..X.X.XX.......X..X..

-> 86

50 50

..................................................

............................................XXXXD.

...............................................XXX

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

................................S.................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..................................................

..............................................*...

..................................................

..................................................

..................................................

->44

50 50

....X.XX.X....XX.X......XX....X..X..XX.X..X...X...

..SXX...X.....X...X...X..XXX...X....XXX.X.....X..X

.X..X......X..XX.X..XXX....X.X...X..X.XX.X..XX....

X.......X.X...XX..X.X.XX....X..X..X..XX.X.......X.

.....X.XX...XX......X.X....XX.X.X...X..XX...XX.X..

.XX..X..X.X.....X.X.X.X....X.XX.......XX.....XX.X.

.X...XXXXXXX...X.....XX..X..X.X...XXX.XX........X.

..X...XXX.X.......X..X....X.....XX....X.X..XX.X...

..X..XXXX.XXX.....XXX.......XXX..X.X.....XX...X...

.X...XX.X..X.X..X....X.X...X.........XX.X.X...XXX.

.X......X...X......X.X.X....XX....XXXXX........XX.

.X....X.XX.XX....X..XXX..X.X.XX......X....XX......

.X..........X..X.X...XX..XX.XX..XX..X...XX.....X..

.XX....X.X....X..X.X.X..XXX.......X........X...X..

...X.X..X...........X.X.X...X.....XXXXX..XX......X

.XX.......X...............XX.X....X.....X.X.......

.XX..........X....XXXX...X..X.X.XXX..XX..X....X.X.

...X.X.X.XXX.X.......XX.X...X..X..XX..........XX.X

XX..XXX.......X...X....X..XX....X...X..XX..X.XX.X.

.X..X....XX.....XX.........X.X.XXX...XX...XXXX.X..

.....X.X....X.X..XX.....X.X.......X.XX...X.X....X.

..X...X....XXXXX.X...XX......XX....XX.X...X......X

.X....X..XX.XX..X....X.X.X..XX.........XX.XXX.....

X..X.X.X.X...X.XXX.........X...X...X...X.X........

....X.X..XXX......XXX...XX.X.X..X..XX.XX.XX..XX..X

.X.XX..X.........XX.XXX...X.X.X....XX.XX..X...X...

..X...X....X...X...X..XX.X.X.....X.X..X.......XX..

...X.XXXX.X..X.X......XX.X.XX...XX.X...X....X..X..

X..X...XXXX....XX.X.XX.XXX......X........X...X....

X..X.......X.....X.XXX......XX....X..X....X..X.X.X

..X..X.....XXX.....X..X..X.X.X...X.XX..X..X....X.X

..X........XXX.XX.XX....X.XXX..XX...X.X...X.X....X

.X..XXX........X......X.X..XX.XX.X.....XXXX.X.....

.X.XX..X.X...XX...XXX...X.......X.X..XX......XXX..

.X.X.X.....X..X...XX.X......XX....XX..X..X.XXXXX..

.X..X....X......X..........X.XXXXX.XX...X.X..X..XX

.X..X.X.X.X...X...X..X..X...XX......XX...X..XXX...

.XX..X......X.X...X..XX..X.X.X..X.XXXXX.XX...X...X

..X.XX.XXX.X....X..XXX.......XX...X..XXXX.X.....X.

X.XXXXX.X...X...XXXX.XXXX..X..XX..XX..............

..X.X.X...X...XX.X.......X....XX.X.X....X.XX...X..

X.X..XXX.X.X....X....X...X.X..X.....X..X...XXXX.X.

..XX.X.XX.....XX.........X.......X.X..XX.X..XXX...

..X..X.XX.XX.X........X...X..X.X.XX...XX....D.X.XX

.X...X...X...X...XX..X....XX...X..X..X.X..XX.XXXXX

....XX...X...X.X.....XXX..XX....X.X.XXX...X...X...

..XXXX....XXX.X..XX........X.X......X.X.....X...XX

.*............X..XX..X.....X.XXXX...X...X......XX.

.XXX..X....X.XXX....X.X.XX.XXX.X....XXX.X.XX.X.XX.

X.X......X....XXX.X.....XXXX.X..XX....XX....XX....

->98

50 50

D.................................................

.XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.XX.............................................X.

...*............................................X.

.XX.............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

.X..............................................X.

SXXXXXXXXXXXXXXXXXXXXXXXX.X.XXXXXXXXXXXXXXXXXXXXX.

..........................X.......................

->152

50 50

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

*********************SD***************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

**************************************************

->1