OpenJ_Bailian - 1088
题解:DFS记忆化搜索
记忆化搜索也可以说是动态规划,最后的答案也是从一个个子问题推导而来
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10;
int n, m;
int g[110][110];
int dis[110][110]; // dis[x][y]代表从坐标(x,y)的点出发的最长路径
int vis[110][110];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int dfs(int sx, int sy)
{
if (dis[sx][sy])
return dis[sx][sy];
dis[sx][sy] = 1;
for (int i = 0; i < 4; ++i)
{
int nx = sx + dir[i][0];
int ny = sy + dir[i][1];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && g[nx][ny] < g[sx][sy])
{
vis[nx][ny] = 1;
dis[sx][sy] = max(dfs(nx, ny) + 1, dis[sx][sy]);
vis[nx][ny] = 0;
}
}
return dis[sx][sy];
}
int main(void)
{
Zeoy;
int t = 1;
while (t--)
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> g[i][j];
int ans = -inf;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
ans = max(dfs(i, j), ans);
}
}
cout << ans << endl;
}
return 0;
}
标签:sy,sx,const,OpenJ,int,1088,110,Bailian,dis
From: https://www.cnblogs.com/Zeoy-kkk/p/17045140.html