티스토리 뷰
https://algospot.com/judge/problem/read/JUMPGAME
algospot.com :: JUMPGAME
외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상
algospot.com
go(x,y) : (x,y)에서 도착점(n-1,n-1)까지 도달할 수 있으면 1, 아니면 0을 반환한다.
cache를 잡아서 중복해서 함수 호출이 일어나지 않도록 한다.
#include <cstdio>
#include <cstring>
int t,n,map[100][100],cache[100][100];
int go(int x,int y)
{
if(x>=n || y>=n) return 0;
if(x==n-1 && y==n-1) return 1;
int &ret=cache[x][y];
if(ret!=-1) return ret;
int next=map[x][y];
return ret=(go(x+next,y) || go(x,y+next));
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&map[i][j]);
memset(cache,-1,sizeof(cache));
printf("%s\n",go(0,0)?"YES":"NO");
}
return 0;
}