bfs 90pts求助 赏关
查看原帖
bfs 90pts求助 赏关
764239
ABCgfed楼主2023/7/14 16:09

#2 RE

#include<iostream>
using namespace std;
int n,m,x[120][120]={0},memory[120][120]={0},dp[120][120]={0},front=-1,rear=0,mx=0;
struct place{
	int x,y;
}queue[10000020];
void deal(){
	int n=queue[rear].x,m=queue[rear].y;
	if(dp[n][m]!=-1){
		rear++;
		memory[n][m]=0;
		return;
	}
	if((dp[n-1][m]!=-1||x[n-1][m]>=x[n][m])&&(dp[n+1][m]!=-1||x[n+1][m]>=x[n][m])&&(dp[n][m+1]!=-1||x[n][m+1]>=x[n][m])&&(dp[n][m-1]!=-1||x[n][m-1]>=x[n][m])){
		int max=-1;
		if(dp[n-1][m]>max&&x[n-1][m]<x[n][m]){
			max=dp[n-1][m];
		}
		if(dp[n+1][m]>max&&x[n+1][m]<x[n][m]){
			max=dp[n+1][m];
		}
		if(dp[n][m+1]>max&&x[n][m+1]<x[n][m]){
			max=dp[n][m+1];
		}
		if(dp[n][m-1]>max&&x[n][m-1]<x[n][m]){
			max=dp[n][m-1];
		}
		dp[n][m]=max+1;
		rear++;
		memory[n][m]=0;
		return;
	}
	if(dp[n-1][m]==-1&&memory[n-1][m]==0){
		front++;
		queue[front].x=n-1;
		queue[front].y=m;
		memory[n][m]=1;
	}
	if(dp[n+1][m]==-1&&memory[n+1][m]==0){
		front++;
		queue[front].x=n+1;
		queue[front].y=m;
		memory[n+1][m]=1;
	}
	if(dp[n][m+1]==-1&&memory[n][m+1]==0){
		front++;
		queue[front].x=n;
		queue[front].y=m+1;
		memory[n][m+1]=1;
	}
	if(dp[n][m-1]==-1&&memory[n][m-1]==0){
		front++;
		queue[front].x=n;
		queue[front].y=m-1;
		memory[n][m-1]=1;
	}
	front++;
	queue[front].x=n;
	queue[front].y=m;
	rear++;
}
void bfs(){
	while(1){
		if(front==rear-1)break;
		deal();
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<=n+1;i++){
		for(int j=0;j<=m+1;j++){
			dp[i][j]=-1;
			if(i==0||j==0||j==n+1||i==n+1){
				dp[i][j]=-2;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>x[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			front++;
			queue[front].x=i;
			queue[front].y=j;
			bfs();
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(dp[i][j]>mx){
				mx=dp[i][j];
			}
		}
	}
	cout<<mx+1;
	return 0;
	/*
	7 7
89 54 72 14 78 29 62
77 49 12 26 83 66 57
99 75 34 23 65 68 79
99 87 65 43 21 23 45
86 53 22 46 80 97 53
14 25 36 47 58 69 70
11 35 70 97 84 57 88
*/
}
2023/7/14 16:09
加载中...