广搜,5AC 5RE 跪等大佬救命 QAQ orz
查看原帖
广搜,5AC 5RE 跪等大佬救命 QAQ orz
122342
今夕何年楼主2022/5/16 19:46

先广搜,标记每一次搜索到连通块搜索过、同一搜索序列号,搜索过程记录搜索区域面积,搜索一遍完成将面积计入到ans数组里,最后通过某一区域标记的搜索序列号访问ans找到搜索区域面即QAQ感觉思路没错呀,球球救救我

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<limits.h>
#include<cmath>
using namespace std;

int n,m;
int mp[1005][1005];
int ans[1001];
int num=2;
struct def_point{
	int x,y;
}; 

def_point que[100005];
int x_dir[4]={0,0,-1,1};
int y_dir[4]={-1,1,0,0};//方向数组 

int cnt=0;
bool ck[1005][1005];

void bfs(int x,int y){
	int ct=0;
	int st=0,ed=1;
	def_point row[1005];
	memset(row,0,sizeof(row));
	row[ed].x=x;row[ed].y=y;
	++ed;
	ck[x][y]=false;
	while(st!=ed){
		++st;
		for(int j=0;j<=3;++j){
			int xx=row[st].x+x_dir[j];
			int yy=row[st].y+y_dir[j];
			if( xx<=n && xx>0 && yy<=n && yy>0  &&
			    ck[xx][yy]    && 
				mp[xx][yy]!=mp[row[st].x][row[st].y]){
				row[ed].x=xx;row[ed].y=yy;
				++ed;
				ck[xx][yy]=false;
			}
		}
	    mp[row[st].x][row[st].y]=num;
		//将每一区域写为第num号索引,之后以便在ans里查找		
	}
	cnt=st-1;//cnt记录本次搜索联通区域的大小 
} 

void check_mp(){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			cout<<mp[i][j];
		}
		cout<<endl;
	}
}

int main(){
	char qaq;	
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			cin>>qaq;
			mp[i][j]=int(qaq);
		}
	}
	for(int i=1;i<=m;++i){
		cin>>que[i].x>>que[i].y;
	}
	memset(ck,true,sizeof(ck));
	//数据输入完毕 
	
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			if(ck[i][j]){
				bfs(i,j);
				ans[num]=cnt;
				++num;
			}
		}
	}

	for(int i=1;i<=m;++i){
		cout<<ans[mp[que[i].x][que[i].y]]<<endl;
	}

	return 0;
}
2022/5/16 19:46
加载中...