王琼老师 @ 2023-08-27 14:11:59
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
void Output(vector<vector<int> > &M)
{
for(int i=0; i<M.size(); i++)
{
for(int j=0; j<M[i].size(); j++)
cout<<setw(2)<<M[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
int Findmax(vector<vector<int> > &M)
{
int max=0;
for(int i=0; i<M.size(); i++)
for(int j=0; j<M[i].size(); j++)
if(max<M[i][j])
max=M[i][j];
return max;
}
int Solve(vector<vector<int> > &M)
{
int m=M.size(), n=M[0].size();
// dp[i][j] 存储的是:以(i,j)为终点的最长的滑道的长度
vector<vector<int> > dp(m, vector<int>(n, 1) );
// 状态初始化: dp[i][j] = 1
// 状态转移方程: dp[i][j] = max(dp[i][j-1], dp[i][j+1], dp[i-1][j], dp[i+1][j]) +1
int i, j;
for(int k=0; k<m*n; k++)
{
bool success=true;
for(i=0; i<m; i++)
for(j=0; j<n; j++)
{
if(i-1>=0 && M[i-1][j]>M[i][j] && dp[i-1][j]+1>dp[i][j]) dp[i][j] = dp[i-1][j]+1, success=false;
if(i+1< m && M[i+1][j]>M[i][j] && dp[i+1][j]+1>dp[i][j]) dp[i][j] = dp[i+1][j]+1, success=false;
if(j-1>=0 && M[i][j-1]>M[i][j] && dp[i][j-1]+1>dp[i][j]) dp[i][j] = dp[i][j-1]+1, success=false;
if(j+1< n && M[i][j+1]>M[i][j] && dp[i][j+1]+1>dp[i][j]) dp[i][j] = dp[i][j+1]+1, success=false;
}
if(success==true) break;
}
// Output(dp);
return Findmax(M);
}
int main()
{
//freopen("data.txt", "r", stdin);
int i,j, m,n; cin>>m>>n;
vector<vector<int> > M(m, vector<int>(n) );
for(i=0; i<m; i++)
for(j=0; j<n; j++)
cin>>M[i][j];
cout<<Solve(M)<<endl;
return 0;
}