求助P3456,70pts
  • 板块学术版
  • 楼主PCCP
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/8/23 17:04
  • 上次更新2023/10/27 14:00:28
查看原帖
求助P3456,70pts
310773
PCCP楼主2022/8/23 17:04

复习的时候敲BFS,写P3456,出问题了,请各位大佬指教。QWQ

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef pair <int,int> PII;
int n,a[1010][1010];
bool st[1010][1010];
int xx[10]={-1,-1,-1,0,0,1,1,1};
int yy[10]={-1,0,1,-1,1,-1,0,1};
int bfs(int x,int y){
	queue<PII> q;
	q.push({x,y});
	st[x][y]=1;
	int flag=0;//1:山峰;2:山谷 ;3:no
	while(q.empty()==false){
		PII t=q.front();
		q.pop();
		for(int i=0;i<8;i++){
			int tx=t.first+xx[i];
			int ty=t.second+yy[i];
			if(tx<=0||tx>n||ty<=0||ty>n){
				continue;
			}
			if(a[tx][ty]<a[t.first][t.second]){
				if(flag==2){
					flag=3;
				}
				if(flag==0){
					flag=1;
				}
			}
			else if(a[tx][ty]>a[t.first][t.second]){
				if(flag==1){
					flag=3;
				}
				if(flag==0){
					flag=2;
				}
			}
			else if(a[tx][ty]==a[t.first][t.second]&&st[tx][ty]==0){
				st[tx][ty]=1;
				q.push({tx,ty});
			}
		}
	}
	return flag;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&a[i][j]);
		}
	}
	int sg=0,sf=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(st[i][j]==1){
				continue;
			}
			int flag=bfs(i,j);
			if(flag==1){
				sf++;
			}
			if(flag==2){
				sg++;
			}
		}
	}
	printf("%d %d",sf,sg);
}
2022/8/23 17:04
加载中...