dfs专题（记忆化搜索）P1141 01迷宫——洛谷（题解）

题目描述

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

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

输入格式

第一行为两个正整数 �,�n,m。

下面 �n 行，每行 �n 个字符，字符只可能是 00 或者 11，字符之间没有空格。

接下来 �m 行，每行两个用空格分隔的正整数 �,�i,j，对应了迷宫中第 �i 行第 �j 列的一个格子，询问从这一格开始能移动到多少格。

输出格式

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

输入输出样例

输入 #1复制

2 2
01
10
1 1
2 2

输出 #1复制

4
4

说明/提示

对于样例，所有格子互相可达。

• 对于 20%20% 的数据，�≤10n≤10；
• 对于 40%40% 的数据，�≤50n≤50；
• 对于 50%50% 的数据，�≤5m≤5；
• 对于 60%60% 的数据，�,�≤100n,m≤100；
• 对于 100%100% 的数据，1≤�≤10001≤n≤1000，1≤�≤1000001≤m≤100000。

想法：

这题也是dfs求连通块，不过细胞那题是求连通块的个数，这题是求一个连通块中有多少个块。代码如下。

代码：

#include<bits/stdc++.h>
using namespace std;
int ans;
char mg[1010][1010];//迷宫 
int n,m; 
int st[1010][1010];//状态数组 
int dx[]={0,0,1,-1};//四个方向 
int dy[]={1,-1,0,0};
void dfs(int x,int y){
    for(int i=0;i<4;i++){
        int xx=dx[i]+x;
        int yy=dy[i]+y;
        if(xx>n||xx<1||yy>n||yy<1) continue;//超范围 
        if(st[xx][yy]==1) continue;//走过了 
        if(mg[xx][yy]==mg[x][y]) continue;//走不了 
        st[xx][yy]=1;
        ans++;
        dfs(xx,yy);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>mg[i][j];
        }
    } 
    int a,b;
    while(m--){
        memset(st,0,sizeof(st));
        ans=1;
        cin>>a>>b;
        st[a][b]=1;
        dfs(a,b);
        cout<<ans<<endl;
    }
}

然而事情没有这么简单，这题这么写会超时，因为查询的次数太多了，查过的点还要重新计算答案，而且属于同一个联通块的点的答案还是一样的，这样就可以用到记忆化搜索。虽然这个也不是我推的，了解一下咯。它这记忆化也是蛮巧妙的吧，用一个二维数组存坐标，一个二维数组存答案，就是直接将整个迷宫的答案都搜一遍并存起来，后面直接查询。而且它搜联通块和搜答案是一起的，就是记忆化和搜答案是一起的。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans=1;
int Ans[1010][1010];
int zb[1000010][2];//坐标 
int st[1010][1010];
char mg[1010][1010];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int x,int y){
    for(int i=0;i<4;i++){
        int xx=dx[i]+x;
        int yy=dy[i]+y;
        if(xx>n||xx<1||yy>n||yy<1) continue;//超范围 
        if(mg[x][y]==mg[xx][yy]) continue;//走不到 
        if(st[xx][yy]==1) continue;//走过了 
        ans++;
        st[xx][yy]=1;
        zb[ans][0]=xx;//存坐标 
        zb[ans][1]=yy;
        dfs(xx,yy);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cin>>mg[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(st[i][j]==0){//搜连通块 
                st[i][j]=1;
                ans=1;
                zb[1][0]=i;
                zb[1][1]=j;
                dfs(i,j);
                for(int k=1;k<=ans;k++){//存答案 
                    Ans[zb[k][0]][zb[k][1]]=ans;
                }
            }
        }
    }
    int a,b;
    while(m--){
        cin>>a>>b;
        cout<<Ans[a][b]<<endl;
    }
}

注意：

存图的时候看看给的图有没有连起来，这样判断数组用int还是char。