글 읽기 - 반례를 못찾겠습니다.

wiz9243 4년 전 0

반례를 못찾겠습니다 ㅠㅠ

dfs로 dp(cnt배열)값에는 값을 맨 끝에서부터 거꾸로 올리는 방식으로 했습니다.

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

int n,m;
char arr[51][51];
int cnt[51][51];
bool visit[51][51];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

int dfs(int x,int y){
	visit[x][y]=true;
	int res=0;
	
	for(int i=0;i<4;i++){
		int X=x+dx[i]*(arr[x][y]-'0');
		int Y=y+dy[i]*(arr[x][y]-'0');
		
		if(arr[X][Y]=='H')continue;
		if(visit[X][Y])return cnt[x][y]=-1;
		
		if(0<=X && X<n && 0<=Y && Y<m){
			if(cnt[X][Y])res=max(res,cnt[X][Y]+1);
			else{
				int a= dfs(X,Y);
				if(a==-1)return cnt[x][y]=-1;	
				res=max(res,a+1);
			}
		} 
	
			
	}
	
	visit[x][y]=false;

	if(res==0)return cnt[x][y]=1;
	return	cnt[x][y]=res;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)scanf("%s",arr[i]);
	
	dfs(0,0);
	
	printf("%d\n",cnt[0][0]);

}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

wiz9243 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말