题解：P12212 [蓝桥杯 2023 国 Python B] 最大阶梯

· · 题解

四个方向的DP，不同顺序的遍历，心细可以写

include <iostream>

using namespace std; int n; const int N=1005; int a[N][N]; int dp[N][N][4];

int main() {

//memset(dp,1,sizeof(dp)); cin>>n; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=0;k<4;k++)dp[i][j][k]=1; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];

//0:看上左 for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i-1>=1&&j-1>=1) { if(a[i][j]==a[i-1][j]&&a[i][j]==a[i][j-1])dp[i][j][0]=min(dp[i-1][j][0],dp[i][j-1][0])+1; } } } //1:看右边下边 for(int i=n;i>=1;i--) { for(int j=n;j>=1;j--) { if(i+1<=n&&j+1<=n) { if(a[i][j]==a[i+1][j]&&a[i][j]==a[i][j+1])dp[i][j][1]=min(dp[i+1][j][1],dp[i][j+1][1])+1; } } } //2:看右边跟上边 for(int i=1;i<=n;i++) { for(int j=n;j>=1;j--) { if(i-1>=1&&j+1<=n) { if(a[i][j]==a[i-1][j]&&a[i][j]==a[i][j+1])dp[i][j][2]=min(dp[i-1][j][2],dp[i][j+1][2])+1;

  }
}

} //3:看左下 for(int i=n;i>=1;i--) { for(int j=1;j<=n;j++) { if(i+1<=n&&j-1>=1) { if(a[i][j]==a[i+1][j]&&a[i][j]==a[i][j-1])dp[i][j][3]=min(dp[i+1][j][3],dp[i][j-1][3])+1; } } } int ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { for(int k=0;k<4;k++) { ans=max(ans,dp[i][j][k]); } }//cout<<endl; } cout<<ans<<endl; return 0; }