외발 뛰기

문제 : https://algospot.com/judge/problem/read/JUMPGAME

algospot.com :: JUMPGAME

입력:

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 격자의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에 각 n개의 숫자로 왼쪽 위부터 각 칸에 쓰인 숫자들이 주어집니다. 오른쪽 아래 있는 끝 점 위치에는 0이 주어집니다.

출력:

각 테스트 케이스마다 한 줄로, 시작점에서 끝 점으로 도달할 수 있을 경우 "YES"를, 아닐 경우 "NO"를 출력합니다. (따옴표 제외)

 

 

코드(C++) 종만북 참조

 

#include 
#include 
using namespace std;
const int MAX = 100;
int board[MAX][MAX];

int Y;
int cache[MAX][MAX];
int jump(int y, int x)
{
if (y ==Y-1 && x == Y-1)
{
return true;
}
if (y > Y-1 || x > Y-1) return false;

int& ret = cache[y][x];
if (ret != -1)   // 중복된 루트를 막아주자.
return ret;

return ret = (jump(y + board[y][x], x) || jump(y, x + board[y][x]));

}
int main()
{
int C;
cin >> C;
while (C--) {
memset(cache, -1, sizeof(cache)); // 재사용할 캐쉬를 -1로 초기화
cin >> Y;

for (int i = 0; i < Y; ++i)
for (int j = 0; j < Y; ++j)
{
cin >> board[i][j];
}

if (jump(0, 0) == 1)
cout << "YES" << endl;
else
cout << "NO" << endl;

}
return 0;
}