3055번: 탈출

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


$O(rc)$

물->고슴도치->물->고슴도치->...
순으로 BFS를 돌려 확인한다.

#include<cstdio>
#include<queue>
using namespace std;
const int fx[] = { 1,0,-1,0 }, fy[] = { 0,1,0,-1 };
struct st { int x, y, c; };
int t, w, h, ck[50][50], tx, ty;
char s[50][51];
int main() {
    queue<st> q;
    scanf("%d%d", &h, &w);
    for (int i = 0; i < h; i++) {
        scanf("%s", s[i]);
        for (int j = 0; j<w; j++) if (s[i][j] == '*') ck[i][j] = 1, q.push({ i,j,0 });
        else if (s[i][j] == 'S') tx = i, ty = j;
    }
    ck[tx][ty] = 1; q.push({ tx,ty,1 });
    while (!q.empty()) {
        st p = q.front();
        for (int i = 0; i < 4; i++) {
            tx = p.x + fx[i]; ty = p.y + fy[i];
            if (tx < 0 || ty < 0 || tx == h || ty == w || ck[tx][ty] || s[tx][ty] == 'X') continue;
            if (s[tx][ty] == 'D') {
                if (!p.c) continue;
                printf("%d", ck[p.x][p.y]);
                return 0;
            }
            ck[tx][ty] = ck[p.x][p.y] + 1;
            q.push({ tx,ty,p.c });
        }
        q.pop();
    }
    if (q.empty()) puts("KAKTUS");
    return 0;
}