1261번: 알고스팟

<aside> 💡 이 문제도 미로에 벽이 있냐, 없냐를 간선의 비용으로 따지기 때문에 0-1 bfs 문제에 속한다. 간선의 INFINITY를 의미하는 숫자는 충분히 크게 잡자!

</aside>

2023년 5월 7일

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
#define endl '\\n';

using tp = tuple<int, int, int>;
using pp = pair<int, int>;
using ll = long long;

#define MAX 102
#define INF 9999999
#define WALL '1'
#define SPACE '0'

int N, M, ans;
char G[MAX][MAX];
int visited[MAX][MAX];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

bool isValid(const int &y, const int &x)
{
    return 0 <= x && x < M && 0 <= y && y < N;
}

void solve()
{
    int x = 0, y = 0;

    deque<tp> q;
    visited[y][x] = 1;
    q.push_back({y, x, 0});

    while (!q.empty())
    {
        auto [y, x, acc] = q.front();
        q.pop_front();

        // base case
        if (y == N - 1 && x == M - 1)
        {
            ans = acc;
            return;
        }

        // search
        for (int d = 0; d < 4; d++)
        {
            int nextY = y + dy[d];
            int nextX = x + dx[d];

            // check is valid coordinates
            if (!isValid(nextY, nextX))
            {
                continue;
            }

            int &nextVisited = visited[nextY][nextX];
            if (nextVisited)
            {
                continue;
            }

            nextVisited = 1;
            if (G[nextY][nextX] == SPACE)
            {
                q.push_front({nextY, nextX, acc});
            }
            else
            {
                q.push_back({nextY, nextX, acc + 1});
            }
        }
    }
}

int main()
{
    fastio;
    cin >> M >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> G[i];
    }

    solve();
    cout << ans << endl;

    return 0;