글 읽기 - 재귀 DP로 짜면 왜 안되나요??

yqkrdudtjr 8년 전 0

처음에 DP로 짰는데 안되길래 BFS로 똑같이 짜서 맞았습니다가 떴습니다

왜 똑같은 조건을 주고 짰는데 DP로 하면 안되나요??

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
int N, M;
char arr[1005][1005];
int cache[1005][1005][3];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
#define inf 987654321
#define min(x, y) x<y ? x:y
int search(int x, int y, int block)
{
	if (x == N - 1 && y == M - 1)
		return 0;
	int &ret = cache[x][y][block];
	if (ret != -1)
		return ret;
	ret = inf;
	for (int i = 0; i < 4; i++)
	{
		int Dx = x + dx[i];
		int Dy = y + dy[i];
		if (Dx < 0 || Dy < 0 || Dx >= N || Dy >= M)
			continue;
		if (block == 0 && arr[Dx][Dy] == '1')
			ret = min(ret, search(Dx, Dy, 1)+1);
		if (arr[Dx][Dy] == '0')
			ret = min(ret , search(Dx, Dy, block)+1);
	}

	return ret;
}

int main(void)
{
	memset(cache, -1, sizeof(cache));
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	int ans = search(0, 0, 0);
	//printf("%d", ans);
	if (ans >= inf)
		printf("-1\n");
	else
		printf("%d", ans+1);
	
	return 0;
}

yukariko 8년 전 0

4방향이기때문에 사이클이 생겨 dp의 성질을 만족하지못하기때문인것같습니다.

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

문제

문제

출처

ICPC

재귀 DP로 짜면 왜 안되나요??

yqkrdudtjr 8년 전 0

yukariko 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말