[2665] 미로만들기

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

2665번: 미로만들기

맵이 작으므로 종료상태일때 바로 return하지 않도록 구현해도 된다.

마냥 방문만 할수 없으므로, [행][열][벽을 지난 회수]로 방문처리해주었다.

위 방법은 입력이 충분히 작기에 가능하다. 실제로는 0-1 bfs태그가 달려야할거 같은 문제였다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

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

int n;

char a[555][555];

bool vst[55][55][3000];

typedef struct {

    int y, x, cnt;

} state;

int f(int sy, int sx) {

    queue<state> q;

    q.push({sy, sx, 0});

    vst[sy][sx][0] = true;

    int ans = 54321;

    while (!q.empty()) {

        auto cur = q.front();

        q.pop();

        if (cur.y == n - 1 && cur.x == n - 1) ans = min(cur.cnt, ans);

        for (int i = 0; i < 4; i++) {

            int y = cur.y + dy[i];

            int x = cur.x + dx[i];

            if (y < 0 || x < 0 || y >= n || x >= n) continue;

            int nxt = cur.cnt + (a[y][x] == '0');

            if (vst[y][x][nxt] == false) {

                vst[y][x][nxt] = true;

                q.push({y, x, nxt});

            }

        }

    }

    return ans;

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n;

    int i, j;

    for (i = 0; i < n; i++)

        for (j = 0; j < n; j++) cin >> a[i][j];

    cout << f(0, 0);

    return 0;

}

---