글 읽기 - dfs + dp로 풀었는데, wrong answer 가 나옵니다.

ian981130s 3년 전 0

dfs + dp로 풀었고, 질문 게시판에 있는 tc들도 다 통과하네요...

어디가 틀렸는지, 아니면 반례가 있는지, 고수님들의 의견 부탁드립니다.

#include <stdio.h>

int IsCycle;
int Sero, Garo;

char Map[55][55];
char InputMap[55][55];

int Memo[51][51];
int IsVisit[51][51];

int dS[4] = {1, -1, 0, 0};
int dG[4] = {0, 0, 1, -1};


int Max(int num1, int num2)
{
	if(num1>num2)
		return num1;
	else
		return num2;
}



void Input()
{
	scanf("%d %d", &Sero, &Garo);
	
	for(int idx=0 ; idx<Sero ; idx++)
		scanf("%s", InputMap[idx]);
		
	for(int idx=0 ; idx<Sero ; idx++)
		for(int jdx=0 ; jdx<Garo ; jdx++)
			Map[idx+1][jdx+1] = InputMap[idx][jdx];	
}



int DFS(int NowS, int NowG, int Cnt)
{
	if(Memo[NowS][NowG]>Cnt)
		return Memo[NowS][NowG];
	
	IsVisit[NowS][NowG] = 1;
	Memo[NowS][NowG] = Cnt;
	
	for(int idx=0 ; idx<4 ; idx++)
	{
		int NextS = NowS + (Map[NowS][NowG]-'0')*dS[idx];
		int NextG = NowG + (Map[NowS][NowG]-'0')*dG[idx];
		
		if(NextS>=1 && NextG>=1 && NextS<=Sero && NextG<=Garo)
		{
			if('1'<=Map[NextS][NextG] && Map[NextS][NextG]<='9')
			{
				if(IsVisit[NextS][NextG]==1)
					IsCycle = 1;
				else
					Memo[NowS][NowG] = Max(Memo[NowS][NowG], DFS(NextS, NextG, Cnt+1));
			}
		}
	}
	
	IsVisit[NowS][NowG] = 0;
	return Memo[NowS][NowG];
}



void Solve()
{
	Input();
	
	int Answer = DFS(1, 1, 1);
	
	if(IsCycle==1)
		printf("-1\n");
	else
		printf("%d\n", Answer);
}



int main(void)
{
	Solve();
	return 0;
}

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

문제

문제

출처

ICPC

dfs + dp로 풀었는데, wrong answer 가 나옵니다.

ian981130s 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말