广搜为啥80分,哪里有错?
查看原帖
广搜为啥80分,哪里有错?
776599
jping楼主2022/12/28 15:22
#include<iostream>
#include<queue>
using namespace std;
struct T{
	int x,y;
}sT,now;
queue<T>AA;
int a[103][103],dp[103][103];
int main(){
	int r,c,ans=1,flag;
	cin>>r>>c;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)cin>>a[i][j];
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++){
			if(a[i][j]>=a[i-1][j] && a[i][j]>=a[i][j-1] && a[i][j]>=a[i][j+1] && a[i][j]>=a[i+1][j]){
				sT.x=i;
				sT.y=j;
				dp[i][j]=1;
				AA.push(sT);
			}
		}
	while(!AA.empty()){
		now=AA.front();
		AA.pop();
//		cout<<now.x<<" "<<now.y<<" "<<dp[now.x][now.y]<<endl;
		if(now.x>1 && dp[now.x-1][now.y]==0){
			flag=0;
			if(dp[now.x-2][now.y]==0 && a[now.x-1][now.y]<a[now.x-2][now.y])flag++;
			if(dp[now.x-1][now.y-1]==0 && a[now.x-1][now.y]<a[now.x-1][now.y-1])flag++;
			if(dp[now.x-1][now.y+1]==0 && a[now.x-1][now.y]<a[now.x-1][now.y+1])flag++;
			if(flag==0){
				sT.x=now.x-1;
				sT.y=now.y;
				dp[now.x-1][now.y]=dp[now.x][now.y]+1;
				AA.push(sT);
			}
		} 
		if(now.y>1 && dp[now.x][now.y-1]==0){
			flag=0;
			if(dp[now.x-1][now.y-1]==0 && a[now.x][now.y-1]<a[now.x-1][now.y-1])flag++;
			if(dp[now.x][now.y-2]==0 && a[now.x][now.y-1]<a[now.x][now.y-2])flag++;
			if(dp[now.x+1][now.y-1]==0 && a[now.x][now.y-1]<a[now.x+1][now.y-1])flag++;
			if(flag==0){
				sT.x=now.x;
				sT.y=now.y-1;
				dp[now.x][now.y-1]=dp[now.x][now.y]+1;
				AA.push(sT);
			}
		} 
		if(now.y<c && dp[now.x][now.y+1]==0){
			flag=0;
			if(dp[now.x-1][now.y+1]==0 && a[now.x][now.y+1]<a[now.x-1][now.y+1])flag++;
			if(dp[now.x][now.y+2]==0 && a[now.x][now.y+1]<a[now.x][now.y+2])flag++;
			if(dp[now.x+1][now.y+1]==0 && a[now.x][now.y+1]<a[now.x+1][now.y+1])flag++;
			if(flag==0){
				sT.x=now.x;
				sT.y=now.y+1;
				dp[now.x][now.y+1]=dp[now.x][now.y]+1;
				AA.push(sT);
			}
		} 
		if(now.x<r && dp[now.x+1][now.y]==0){
			flag=0;
			if(dp[now.x+2][now.y]==0 && a[now.x+1][now.y]<a[now.x+2][now.y])flag++;
			if(dp[now.x+1][now.y-1]==0 && a[now.x+1][now.y]<a[now.x+1][now.y-1])flag++;
			if(dp[now.x+1][now.y+1]==0 && a[now.x+1][now.y]<a[now.x+1][now.y+1])flag++;
			if(flag==0){
				sT.x=now.x+1;
				sT.y=now.y;
				dp[now.x+1][now.y]=dp[now.x][now.y]+1;
				AA.push(sT);
			}
		} 
	}
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++){
			ans=max(ans,dp[i][j]);
		}
	cout<<ans;
	return 0;
}
2022/12/28 15:22
加载中...