#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int board[105][105];
int dp[105][105];
int n;
int jump(int x, int y);
int main()
{
int c;
scanf("%d", &c);
for (int i = 1; i <= c; i++)
{
scanf("%d", &n);
for (int a = 1; a <= n; a++)
{
for (int b = 1; b <= n; b++)
{
scanf("%d", &board[a][b]);
dp[a][b] = -1; //처음엔 여기를 0으로 초기화
}
}
if (jump(1,1))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
int jump(int x, int y)
{
if (x == n && y == n)
return 1;
if (x > n || y > n)
return 0;
if (dp[x][y] != -1)
return dp[x][y];
dp[x][y] = (jump(x + board[x][y], y) || jump(x, y + board[x][y]));
return dp[x][y];
}
제가 처음에는 dp배열에 0값으로 초기화하고 제출을 했는데 시간초과가 뜨더군요 ㅜㅜ 근데 -1으로 초기화한 후 제출해보니 맞았다고 뜨네요 원인이 너무 궁금합니다 ㅠㅠㅠ 도와주세요 ㅠ
jump 함수 내의 if (dp[x][y] != -1) 절에서 dp[x][y]의 값이 -1이 아니면 바로 return 하도록 되어있네요.
즉 -1을 초기값으로 본다는 것인데, 0으로 초기화하면 모든 경우에 대해 '아직 시도하지 않았다'가 아닌 '갈수없다'라고 초기화하는것이랑 똑같습니다.
fegler
제가 처음에는 dp배열에 0값으로 초기화하고 제출을 했는데 시간초과가 뜨더군요 ㅜㅜ 근데 -1으로 초기화한 후 제출해보니 맞았다고 뜨네요 원인이 너무 궁금합니다 ㅠㅠㅠ 도와주세요 ㅠ
9년 전