탈출 백준3055, multisourceBfs

문제

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

설명

multisourceBfs의 문제이다 그러나 알아보지 못했다가 틀렸다가 해결

• 문제에서'D'와 'S'는 하나씩만 주어진다.라고 적혀있다. 이점을 보면 물은 하나씩만 주어지라는 '보장'이 없는 것이다. -> 그럼 멀티소스 bfs ㄱㄱ

소스

#include <bits/stdc++.h>

using namespace std;

int r, c, ans;
char grid[100][100];
int Water[100][100];
int visited[100][100];
int Watervisited[100][100];
pair<int, int> startPos, endPos;
vector<pair<int, int>> waterPos;

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };


bool CanGo(int x, int y) {
    if (visited[x][y] != -1 || x < 0 || y < 0 || x >= r || y >= c || grid[x][y] == '*' || grid[x][y] == 'X') return false;

    return true;
}
bool WaterCanGo(int x, int y) {
    if (Watervisited[x][y] != -1 || x < 0 || y < 0 || x >= r || y >= c || grid[x][y] == 'X') return false;

    return true;
}
void WaterBfs() {
    queue<pair<int, int>> q;

    for (int i = 0; i < waterPos.size(); i++)
    {
        //cout << waterPos[i].first << " " << waterPos[i].second << endl;
        q.push({ waterPos[i].first, waterPos[i].second });
        Watervisited[waterPos[i].first][waterPos[i].second] = 0;
    }

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (WaterCanGo(nx, ny)) {
                if (grid[nx][ny] == 'D') continue;
                q.push({ nx, ny });
                Watervisited[nx][ny] = Watervisited[x][y] + 1;
            }
        }
    }
}
int bfs() {
    queue<pair<int, int>> q;
    q.push({ startPos.first, startPos.second });
    visited[startPos.first][startPos.second] = 0;

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if (grid[x][y] == 'D') {
            return visited[x][y];
        }
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (CanGo(nx, ny)) {
                if (Watervisited[nx][ny] > visited[x][y] + 1 || Watervisited[nx][ny] == -1) {
                    visited[nx][ny] = visited[x][y] + 1;
                    q.push({ nx, ny });
                }
            }

        }

    }
    return -1;
}
int main() {

    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> grid[i][j];

            if (grid[i][j] == 'S') {
                startPos = make_pair( i ,j );
            }
            else if (grid[i][j] == 'D') {
                endPos = make_pair(i, j);
            }
            else if (grid[i][j] == '*') {
                waterPos.push_back({ i, j });
            }
        }
    }
    memset(Watervisited, -1, sizeof(Watervisited));
    memset(visited, -1, sizeof(visited));

    WaterBfs();
    ans = bfs();

    if (ans == -1) cout << "KAKTUS";
    else cout << ans;
    return 0;
}