BFS WA 一个点
查看原帖
BFS WA 一个点
356003
Moeebius楼主2021/8/4 18:31
#include <bits/stdc++.h>
using namespace std;
struct point{
	int x,y,step;
};
point q[10000000],s;
int used[1001][1001],front,tail,n,m,a[1001][1001];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

void bfs(){
	//int step=0;
	front=tail=1;
	//memset(used,0,sizeof(used));
	q[1]=s;
	used[s.x][s.y]=s.step;
	while(front<=tail){
		point u=q[front++];
		point v;
		for(int i=0; i<4; i++){
			v.x=u.x+dx[i],v.y=u.y+dy[i],v.step=u.step+1;
			if(v.x<1||v.x>n||v.y<1||v.y>m) continue;
			if(used[v.x][v.y]>v.step) continue;
			if(a[v.x][v.y]>=a[u.x][u.y]) continue;
			q[++tail]=v;
			used[v.x][v.y]=v.step;
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			scanf("%d",&a[i][j]);
		}
	}
	s.step=1;
	int ans=0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(used[i][j]==0){
				s.x=i;
				s.y=j;
				bfs();
			}
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(used[i][j]>ans) ans=used[i][j];
		}
	}
	cout<<ans;
	return 0;
}
2021/8/4 18:31
加载中...