P1141 01迷宫

这题数据有点高级啊（这么高级的数据能不能把它变成黄题呢？不然显得我很垃圾（虽然是事实））

思路

联通块，把周围四格与自己不同的联通起来，看成一个大块，知道要的坐标属于哪个大块并数出大块有多少个点就行了

我的第一个想法是先预处理出联通块，然后直接暴力搜索，需要哪个坐标就去搜大块有几个点（想着橙题，随便做都能AC。。

（70分。。

#include <bits/stdc++.h>
using namespace std;
int a[1005][1005];
int b[1005][1005];
bool c[1005][1005];
int n,m;
void build(int x,int y,int k)
{
	if(x>n || x==0) return; if(y>n || y==0) return ;
	b[x][y]=k;
	if(a[x+1][y]!=a[x][y] && !b[x+1][y]) build(x+1,y,k);
	if(a[x-1][y]!=a[x][y] && !b[x-1][y]) build(x-1,y,k);
	if(a[x][y+1]!=a[x][y] && !b[x][y+1]) build(x,y+1,k);
	if(a[x][y-1]!=a[x][y] && !b[x][y-1]) build(x,y-1,k);
}
int search(int x,int y)
{
	int ans=1;
	if(b[x+1][y]==b[x][y] && !c[x+1][y]) {c[x+1][y]=1; ans+=search(x+1,y);}
	if(b[x-1][y]==b[x][y] && !c[x-1][y]) {c[x-1][y]=1; ans+=search(x-1,y);}
	if(b[x][y+1]==b[x][y] && !c[x][y+1]) {c[x][y+1]=1; ans+=search(x,y+1);}
	if(b[x][y-1]==b[x][y] && !c[x][y-1]) {c[x][y-1]=1; ans+=search(x,y-1);}
	return ans;
}
int main()
{
	int x,y,k=1;
	string s;
	cin>>n>>m;
	memset(a,100,sizeof(a));
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		for(int j=0;j<s.size();j++)
		    a[i][j+1]=s[j]-48;
	}//输入的时候是字符串，需要逐字处理 
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	        if(!b[i][j]){
	        	build(i,j,k);
	            k++;
			}//预处理 ，属于同一个大块的都有相同的K值 
	for(int k=1;k<=m;k++)
	{
		cin>>x>>y;
		int ans=0;
		memset(c,0,sizeof(c));
		c[x][y]=1;
		ans=search(x,y);//暴力搜索所属大块有几个点 
		cout<<ans<<endl;
	}
	return 0;
}

然后就想着改进：感觉每次都暴力数大块有几个点，假如几个点属于同一大块，不就重复数了吗，既然这样，再预处理一下，直接输出答案不就完美了（想到这，感觉这次肯定能AC了。。

（80分。。 这数据真的高级

#include <bits/stdc++.h>
using namespace std;
int a[1005][1005];
int b[1005][1005];
bool c[1005][1005];
int d[1005][1005];
int n,m;
void build(int x,int y,int k)
{
	if(x>n || x==0) return; if(y>n || y==0) return ;
	b[x][y]=k;
	if(a[x+1][y]!=a[x][y] && !b[x+1][y]) build(x+1,y,k);
	if(a[x-1][y]!=a[x][y] && !b[x-1][y]) build(x-1,y,k);
	if(a[x][y+1]!=a[x][y] && !b[x][y+1]) build(x,y+1,k);
	if(a[x][y-1]!=a[x][y] && !b[x][y-1]) build(x,y-1,k);
}
int search(int x,int y)
{
	int ans=1;
	if(b[x+1][y]==b[x][y] && !c[x+1][y]) {c[x+1][y]=1; ans+=search(x+1,y);}
	if(b[x-1][y]==b[x][y] && !c[x-1][y]) {c[x-1][y]=1; ans+=search(x-1,y);}
	if(b[x][y+1]==b[x][y] && !c[x][y+1]) {c[x][y+1]=1; ans+=search(x,y+1);}
	if(b[x][y-1]==b[x][y] && !c[x][y-1]) {c[x][y-1]=1; ans+=search(x,y-1);}
	return ans;
}
void build1(int x,int y,int k)//预处理，在d数组直接标出属于同一个大块的点的个数 
{
	if(x>n || x==0) return; if(y>n || y==0) return ;
	d[x][y]=k;
    if(b[x+1][y]==b[x][y] && !d[x+1][y]) {d[x+1][y]=k; build1(x+1,y,k);}
	if(b[x-1][y]==b[x][y] && !d[x-1][y]) {d[x-1][y]=k; build1(x-1,y,k);}
	if(b[x][y+1]==b[x][y] && !d[x][y+1]) {d[x][y+1]=k; build1(x,y+1,k);}
	if(b[x][y-1]==b[x][y] && !d[x][y-1]) {d[x][y-1]=k; build1(x,y-1,k);}
}
int main()
{
	int x,y,k=1;
	string s;
	cin>>n>>m;
	memset(a,100,sizeof(a));
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		for(int j=0;j<s.size();j++)
		    a[i][j+1]=s[j]-48;
	}
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	        if(!b[i][j]){
	        	build(i,j,k);
	        	memset(c,0,sizeof(c));
	        	c[i][j]=1;
	        	int ans=search(i,j);//搜索出大块有几个点 
	        	build1(i,j,ans);//预处理 
	            k++;
			}
	for(int k=1;k<=m;k++)
	{
		cin>>x>>y;
		cout<<d[x][y]<<endl;//直接输出结果 
	}
	return 0;
}

然后实在撑不住，去看了题解。。

每次碰到没搜过的就进行一次搜索，碰到的就直接输出（用数组模拟队列来储存属于同一大块的点的坐标

#include <bits/stdc++.h>
using namespace std;
int a[1005][1005];
int c[1005][1005];
int d[1005][1005];
int xx[10000005],yy[1000005];
int n,m;
void search(int x,int y)
{
	int t=1,h=0,ans=0;
	while(h<t)//bfs的队列 
	{
	    h++;
	    x=xx[h]; y=yy[h];
		if(a[x+1][y]!=a[x][y] && !c[x+1][y] && x+1<=n) {t++; c[x+1][y]=1; xx[t]=x+1; yy[t]=y;}
        if(a[x-1][y]!=a[x][y] && !c[x-1][y] && x-1>0) {t++; c[x-1][y]=1; xx[t]=x-1; yy[t]=y;}
	    if(a[x][y+1]!=a[x][y] && !c[x][y+1] && y+1<=n) {t++; c[x][y+1]=1; xx[t]=x; yy[t]=y+1;}
	    if(a[x][y-1]!=a[x][y] && !c[x][y-1] && y-1>0) {t++; c[x][y-1]=1; xx[t]=x; yy[t]=y-1;}
	    
	}
	for(int i=1;i<=t;i++)
	    d[xx[i]][yy[i]]=t;//每个属于大块的点都标记上大块点的个数 
	return ;
}
int main()
{
	int x,y,k=1;
	string s;
	cin>>n>>m;
	memset(a,100,sizeof(a));
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		for(int j=0;j<s.size();j++)
		    a[i][j+1]=s[j]-48;
	}
	for(int k=1;k<=m;k++)
	{
		cin>>x>>y;
		if(!d[x][y]) {c[x][y]=1; xx[1]=x; yy[1]=y; search(x,y);}//如果没搜过就搜 
		cout<<d[x][y]<<endl; 
	}
	return 0;
}