题目大意

---

 题目描述

有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。

输入格式 

第1行为两个正整数n,m。
下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。
接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。

输出格式

m行，对于每个询问输出相应答案。

输入输出样例

输入 #1

2 2
01
10
1 1
2 2

输出 #1

4
4

---

三份代码

#1 70pts做法(暴搜)

//3个点TLE
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct Pos
{
    int x,y;
};
queue <Pos> q;
int n,m,x,y,tx,ty,ans,ask_a,ask_b;
char mp[1001][1001];
bool vis[1001][1001];
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
int bfs(int sx,int sy)
{
    q.push((Pos){sx,sy});
    vis[sx][sy]=true;
    while(!q.empty())
    {
        x=q.front().x; 
        y=q.front().y;
        q.pop();
        for(int i=0;i<4;i++)
        {
            tx=x+dx[i];
            ty=y+dy[i];
            if(tx<=0||tx>n||ty<=0||ty>n) continue;
            if(vis[tx][ty]==true||mp[tx][ty]==mp[x][y]) continue;
            ans++;
            q.push((Pos){tx,ty});
            vis[tx][ty]=true;
        }
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>mp[i][j];
    for(int i=1;i<=m;i++)
    {
        memset(vis,false,sizeof(vis));
        ans=0;
        cin>>ask_a>>ask_b;
        cout<<bfs(ask_a,ask_b)+1<<endl;
    }
    return 0;
}

#2 70pts做法(暴搜+连通块标记)

//先输入后计算+标记方法错误
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct Pos
{
    int x,y;
};
queue <Pos> q,bk;
int n,m,x,y,tx,ty,ans,ask_a,ask_b;
char mp[1001][1001];
bool vis[1001][1001];
int book[1001][1001];
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
int bfs(int sx,int sy)
{
    q.push((Pos){sx,sy});
    bk.push((Pos){sx,sy});
    vis[sx][sy]=true;
    while(!q.empty())
    {
        x=q.front().x; 
        y=q.front().y;
        q.pop();
        for(int i=0;i<4;i++)
        {
            tx=x+dx[i];
            ty=y+dy[i];
            if(tx<=0||tx>n||ty<=0||ty>n) continue;
            if(vis[tx][ty]==true||mp[tx][ty]==mp[x][y]) continue;
            ans++;
            q.push((Pos){tx,ty});
            bk.push((Pos){tx,ty});
            vis[tx][ty]=true;
        }
    }
    while(!bk.empty())
    {
        book[bk.front().x][bk.front().y]=ans;
        bk.pop();
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>mp[i][j];
    cin>>ask_a>>ask_b;
    cout<<bfs(ask_a,ask_b)+1<<endl;
    for(int i=2;i<=m;i++)
    {
        ans=0;
        memset(vis,false,sizeof(vis));
        cin>>ask_a>>ask_b;
        if(book[ask_a][ask_b]!=0) cout<<book[ask_a][ask_b]+1<<endl;
        else cout<<bfs(ask_a,ask_b)+1<<endl;
    }
    return 0;
}

#3 AC做法(暴搜+连通块标记+先计算后访问)

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
struct Pos
{
    int x,y;
};
queue <Pos> q,bk; //STL队列
int n,m,x,y,tx,ty,ans,ask_a,ask_b;
char mp[1001][1001]; //存储地图
bool vis[1001][1001]; //存储访问情况
int book[1001][1001]; //存储连通计算后的值
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1}; //四个方向
void bfs(int sx,int sy)
{
    q.push((Pos){sx,sy});
    bk.push((Pos){sx,sy});
    vis[sx][sy]=true;
    while(!q.empty())
    {
        x=q.front().x; 
        y=q.front().y;
        q.pop();
        for(int i=0;i<4;i++)
        {
            tx=x+dx[i];
            ty=y+dy[i];
            if(tx<=0||tx>n||ty<=0||ty>n) continue;
            if(vis[tx][ty]==true||mp[tx][ty]==mp[x][y]||book[tx][ty]!=0) continue;
            ans++;
            q.push((Pos){tx,ty});
            bk.push((Pos){tx,ty});
            vis[tx][ty]=true;
        }
    }
    while(!bk.empty())
    {
        book[bk.front().x][bk.front().y]=ans;
        bk.pop();
    }
    ans=0; //每次都要清零
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>mp[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(book[i][j]==0) bfs(i,j); //先计算后访问
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&ask_a,&ask_b);
        printf("%d\n",book[ask_a][ask_b]+1); 
    }
    return 0;
}

---

总结

本题坑点

#1 数据规模大。
#2 答案ans的清零。
#3 连通块的几录。
#4 重复的搜索。
#5 计算、访问的先后顺序。

---

本题难度 普及/提高-