백준 16933번 벽 부수고 이동하기3 모르겠어요 ㅜㅜ

게시물 수정 , 삭제는 로그인 필요

예제 입력과 게시판 반례 모두 통과하는 것 같은데 제출하자마자 틀렸다고 나오네요 ㅜㅜㅜ
어디가 잘못된지 모르겠습니다ㅜㅜ 반례 혹은 틀린 부분 알려주시면 정말 감사하겠습니다!

#include <iostream>

#include <algorithm>

#include <queue>

#define MAX 1001

#define K_MAX 11

#define INF 987654321

class Pos {

public:

int r;

int c;

int k;

int day;

Pos() :r(-1), c(-1), k(-1), day(1) {}

Pos(int r, int c, int k, int day) :r(r), c(c), k(k), day(day) {}

};

int N = 0, M = 0, K = 0;

int dr[4] = { -1, 0, +1, 0 };

int dc[4] = { 0, -1, 0, +1 };

char graph[MAX][MAX];

int dp[MAX][MAX][K_MAX][2];  // [r][c][k][day]

int bfs(int startR, int startC) {

int ans = INF;

std::queue<Pos> q;

q.push(Pos(startR, startC, 0, 1));

dp[startR][startC][0][1] = 1;

while (!q.empty()) {

Pos x = q.front();

q.pop();

if (x.r == N && x.c == M) {

ans = std::min(ans, dp[x.r][x.c][x.k][x.day]);

}

else {

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

int nextR = x.r + dr[i];

int nextC = x.c + dc[i];

int nextD = (x.day + 1) % 2;

if (1 <= nextR && nextR <= N && 1 <= nextC && nextC <= M) {

// 빈 칸이면

if (graph[nextR][nextC] == '0') {

// 방문 x

if (dp[nextR][nextC][x.k][nextD] == 0) {

q.push(Pos(nextR, nextC, x.k, nextD));

dp[nextR][nextC][x.k][nextD] = dp[x.r][x.c][x.k][x.day] + 1;

}

}

else if (graph[nextR][nextC] == '1') {

// 벽이면

// 부술 수 있고 

if ((x.k < K)) {

// 현재가 낮이면.

if (x.day == 1) {

// 방문 x이면

if (dp[nextR][nextC][x.k + 1][nextD] == 0) {

q.push(Pos(nextR, nextC, x.k + 1, nextD));

dp[nextR][nextC][x.k + 1][nextD] = dp[x.r][x.c][x.k][x.day] + 1;

}

}

else {

// 밤이면

// 방문 x면

if (dp[nextR][nextC][x.k + 1][x.day] == 0) {

q.push(Pos(nextR, nextC, x.k + 1, x.day));

dp[nextR][nextC][x.k + 1][x.day] = dp[x.r][x.c][x.k][x.day] + 2;

}

}

}

}

}

}

}

}

if (ans == INF) { ans = -1; }

return ans;

}

int main() {

std::cin >> N >> M >> K;

for (int r = 1; r <= N; r++) {

for (int c = 1; c <= M; c++) {

std::cin >> graph[r][c];

}

}

int ans = bfs(1, 1);

std::cout << ans;

return 0;

}