跳跃问题

发表于 | 分类于 |
字数统计: 370 | 阅读时长 ≈ 1

跳跃问题

某n*n的棋盘的每个格子中都有1到9个整数。从棋盘的左上角出发，向右或向下每次跳跃格子所指定的格数，判断是否能够到达棋盘的右下角。如果能，输出true, 否则输出false.

输入：

输入第一行为整数n，表示棋盘方格的数量。其后的n行，各行均有n个数字。表示在该方格中可以向下或向右跳跃的方格数。

输出：

输出1行，true或者false. true表示从左上角可以跳跃到右下角,否则为false。

样例输入：

7 
2 5 1 6 1 4 1
6 1 1 2 2 9 3
7 2 3 2 1 3 1
1 1 3 1 7 1 2
4 1 2 3 4 1 2
3 3 1 2 3 4 1
1 5 2 9 4 7 1

样例输出：

true

思路

没什么好说的，如果dp[i][j]能到达则dp[i+data[i][j]][j] , dp[i][j+data[i][j]] 也能到达。

时间复杂度$O(n^2)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
using namespace std;

int main(){
 int n;
 int data[100][100];
 bool dp[100][100];
 cin>>n;
 for(int i=0;i<n;i++){
     for(int j=0;j<n;j++){
         cin>>data[i][j];
         dp[i][j]=false;
     }
 }
 dp[0][0]=true;
 for(int i=0;i<n;i++){
     for(int j=0;j<n;j++){
         if(dp[i][j]==true){
             dp[i+data[i][j]][j]=true;
             dp[i][j+data[i][j]]=true;
         }
     }
 }
 cout<<dp[n-1][n-1]<<endl;
return 0;
}

0%