题解 P1141 【01迷宫】

· · 题解

水平不高，写这题时遇到不少问题，所以发个题解看看能不能帮到大家找到忽视的地方。

刚开始看到这题就觉得应该用宽搜来做，于是直接打了一个宽搜程序，如下：

#include<bits/stdc++.h>
using namespace std;
int _map[1001][1001];
bool flag[1001][1001];
struct mg
{
    int x,y;
}q[1000001];
//超时3个点 
int main()
{
    int sx,sy,i,j,n,m,l,nx,ny,k,f,r,sum;
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    char ch;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            cin>>ch;
            if(ch=='1') _map[i][j]=1;
            else _map[i][j]=0;
        }
    for(l=1;l<=m;l++)
    {
        cin>>sx>>sy;
        sum=1;
        f=1;
        r=1;
        q[f].x=sx;
        q[f].y=sy;
        memset(flag,true,sizeof(flag));
        flag[sx][sy]=false;
        while(f<=r)
        {
            for(k=0;k<4;k++)
            {
                nx=q[f].x+dx[k];
                ny=q[f].y+dy[k];
                if(flag[nx][ny]&&nx>=1&&nx<=n&&ny>=1&&ny<=n&&((_map[nx][ny]==0&&_map[q[f].x][q[f].y]==1)||(_map[nx][ny]==1&&_map[q[f].x][q[f].y]==0)))
                {
                    r++;
                    sum++;
                    flag[nx][ny]=false;
                    q[r].x=nx;
                    q[r].y=ny;
                }
            }
            f++;
        }
        cout<<sum<<endl;
    }
    return 0;
}

然后悲惨的超时3个点。。。很明显，这题数据很大，读一组查一遍必然爆炸。此时应该加以优化，于是就有了以下程序：

#include<bits/stdc++.h>
using namespace std;
char _map[1001][1001];//_map数组保存地图 
int flag[1001][1001],a[1000001];//a数组要开大一点，刚开始开a[1001]错了3个点 
//flag数组保存各个点所在的连通图，以及是否已经处理过，a数组保存各个连通图的大小
struct mg
{
    int x,y;
}q[1000001];
int main()
{
    int sx,sy,i,j,n,m,l,nx,ny,k,f,r,sum,d;
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};//四个方向
    scanf("%d %d",&n,&m);//n是正方形地图边长，m是数据组数 
    memset(a,0,sizeof(a));
    memset(flag,0,sizeof(flag)); //你可以无视这两行memset
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            cin>>_map[i][j];//读入地图 
    d=0;//d用来保存当前是在第几个连通图中 
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(flag[i][j]==0)//如果当前位置不在已知连通图中（还未处理过） 
            {
                d++;//记录当前所在连通图数 
                f=1;
                r=1;
                q[f].x=i;
                q[f].y=j;
                flag[i][j]=d;
                sum=1;//初始化
                while(f<=r)
                {
                    for(k=0;k<4;k++)
                    {
                        nx=q[f].x+dx[k];
                        ny=q[f].y+dy[k];
                        if(flag[nx][ny]==0&&nx>=1&&nx<=n&&ny>=1&&ny<=n&&((_map[nx][ny]=='1'&&_map[q[f].x][q[f].y]=='0')||(_map[nx][ny]=='0'&&_map[q[f].x][q[f].y]=='1')))
                        //如果新位置能走且在地图上 
                        {
                            r++;
                            sum++;//计数器累加 
                            flag[nx][ny]=d;//标记新位置在第d个连通图中 
                            q[r].x=nx;
                            q[r].y=ny;//更新位置 
                        }
                    }
                    f++;
                }
                a[d]=sum;//保存当前连通图能移动到多少格 
            }
    for(i=1;i<=m;i++)
    {
        cin>>sx>>sy;//读入询问 
        cout<<a[flag[sx][sy]]<<endl;//直接查找答案并输出 
    }
    return 0;
}

本人刚开始将数组开小了，然后WA 4个点满脸懵。思想借鉴吸取了之前的一些题解，就是将初始地图分割成一个个联通图。 注意：如果整张图全是1或全是0的话连通图数量会极大，数组开小会WA，直接一遍遍搜索会超时。

第一次发题解语言表述可能不好请多包涵。。。