백준 소스코드 [C++] 3055 탈출

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

3055번: 탈출

백준 소스코드 [C++] 3055 탈출

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string.h>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#include <cstdlib>
#include <cassert>
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define pli pair<ll, int>
#define make_unique(v) sort(all(v)), v.erase(unique(all(v)), v.end())
typedef long long ll;
using namespace std;

struct dot {
    int y, x;
};
dot D;
string s[52];
bool vis[52][52];
int time = 0;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
bool chk = false;
queue<dot> qs, qw;
void bfs() {
    while (!qs.empty()) {
        time++;
        int SIZE = qw.size();
        for(int j=0;j<SIZE;j++) {
            dot water = qw.front();
            qw.pop();
            for (int i = 0;i < 4;i++) {
                int Y = water.y + dy[i];
                int X = water.x + dx[i];
                if (s[Y][X] == '.') {
                    qw.push({ Y,X });
                    s[Y][X] = '*';
                    vis[Y][X] = true;
                }
            }
        }

        SIZE = qs.size();
        for (int j = 0;j < SIZE;j++) {
            dot gosm = qs.front();
            qs.pop();
         
            for (int i = 0;i < 4;i++) {
                int Y = gosm.y + dy[i];
                int X = gosm.x + dx[i];
                if (s[Y][X] == '.' && vis[Y][X]==false) {
                    qs.push({ Y,X });
                    vis[Y][X] = true;
                }
                else if (s[Y][X] == 'D') {
                    chk = true;
                    return;
                }
            }
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    s[0].resize(m + 2, '#');
    s[n+1].resize(m + 2, '#');
    for (int i = 1;i <= n;i++) {
        cin >> s[i];
        s[i] = "#" + s[i] + "#";
        for (int j = 1;j <= m;j++) {
            if (s[i][j] == 'D') D = { i,j };
            else if (s[i][j] == 'S') {
                qs.push({ i,j });
                vis[i][j] = true;
            }
            else if (s[i][j] == '*') {
                qw.push({ i,j });
                vis[i][j] = true;
            }
        }
    }
    bfs();
    if (chk == true)
        cout << time;
    else cout << "KAKTUS";
    return 0;
}