题解 P1141 【01迷宫】

LightningUZ · 2018-10-06 13:10:00 · 题解

怎么都是深搜的题解，我一开始还以为广搜是错的……

（DEV-C++：那你还调了那么多次……）

贴代码（思路见注释）:

#include<bits/stdc++.h>
using namespace std;
bool mp[1010][1010];
int vis[1010][1010];
int q[1010*1010][2];
/*
手写队列比STL快
q[i][0]表示x坐标
q[i][1]表示y坐标
千万不要用struct
要用就用class
struct在栈中存储,栈空间小 
*/ 

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};//四个方向扩展 

int tot=1;
int ans[1010*1010];
/*
标记是第几个联通块 
ans[i]保存第i个联通块的大小 
*/
int n,m;
/*
check判断是否在迷宫中,
且没有被访问过
判断是否访问过，只需看
vis[x][y]是不是tot即可 
*/
bool check(int x,int y)
{
    if (vis[x][y]==tot) return false;
    if (x<1 or x>n) return false;
    if (y<1 or y>n) return false;
    return true;
}
void bfs(int x,int y)
{
    int head=1,tail=1;
    q[tail][0]=x;
    q[tail][1]=y;
    vis[x][y]=tot; 
    tail++;
    //x,y入队 
    int cnt=1;//计数菌
    /*
    计数君初始为1,因为算上了
    传进来的x,y 
    */ 
    while(head<tail)
    {
        int hx=q[head][0];
        int hy=q[head][1];
        //hx,hy取队首,即q[head] 
        for(int i=0;i<4;i++)
        {
            int tx=hx+dx[i];
            int ty=hy+dy[i];
            //队列扩展 
            if (check(tx,ty) and mp[tx][ty]!=mp[hx][hy])
            {
                q[tail][0]=tx;
                q[tail][1]=ty;
                vis[tx][ty]=tot;//标记联通块 
                tail++;
                cnt++;//计数菌++ 
            }
        }
        head++;
    }
    ans[tot]=cnt;//标记第tot个联通块 
    tot++;
}
int main()
{
    memset(vis,-1,sizeof(vis));
    //记得初始化 
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        char tmp[1010];
        scanf("%s",tmp+1);//从1开始 
        for(int j=1;j<=n;j++)
        {
            mp[i][j]=tmp[j]-'0';
        }
    }
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int tmp=vis[x][y];//联通块编号 
        if (tmp==-1)//说明这个联通块没有被BFS过 
        {
            bfs(x,y);
            //那就BFS一遍 
            printf("%d\n",ans[vis[x][y]]);
        }
        else//被算过,就直接输答案 
        {
            printf("%d\n",ans[vis[x][y]]);
        }
    } 
    exit(0);
}