[17836] 공주님을 구해라!

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

17836번: 공주님을 구해라!

<문제>

visited를 3차원으로 만든뒤 (0, 0)에서 (n-1, m-1)까지 4방향 bfs를 돌리는 문제

단순히 검에 도착하면 memset후 큐 초기화를 진행하면

도착지와 검까지의 거리가 같을때, 검을 먼저 탐색하는 경우가 반례가 되어

검을 구하기 전과 후의 visited를 분리하고 초기화는 진행하지 않아야한다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
bool visited[101][101][2];
int n, m, t, a[101][101], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
typedef struct {
    int y, x, turn;
    bool key;
} state;
queue<state> q;
int main(void) {
    cin >> n >> m >> t;
    int i, j;
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++) cin >> a[i][j];
    q.push({0, 0, 0, 0});
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (cur.turn > t) continue;
        if (cur.y == n - 1 && cur.x == m - 1) {
            cout << cur.turn;
            return 0;
        }
        for (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 >= m) continue;
            if (visited[y][x][cur.key]) continue;
            visited[y][x][cur.key] = 1;
            if (a[y][x] == 0) {
                q.push({y, x, cur.turn + 1, cur.key});
            } else if (a[y][x] == 1 && cur.key == 1) {
                q.push({y, x, cur.turn + 1, cur.key});
            } else if (a[y][x] == 2) {
                q.push({y, x, cur.turn + 1, 1});
            }
        }
    }
    cout << "Fail";
    return 0;
}