洛谷P1141 01迷宮

題目描述

有一個僅由數字00與11組成的n \times nn×n格迷宮。若你位于一格0上，那麼你可以移動到相鄰44格中的某一格11上，同樣若你位于一格1上，那麼你可以移動到相鄰44格中的某一格00上。

你的任務是：對于給定的迷宮，詢問從某一格開始能移動到多少個格子（包含自身）。

輸入輸出格式

輸入格式：

第11行為兩個正整數n,mn,m。

下面nn行，每行nn個字元，字元隻可能是00或者11，字元之間沒有空格。

接下來mm行，每行22個用空格分隔的正整數i,ji,j，對應了迷宮中第ii行第jj列的一個格子，詢問從這一格開始能移動到多少格。

輸出格式：

mm行，對于每個詢問輸出相應答案。

輸入輸出樣例

輸入樣例#1： 複制

2 2
01
10
1 1
2 2
      

輸出樣例#1： 複制

4
4
      

說明

所有格子互相可達。

對于20\%20%的資料，n≤10n≤10；

對于40\%40%的資料，n≤50n≤50；

對于50\%50%的資料，m≤5m≤5；

對于60\%60%的資料，n≤100,m≤100n≤100,m≤100；

對于100\%100%的資料，n≤1000,m≤100000n≤1000,m≤100000。

第一次爆搜妥妥的TLE啊有木有，這個時候就要看看大佬們怎麼做的了嘻嘻

思路： 其實這就是一個連通圖嘛，隻不過不是相同的數組成一個連通圖，而是從這個點出發能到達的所有點組成一個連通圖

我們這樣，把第一次搜尋能到達的所有的點都标記為1，第二次搜尋沒有被搜過的點标記為2。。。

這個時候我們就開一個uni數組，第i次搜尋到的點都标記為i 于是就變成了這樣：

由于這裡總共有四個聯通快，是以隻需要搜四次，就會把所有的點搜完，然後仔細數一下第一個聯通快有16個塊，于是ans[1]==16，第二個ans[2]=12。。。。；

還有就是vis不用初始化，因為任何兩次的搜尋都不會交叉，隻需要判斷别忘回走就行了

#include<bits/stdc++.h>
#define M 1005
using namespace std;
struct node{int x,y;};
int a[M][M],uni[M][M];//nui儲存i j這個點屬于第幾個聯通快 
int m,n,ans[10000000],k=0;//ans儲存第i個連通圖有多少塊
bool vis[M][M];//标記是否走過 
queue<node> Q;
node temp;
void move(int tx,int ty,int flag)//移動函數 
{
	if(tx>=0&&tx<n&&ty>=0&&ty<n&&vis[tx][ty]==false&&flag!=a[tx][ty])
	{
		vis[tx][ty]=true;
		Q.push((node){.x=tx,.y=ty});
	}
}
int bread(int ix,int iy)//廣搜 
{
	int sum=0;
	Q.push((node){.x=ix,.y=iy});
	vis[ix][iy]=true;
	while(!Q.empty())
	{
		sum++;//累加 
		temp=Q.front();Q.pop();
		int tx=temp.x,ty=temp.y;
		int flag=a[tx][ty];
		uni[tx][ty]=k; //這個點在第k個點連通圖中 
		move(tx+1,ty,flag);
		move(tx-1,ty,flag);
		move(tx,ty+1,flag);
		move(tx,ty-1,flag);
	}
	return sum;
}
int main()
{
	cin>>n>>m;
	
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	scanf("%1d",&a[i][j]);
	
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	if(uni[i][j]==0)//如果這個點不屬于已經判斷的任何聯通塊
	ans[++k]=bread(i,j);//第k個連通圖有多少塊
	
	while(m--)
	{
		int ix,iy;
		cin>>ix>>iy;
		cout<<ans[uni[ix-1][iy-1]]<<endl;
		//ix-1,iy-1屬于第幾個聯通圖，第幾個連通圖有多少塊磚 
	}
	return 0;
}