JUMPGAME.cpp

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

int matrix[101][101];
int cache[101][101];
int matrix_num;

int DP(int x, int y)
{
    if(y > matrix_num || x > matrix_num)
        return 0;
    if(x == matrix_num && y == matrix_num)
        return 1;

    int& ref = cache[x][y];
    if(ref != -1) return ref;

    int jumpsize = matrix[x][y];
    return ref = (DP(x + jumpsize, y) || DP(x, y + jumpsize));
}

int main()
{
    int test_case_num;
    cin >> test_case_num;
    for(int k = 0; k < test_case_num; ++k)
    {
        memset(cache, -1, sizeof(cache));
        cin >> matrix_num;

        for(int i = 1; i <= matrix_num; ++i)
        {
            for(int j = 1; j <= matrix_num; ++j)
            {
                int input;
                cin >> input;
                matrix[i][j] = input;
            }
        }
    
        switch(DP(1, 1))
        {
            case 0:
                cout << "NO";
                break;
            case 1:
                cout << "YES";
                break;
        }
        cout << endl;
    }
    return 0;
}