KK_lang @ 2022-11-08 18:39:49
思路:DFS,#2 T掉了,求如何优化。
#include<bits/stdc++.h>
using namespace std;
int n, m, ans;
int a[110][110];
bool vis[110][110];
void dfs(int x, int y, int step)
{
if (x < 1 || x > n || y < 1 || y > m) return;
if (vis[x][y]) return;
vis[x][y] = true;
ans = max(ans, step);
if (a[x][y] > a[x + 1][y]) dfs(x + 1, y, step + 1);
if (a[x][y] > a[x][y + 1]) dfs(x, y + 1, step + 1);
if (a[x][y] > a[x - 1][y]) dfs(x - 1, y, step + 1);
if (a[x][y] > a[x][y - 1]) dfs(x, y - 1, step + 1);
vis[x][y] = false;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dfs(i, j, 1);
cout << ans << endl;
return 0;
}
感谢各位大佬
by xiaoPanda @ 2022-11-08 18:43:43
@KK_lang 记忆化搜索。
by KK_lang @ 2022-11-08 18:46:31
@xiaoPanda 艹谢谢,但是我已经几乎彻底忘记记忆化了。。。
by Tu_es_trop_belle @ 2022-11-08 19:35:15
@KK_lang 提示:第二个点答案是9900
by KK_lang @ 2022-11-08 22:49:56
@Tu_es_trop_belle 。。。