[3055] 탈출

https://www.acmicpc.net/problem/3055

이전의 글 중에서.. 불이라는 문제가 있는데요!!
그 문제랑 완전히 똑같다고 보시면됩니다!!!!!

bfs연습하기 좋을것 같군요!

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
 
#define MAX_SIZE 51
 
using namespace std;
 
typedef struct _data
{
    int x;
    int y;
    int sec;
    bool water;
} data;
 
int r, c;
char map[MAX_SIZE][MAX_SIZE];
bool visit[MAX_SIZE][MAX_SIZE];
int startx, starty;
int endx, endy;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
vector<pair<int, int> > w;
 
//고슴도치 S
//동굴 D
//X는 벽
//*는 물
void input()
{
    scanf("%d %d", &r, &c);
    getchar();
 
    for(int i = 0; i < r; i++)
    {
        for(int j = 0; j < c; j++)
        {
            scanf("%c", &map[i][j]);
 
            if(map[i][j] == 'S')
            {
                startx = i;
                starty = j;
            }
            else if(map[i][j] == 'D')
            {
                endx = i;
                endy = j;
            }
            else if(map[i][j] == '*')
            {
                w.push_back(make_pair(i, j));
            }
        }
        getchar();
    }
}
 
int bfs()
{
    queue<data> q;
    for(int i = 0; i < w.size(); i++) q.push(data{w[i].first, w[i].second, 0, 1});
    q.push(data{startx, starty, 0, 0});
 
    while(!q.empty())
    {
        data pop_data = q.front();
        q.pop();
 
        int x = pop_data.x;
        int y = pop_data.y;
        int t = pop_data.sec;
        bool water = pop_data.water;
 
        if(water == 0 && endx == x && endy == y) return t;
 
        if(!water && visit[x][y] == 1) continue;
        else if(!water && visit[x][y] == 0) visit[x][y] = 1;
 
 
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            if(map[nx][ny] == 'X' || map[nx][ny] == '*') continue;
            if(water && map[nx][ny] == 'D') continue;
            if(water) map[nx][ny] = '*';
            q.push(data{nx, ny, t + 1, water});
        }
    }
 
    return -1;
}
 
int main()
{
    input();
    int ret = bfs();
    if(ret == -1) puts("KAKTUS");
    else printf("%d\n", ret);
 
 
 
    return 0;
}