글 읽기 - dp로 푸는게맞나여?ㅠㅠ

uk7880 7년 전 0

solve 부분이 뭔가 틀린것같은데 뭐가 틀렸는지모르겠어여...

예외 테케나 틀린부분좀 지적해주세요 ㅠㅠ

#ifdef _DEBUG
#include "bits_stdc++.h"
#else
#include "bits/stdc++.h"
#endif
#pragma warning(disable:4996)
using namespace std;

int n, m,k,x,y,ans=99999999;
bool range(int x, int y) { 
	if (x<0 || y<0 || x>n - 1 || y>m - 1) return false;
	return true;
}
vector<pair<int, int> > xy;
int arr[1001][1001];
int dp[1001][1001];

int solve(int x,int y) {
	if (x == n - 1) return 0;
	int &ret = dp[x][y];
	if (ret != -1) return ret;

	ret = 100000000;
	for (int i = 0; i < k; i++) {
		int nx = x + xy[i].first;
		int ny = y + xy[i].second;
		if(range(nx,ny) && arr[nx][ny])
			ret = min(ret,solve(nx, ny)+1);
	}

	return ret;
}

int main() {
	memset(dp, -1, sizeof dp);
	scanf("%d %d", &n, &m);

	for(int i=0;i<n;i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &arr[i][j]);

	scanf("%d", &k);
	for (int i = 0; i < k;i++) {
		scanf("%d %d", &x, &y);
		xy.push_back({ x,y });
	}

	for (int i = 0; i < m; i++)
		if (arr[0][i])
			ans = min(ans, solve(0,i));

	printf("%d\n", ans == 99999999 ? -1 : ans);
}

haja 7년 전 0

BFS로 풀어야 할 것 같아요

uk7880 7년 전 0

BFS로 풀긴했는데 저거는 왜안되는걸까요ㅠㅠ 쮸륵

haja 7년 전 2

부분문제의 의존관계에 사이클이 생겨요

solve를 호출했을때 값이 이미 들어있어서 바로 반환한 값이 최적해가 아닐 수 있어요.

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

문제

문제

출처

ICPC

dp로 푸는게맞나여?ㅠㅠ

uk7880 7년 전 0

haja 7년 전 0

uk7880 7년 전 0

haja 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말