wa了8个点,20分求助(求助帖,玄关。)

P1434 [SHOI2002] 滑雪

王琼老师 @ 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;
}

|