글 읽기 - 예외케이스찾아주세요

tkim0723 7년 전 0

예제는 돌아가지만 틀렸습니다 나오네요.

뭐가문제일까요?

#include <iostream>
using namespace std;
#define INF 1000*1000*100
int n, m;
int map[1002][1002];
int V[1002][1002], D[1002][1002][3];
int dir[3][2] = { { 0, -1 }, { 0, 1 }, { 1, 0 } };

int max(int a, int b)
{
	return a > b ? a : b;
}
int recur(int r,int c,int d)
{
	if (r == n && c == m) return map[r][c];
	int& ret = D[r][c][d];
	if (ret != -INF) return ret;

	for (int k = 0; k < 3; ++k)
	{
		int nr = r + dir[k][0];
		int nc = c + dir[k][1];
		if (nr<1 || nr>n || nc<1 || nc>m)continue;
		if (V[nr][nc] == 0)
		{
			V[nr][nc] = 1;
			ret = max(ret, recur(nr, nc, k) + map[r][c]);
			V[nr][nc] = 0;
		}
	}
	return ret;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
		{
			cin >> map[i][j];
			for (int k = 0; k < 3; ++k)
				D[i][j][k] = -INF;
		}
	cout << recur(1, 1, 0) << endl;
	return 0;
}

kameron 7년 전 2

4 4

1 1 1 1
-1 -1 -1 1
1 1 1 1
100 -10 1 1

현재 소스로는 (1,1) -> (1,2) -> (1,3) -> (1,4) -> (2,4) -> (3,4) -> (3,3) -> (3,2) -> (3,1) -> (4,1) -> (4,2) -> (4,3) -> (4,4)

ret 부분 초기화가 잘못되어서 (4,2)에서 리턴값을 받을때 항상 ret의 초기화값인 0과 비교하게 되어서 결국 0을 리턴하게 됩니다.

그부분에서 문제가 생기는것 같네요.

tkim0723 7년 전 0

소스 수정했습니다.

말씀해주신 TC는 해결되는데 여전히 문제가 있네요.

kameron 7년 전 2

2 2

1 2

3 4

이 TC의 답은 8인데 해당 소스로 돌려보면 11이 나오죠.

(1,1) 이후에 (1,2)로 이동하는데

v[1][1]은 체킹이 항상되어 있지 않기때문에 (1,2)에서 다시 (1,1)로 이동하게 됩니다.

그래서 결국 (1,1) -> (1,2) -> (1,1) -> (2,1) -> (2,2) 즉 11이 나오게 됩니다.

기본 1,1 체킹이 필요해보이네요.

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

문제

문제

출처

ICPC

예외케이스찾아주세요

tkim0723 7년 전 0

kameron 7년 전 2

tkim0723 7년 전 0

kameron 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말