wa了8个点,20分求助(求助帖,玄关。)
查看原帖
wa了8个点,20分求助(求助帖,玄关。)
501009
王琼老师楼主2023/8/27 14:11
#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;
}
2023/8/27 14:11
加载中...