글 읽기 - 미로 탈출 문제 질문드립니다.

kwakmeensoo 6년 전 1

이 문제를 Dp로 풀었는데, 자꾸 틀리네요.

게시판에 있는 예제는 모두 잘 나옵니다.

비슷한 문제인 벽 부수고 이동하기 또한, Dp로는 틀리고 BFS로 해야 맞는데, 이유를 모르겠습니다 ㅠㅠ

이와 비슷한 유형은 Dp로 해결이 불가능 한가요?

벽 부수고 이동하기 게시판을 보니 yukariko님이 해주신 답글에는 Dp로 풀면 안된다고 하셨는데, 이유를 잘 모르겠습니다.

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define INF 987654321
using namespace std;
int dirx[] = { 0, 0, 1, -1};
int diry[] = { 1, -1, 0, 0};
int Dp[1010][1010][2];
bool Map[1010][1010];
int N, M, Hx, Hy, Ex, Ey;
int f(int i, int j, int k) {
    if(i < 1 || j < 1 || i > N || j > M) return INF;
    if(i == Ex && j == Ey) return 0;
    int &ret = Dp[i][j][k];
    if(ret) return ret;
    ret = INF;
    for(int d = 0; d < 4; ++d) {
        int nx = i + dirx[d], ny = j + diry[d];
        if(!Map[nx][ny]) ret = min(ret, f(nx, ny, k) + 1);
        else ret = min(ret, k ? INF : f(nx, ny, 1) + 1);
    }
    return ret;
}
int main() {
    scanf("%d %d", &N, &M);
    scanf("%d %d", &Hx, &Hy);
    scanf("%d %d", &Ex, &Ey);
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= M; ++j) {
            scanf("%d", &Map[i][j]);
        }
    }
    printf("%d", f(Hx, Hy, 0) == INF ? -1 : f(Hx, Hy, 0));
}

jung2381187 6년 전 0

점화식을 써보면 아마 깨닫지 않으실까 합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

미로 탈출 문제 질문드립니다.

kwakmeensoo 6년 전 1

jung2381187 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말