[B3055] - 탈출

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

물을 먼저 시간에 따라 이동시킨 후 고슴도치가가 그 시간내에 목적지에 도달할 수 있는지 확인하는 BFS문제이다.

#include<iostream>
#include<queue>
using namespace std;
char a[51][51];
int d[51][51];
int d2[51][51];
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
int main() {
    int n, m;
    cin >> n>>m;
    int startx, starty;
    int endx, endy;
    queue<pair<int, int>>q;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        for (int j = 0; j < m; ++j) {
            d[i][j] = -1;
            d2[i][j] = -1;
            if (a[i][j] == '*') {
                q.push({ i,j });
                d[i][j] = 0;
            }
            if(a[i][j]=='S'){
                startx = i;
                starty = j;
            }
            else if (a[i][j] == 'D') {
                endx = i;
                endy = j;
            }
        }
    }
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx >= 0 && nx < n&&ny >= 0 && ny < m) {
                if (a[nx][ny] == 'X'||a[nx][ny]=='D')
                    continue;
                if (d[nx][ny] == -1) {
                    d[nx][ny] = d[x][y] + 1;
                    q.push({ nx,ny });
                }
            }
        }
    }
    q.push({ startx,starty });
    d2[startx][starty] = 0;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx == endx && ny == endy) {
                cout << d[x][y] + 1 << '\n';
                return 0;
            }
            if (nx >= 0 && nx < n&&ny >= 0 && ny < m) {
                if (a[nx][ny] == 'X')
                    continue;
                if (d2[nx][ny] != -1)
                    continue;
                if (d2[x][y] + 1 < d[nx][ny])
                {
                    d2[nx][ny] = d2[x][y] + 1;
                    q.push({ nx,ny });
                }
            }
        }
    }
    if (d2[endx][endy] == -1) 
        cout << "KAKTUS" << '\n';
    else
        cout << d2[endx][endy] << '\n';
    
}