60pts,WA#1,9,10,MLE#2
查看原帖
60pts,WA#1,9,10,MLE#2
1049379
jhlcxoi114514楼主2025/2/8 10:31

代码较长,请慢慢食用(悬关)。

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,M=1e2+10;
struct node{
	int x,y,k;
}a[M*M];
int dp[M][M],mp[M][M],n,m;
int dix[]={1,0,-1,0},diy[]={0,1,0,-1};
queue<pair<int,int> > q;
bool cmp(node a,node b){
	return a.k<b.k;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[(i-1)*m+j].k;
			mp[i][j]=a[(i-1)*m+j].k;
			a[(i-1)*m+j].x=i,a[(i-1)*m+j].y=j;
		} 
	}
	sort(a+1,a+n*m+1,cmp);
	dp[a[1].x][a[1].y]=1;
	q.push(make_pair(a[1].x,a[1].y));
    while(!q.empty()){
    	int tx=q.front().first,ty=q.front().second;
    	q.pop();
    	for(int i=0;i<4;i++){
    		int nx=tx+dix[i];
    		int ny=ty+diy[i];
    		if(nx>0&&ny>0&&nx<=n&&ny<=m&&mp[nx][ny]>mp[tx][ty]){
    			q.push(make_pair(nx,ny));
    			dp[nx][ny]=dp[tx][ty]+1;
    		}
    	}
    }
    int Max=-1;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		Max=max(Max,dp[i][j]);
    	}
    }
    cout<<Max;
}
2025/2/8 10:31
加载中...