洛谷 P1141 01迷宫

ゝ一世哀愁。 2023-09-26 18:23 128阅读 0赞

> ### 题目描述 ###
> 
> 有一个仅由数字 0 与 1 组成的n×n 格迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上，同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。
> 
> 你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
> 
> ### 输入格式 ###
> 
> 有一个仅由数字 0 与 1组成的n×n 格迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上，同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。
> 
> 你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
> 
> ### 输出格式 ###
> 
> m 行，对于每个询问输出相应答案。
> 
> ### 输入输出样例 ###
> 
> **输入** 
> 
>     2 2
>     01
>     10
>     1 1
>     2 2
> 
> **输出** 
> 
>     4
>     4
> 
> ### 说明/提示 ###
> 
> 所有格子互相可达。
> 
> 对于 20% 的数据，n≤10；
> 
> 对于 40% 的数据，n≤50；
> 
> 对于50% 的数据，m≤5；
> 
> 对于60% 的数据，n,m≤100；
> 
> 对于 100% 的数据,n≤1000,m≤100000。

#include<bits/stdc++.h>
    using namespace std;
    const int M=1010;
    int n,m;
    int vis[M][M];
    bool mp[M][M];
    int xx[]={0,1,-1,0};
    int yy[]={1,0,0,-1};
    int color,cnt,ans[1000010];
    void bfs(int x,int y)
    {
    	queue<int>h;
    	queue<int>l;
    	h.push(x);
    	l.push(y);
    	vis[x][y]=color;
    	while(!l.empty())
    	{
    		for(int i=0;i<4;i++)
    		{
    			int dx=h.front()+xx[i];
    			int dy=l.front()+yy[i];
    			if(dx>=1&&dx<=n&&dy>=1&&dy<=n&&!vis[dx][dy]&&mp[dx][dy]!=mp[h.front()][l.front()])
    			{
    				h.push(dx);
    				l.push(dy);
    				vis[dx][dy]=color;
    			}
    		}
    		h.pop();
    		l.pop();
    		cnt++;
    	}
    }
    int main()
    {
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			char x;
    			cin>>x;
    			if(x=='1') mp[i][j]=1;
    			else mp[i][j]=0;
    		}
    	}
    	
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			if(!vis[i][j])
    			{
    				color++;
    				bfs(i,j);
    				ans[color]=cnt;
    				cnt=0;
    			}
    		}
    	}
    	
    	for(int i=1;i<=m;i++)
    	{
    		int x,y;
    		cin>>x>>y;
    		cout<<ans[vis[x][y]]<<endl;
    	}
    	return 0;
    }