A33818. 最长路线
填空题
困难
知识点
题目描述
最长路线
题目描述
有一个N*M的矩阵，且矩阵中每个方格中都有一个整数（0≤整数≤100） ，小蓝需要按照以下要求从矩阵中找出一条最长的移动路线，且输出最长路线的长度（1个方格为1个长度）。
要求
1.小蓝可以从矩阵中任意一个方格开始向它的上、下、左、右相邻的任意一个方格移动，且移动的路线不能有交叉；
2.小蓝每次所要移动到的方格中的整数都要小于当前所在方格中的整数（如当前所在的方格中的整数为3，那么可以移动到数字为0，1，2的格子里，不可以移动到数字为3，4，5...的格子里）；
例如：N=3，M=3，矩阵方格如下：
最长路线为4 -> 3 -> 2 -> 1，故路线长度为4。
输入描述
第一行输入两个正整数N，M（1＜N≤1000，1＜M≤1000），N表示矩阵的行数，M表示矩阵的列数，两个正整数之间以一个空格隔开
第二行开始输入N行，每行包含M个整数（0≤每个整数≤100），表示每个方格中的整数，每个整数之间以一个空格隔开
输出描述
输出一个整数，表示最长路线的长度
样例输入
3 3
1 1 3
2 3 4
1 1 1
样例输出
4
参考答案
#include<iostream>
using namespace std;
int my_arr[1001][1001];
bool flag[1001][1001];
int n, m;
int cnt = 1;
int max_cnt = 1;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
void dfs(int x, int y) {
if((my_arr[x][y] <= my_arr[x - 1][y] || x - 1 < 1) && (my_arr[x][y] <= my_arr[x + 1][y] || x + 1 > m) && (my_arr[x][y] <= my_arr[x][y - 1] || y - 1 < 1) && (my_arr[x][y] <= my_arr[x][y + 1] || y + 1 > n)) {
if(cnt > max_cnt)max_cnt = cnt;
return;
}
for(int i = 0; i < 4; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
if(tx >= 1 && tx <= m && ty >= 1 && ty <= n && flag[tx][ty] == 0 && my_arr[tx][ty] < my_arr[x][y]) {
flag[tx][ty] = 1;
cnt++;
dfs(tx, ty);
flag[tx][ty] = 0;
cnt--;
}
}
}
int main() {
cin >> n >> m;
int result = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> my_arr[i][j];
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
max_cnt = 1;
cnt = 1;
for(int x = 1; x <= n; x++) {
for(int y = 1; y <= m; y++) {
flag[x][y] = 0;
}
}
flag[i][j] = 1;
dfs(i, j);
if(max_cnt > result)result = max_cnt;
}
}
cout << result << endl;
return 0;
}
上一题
下一题