解题报告 P1141 【01迷宫】广度优先搜索

2018-03-11 20:21:16


迷宫这个模型各位OIer见得可多了,一般是搜索类题目,同样地,这道题是一道巨坑浅显的广搜题

我们直接看判断条件:在当前点可以走到相邻的不同数字的点上去

这个题有多个询问,并且 $m\le100,000$ ,所以每次做一遍BFS肯定不现实(事实证明这样还是有 $70$ 分的),所以要用到记忆化搜索,这样才能减少时间开销。

记忆化搜索思想:已经搜到的联通块不必再搜,将处于相同联通块的格子用并查集并起来,即在之后的搜索中,一旦搜索到与当前状态的格子处于相同联通块的格子,则直接跳过,则一个联通块只会搜到一次。那么当一个点更新完时,与它相连的联通块的值(可以到达的点)一定和它一样,用vis数组存下来,这样可以用vis数组代替bool数组used(我的最初程序也用到了used,后来发现不需要,不知道bool数组调用时会不会稍微快一点),因此在之后vis不为0的点就不需要入队了。

说到used数组,有一个重要的点希望大家不要被坑了

就是不要在每次的bfs里都对used数组重置一遍,第一很费时间,第二,完全没有必要,第三,想打裸的BFS( $70$ 分)用used是需要每次重置的,因为每次相当于重新做了一遍,没有用到记忆化

另一个注意事项:在相邻格子遍历时,千万不要越界,所以大家看到我的判断条件比较长(其实一个for循环解决一切),多一个条件保险一些。

再一个注意事项,这个题的输入格式是字符形式,所以要考虑行末有没有'\n'(用cin当我没说,其实也可以过)要特意读入一下

剩下的就是考广搜的基本功啦


Code:

#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct point
{
    int x,y;
}t[1000005];
queue<point> q;
int a[1001][1001],vis[1001][1001],s[1000005];
int n,m,u[1001][1001];
int Find(int x)
{
    if(s[x]==x)
        return s[x];
    return s[x]=Find(s[x]);
}
void Union(int x,int y)
{
    s[Find(y)]=s[Find(x)];
    return ;
}
void turn(int x)//预处理坐标转换(用空间换时间)
{
    for(int i=1;i<=x;i++)
        for(int j=1;j<=x;j++)
            u[i][j]=(i-1)*n+j;
    return;
}
int bfs(int x,int y)
{
    int ans=0,k=0;
    point p;
    p.x=x;
    p.y=y;
    q.push(p);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        t[++k].x=p.x;
        t[k].y=p.y;
        if(vis[p.x][p.y])
        {
            ans+=vis[p.x][p.y];
            continue;
        }
        ans++;
        if(!vis[p.x-1][p.y]&&p.x>1&&a[p.x-1][p.y]!=a[p.x][p.y])
            if(Find(u[p.x-1][p.y])!=Find(u[p.x][p.y]))
            {
                p.x--;
                q.push(p);
                p.x++;
                Union(u[p.x-1][p.y],u[p.x][p.y]);
            }
        if(!vis[p.x+1][p.y]&&p.x<n&&a[p.x+1][p.y]!=a[p.x][p.y])
            if(Find(u[p.x+1][p.y])!=Find(u[p.x][p.y]))
            {
                p.x++;
                q.push(p);
                p.x--;
                Union(u[p.x+1][p.y],u[p.x][p.y]);
            }
        if(!vis[p.x][p.y-1]&&p.y>1&&a[p.x][p.y-1]!=a[p.x][p.y])
            if(Find(u[p.x][p.y-1])!=Find(u[p.x][p.y]))
            {
                p.y--;
                q.push(p);
                p.y++;
                Union(u[p.x][p.y-1],u[p.x][p.y]);
            }
        if(!vis[p.x][p.y+1]&&p.y<n&&a[p.x][p.y+1]!=a[p.x][p.y])
            if(Find(u[p.x][p.y+1])!=Find(u[p.x][p.y]))
            {
                p.y++;
                q.push(p);
                p.y--;
                Union(u[p.x][p.y+1],u[p.x][p.y]);
            }
    }
    for(int i=1;i<=k;i++)
        vis[t[i].x][t[i].y]=ans;
    vis[x][y]=ans;
    return ans;
}
int main()
{
    memset(vis,0,sizeof(vis));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n*n;i++)
        s[i]=i;
    turn(n);
    char c;
    scanf("\n");
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            c=getchar();
            a[i][j]=c-'0';
        }
        scanf("\n");
    }
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",bfs(x,y));
    }
    return 0;
}