P1141 01迷宫

洛谷 DFS 优化 C++ 所有文稿

题目描述

有一个仅由数字$0$与$1$组成的$n \times n$格迷宫。若你位于一格$0$上，那么你可以移动到相邻$4$格中的某一格$1$上，同样若你位于一格$1$上，那么你可以移动到相邻$4$格中的某一格$0$上。

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

输入输出格式

输入格式：

第$1$行为两个正整数$n,m$。

下面$n$行，每行$n$个字符，字符只可能是$0$或者$1$，字符之间没有空格。

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

输出格式：

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

输入输出样例

输入样例

2 2
01
10
1 1
2 2

输出样例

4
4

说明

所有格子互相可达。

对于$20\%$的数据，$n≤10$；

对于$40\%$的数据，$n≤50$；

对于$50\%$的数据，$m≤5$；

对于$60\%$的数据，$n≤100,m≤100$；

对于$100\%$的数据，$n≤1000,m≤100000$。

解

主要注意的是一个优化问题

一开始用BFS写，其实本质上是求连通块，所以两种算法都可以，但是都遇到了有三个测试点超时的问题

#include <iostream>
#include <cmath>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
int n,m,cnt=0;
bool t[1010][1010],step[1010][1010];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
void dfs(int x,int y){
    for(int j=0;j<4;j++) {
        int yy=y+dir[j][0],xx=x+dir[j][1];
        if (yy>0&&yy<=n&&xx>0&&xx<=n){
            if (t[y][x]!=t[yy][xx]&&step[yy][xx]){
                cnt++;
                step[yy][xx]=false;
                dfs(xx,yy);
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            char c;
            cin>>c;
            if (c=='1') t[i][j]=true;
            else t[i][j]=false;
        }
    }
    for(int i=0;i<m;i++){
        memset(step,true,sizeof(step));
        cnt=1;//包括起点在内
        int x1,y1;
        cin>>y1>>x1;
        step[y1][x1]=false;//注意起点的标记
        queue<pair<int,int> > qu;
        qu.push(make_pair(x1,y1));
        while(!qu.empty()){//bfs
            int x=qu.front().first,y=qu.front().second;
            qu.pop();
            for(int j=0;j<4;j++) {
                int yy=y+dir[j][0],xx=x+dir[j][1];
                if (yy>0&&yy<=n&&xx>0&&xx<=n){
                    if (t[y][x]!=t[yy][xx]&&step[yy][xx]){
                        cnt++;
                        step[yy][xx]=false;
                        qu.push(make_pair(xx,yy));
                    }
                }
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

在深搜的过程中加入了已搜索的标记

#include <iostream>
#include <cmath>
#include <string>
#include <string.h>
#include <cstdio>
using namespace std;
int n,m,cnt=1;
bool t[1010][1010],step[1010][1010];
int a[1010][1010];//序号记录
int ma[1000010];//序号为in的连通块，连通块数量为ma[in]
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
void dfs(int x,int y,int num){
    for(int j=0;j<4;j++) {
        int yy=y+dir[j][0],xx=x+dir[j][1];
        if (yy>0&&yy<=n&&xx>0&&xx<=n){
            if (t[y][x]!=t[yy][xx]&&step[yy][xx]){
                cnt++;
                step[yy][xx]=false;
                a[yy][xx]=num;//标记序号
                dfs(xx,yy,num);
            }
        }
    }
}
int main(){
    memset(a,-1,sizeof(a));
    memset(step,true,sizeof(step));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            char c;
            cin>>c;
            if (c=='1') t[i][j]=true;
            else t[i][j]=false;
        }
    }
    for(int i=0;i<m;i++){
        cnt=1;//包括起点在内
        int x1,y1;
        scanf("%d%d",&y1,&x1);
        if (a[y1][x1]>0) printf("%d\n",ma[(a[y1][x1])]);
        else{
            step[y1][x1]=false;//注意起点的标记
            a[y1][x1]=i+1;
            dfs(x1,y1,i+1);
            ma[i+1]=cnt;
/*
这是之前的一个做法，直接在序号标记数组里记录连通块数量，但还是超时，所以改成了标号，根据标号查找联通量
            for(int in=1;in<=n;in++){
                for(int jn=1;jn<=n;jn++){
                    if (!step[in][jn]) a[in][jn]=cnt;
                }
            }
*/
            printf("%d\n",cnt);
        }
    }
    return 0;
}