题目分析
1.看数据范围,大概知道dfs能做
2.自0问题开始查找,确保之后每次查找到的问题的困难度均大于上一次
3.遍历所有情况再记录cnt即可
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 20;int g[N][N];
bool vis[N];
int n, ans;void dfs(int x, int val, int cnt) {ans = (ans > cnt ? ans : cnt);for(int i = 0; i < n; i++){if(vis[i] || i == x) continue; //走过或为当前点则continueif(g[x][i] >= val) {vis[i] = 1;dfs(i, g[x][i], cnt + 1);vis[i] = 0;}}
}int main()
{while(scanf("%d", &n) != EOF){ans = 0;memset(vis, 0, sizeof vis);for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){scanf("%d", &g[i][j]);}}vis[0] = 1;dfs(0, 0, 1);printf("%d\n", ans);}return 0;
}