글 읽기 - 재귀 DP로는 불가능하나요?

kwakmeensoo 5년 전 0

벽 부수고 이동하기 예전에 BFS로 풀었었는데, 메모이제이션 DP로 다시 풀어보려 하니까 계속 오답뜨네요.

다른 분들이 올린 테케도 다 제대로 뜨고, 틀린 곳 없는 것 같은데... 메모이제이션 DP로는 불가능 한가요?

#include <cstdio>
#include <algorithm>
using namespace std;

const int END_POINT_SCORE = 1;
const int IMPOSSIBLE = 987654321;

int N, M, Ex, Ey, Sx, Sy;
int Dp[1010][1010][2];
bool Maze[1010][1010];

int dirx[] = { 0, 0, 1, -1};
int diry[] = { 1, -1, 0, 0};

void initializing();
int go(int, int, int);

int main() {
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= M; ++j) scanf("%1d", &Maze[i][j]);
    }
    initializing();

    if(N == 1 && M == 1) {
        printf("-1");
        return 0;
    }

    int flag = go(1, 1, 0);
    printf("%d", flag != IMPOSSIBLE ? flag : -1);
}

int go(int i, int j, int k) {
    if(i == Ex && j == Ey) return END_POINT_SCORE;

    int &ret = Dp[i][j][k];
    if(ret != -1) return ret;
    ret = IMPOSSIBLE;

    for(int d = 0; d < 4; ++d) {
        int nx = dirx[d] + i;
        int ny = diry[d] + j;
        if(nx < 1 || ny < 1 || nx > N || ny > M) continue;
        if(Maze[nx][ny] && !k) ret = min(ret, go(nx, ny, 1) + 1);
        if(Maze[nx][ny] ==  0) ret = min(ret, go(nx, ny, k) + 1);
    }

    return ret;
}

void initializing() {
    Ex = N;
    Ey = M;
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= M; ++j) {
            Dp[i][j][0] = Dp[i][j][1] = -1;
        }
    }
}

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

문제

문제

출처

ICPC

재귀 DP로는 불가능하나요?

kwakmeensoo 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말