题目描述

有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。

你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身

思路

一开始打了一个暴力广搜，然后超时了70分
后面发现可以之做一边，把每一部分可以走到的格数先算出来，再输出就可以了

#include <stdio.h>
#include <queue>
#include <string>
using namespace std;
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
int a[1001][1001],ans,t=0;
int f[1000001],fl[1001][1001],n,m;
int bfs(int x,int y)
{
    queue<int> tx;
    queue<int> ty;
    tx.push(x);
    ty.push(y);
    fl[x][y]=t;
    while (!tx.empty())
    {
        int xx=tx.front(),yy=ty.front();
        tx.pop(); ty.pop();
        for (int i=1;i<=4;i++)
            if (xx+dx[i]>=1&&xx+dx[i]<=n&&yy+dy[i]>=1&&yy+dy[i]<=n&&a[xx+dx[i]][yy+dy[i]]!=a[xx][yy]&&fl[xx+dx[i]][yy+dy[i]]==0)
            {
                tx.push(xx+dx[i]);
                ty.push(yy+dy[i]);
                fl[xx+dx[i]][yy+dy[i]]=t;
                ans++;
            }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        char ch[1001];
        scanf("%s",ch);
        for (int j=0;j<n;j++)
            if (ch[j]=='1') a[i][j+1]=1;
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (fl[i][j]==0)
            {
                t++;
                ans=1;
                bfs(i,j);
                f[t]=ans;
            }
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",f[fl[x][y]]);
    }
}