Yao Lirong's Blog

P1141 01迷宫

NOI
2019/07/04

题目来源：洛谷P1141 01迷宫

BFS找连通块

  1. 连通块肯定还是DFS找得快，因为一开始不知道什么是连通块所以写了个BFS

  2. 搜索连通块不需要记录从某一个点出发最远能到达哪个点（BFS搜索最短距离），只需要记录从某一个点出发一共经过了多少个符合条件的点就行了（BFS搜索连通块），因为如果A和B联通，B和C联通，那么A和C必然联通，所以一次搜索能达到的所有点必定在同一个连通块内

  3. 如果对于每个查询我们都搜索一遍的话肯定会超时，所以我们用vis数组记录下来一次搜索中所有经过的点所在的（必定是同一个）连通块的序号，ans数组记录相应序号的连通块中共有几个点，下次如果询问的点已经被搜索过就可以免去搜索直接输出答案了。

  4. 程序向本来被封死的地方走了一步，可能是初始化的问题。初始化就别用那些花里胡哨的句子了，还是老老实实写for循环吧，反正时间空间够用，别的句子太容易出错

  5. 莫名其妙输出来几十万的数据，估计是爆内存了，数组一定要根据题目要求开得足够大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
struct node{
    int x,y;
};
int m,n,question[100005][2],dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}},vis[1003][1003],ans[100005],connect=1; bool maze[1003][1003];
///question 存储了每组询问的起点坐标
///vis = 0 代表这个点没走过，现在不在任何一个连通块里面；vis = x (x>0) 代表这个点走过了，并且在x号连通块里面；这个数组一定要开大，只开到1003是不行的，必须要开到和question一个数量级
///ans 存储每个连通块里面共有几个点
///maze 存储这个迷宫
///connect 代表各个连通块的序号
int bfs(int, int); bool legal(node, node);
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            char a;
            cin>>a;
            if(a=='0') maze[i][j]=0;
            else if(a=='1') maze[i][j]=1;
        }///因为每个输入之间是不空格的，所以用char来输入做一个巧妙的处理
    for(int i=1;i<=m;i++)
        cin>>question[i][0]>>question[i][1];
    ///初始化最后出了很大问题，还是用最保险的for循环
    for(int i=0;i<100005;i++) ans[i]=1;
    for(int i=0;i<1003;i++) for(int j=0;j<1003;j++) vis[i][j]=0;

    for(int i=1;i<=m;i++)
        cout<<bfs(question[i][0],question[i][1])<<endl;
    return 0;
}
bool legal(node now, node next)
{
    ///这里不需要分情况讨论“如果 now==0 则必须 next==1” 或相反，只需要确保now和next的值不同就行了
    return maze[now.x][now.y]!=maze[next.x][next.y] &&
    next.x>=1 && next.x<=n && next.y>=1 && next.y<=n && vis[next.x][next.y]==0;
}
int bfs(int x, int y)
{
    queue <node> q;
    node start;
    start.x = x; start.y = y;
    if(vis[start.x][start.y]==0){///如果这个点不在现有的任何一个连通块内，则进入队列，开始bfs
        vis[start.x][start.y] = connect;
        q.push(start);
    }
    else return ans[vis[start.x][start.y]];///如果这个点在某个连通块内，则直接输出此连通块对应的结果

    while(!q.empty()){
        node now = q.front();
        q.pop();

        for(int i=0;i<4;i++){
            node next;
            next.x = now.x + dir[i][0];
            next.y = now.y + dir[i][1];

            if(legal(now,next)){
                vis[next.x][next.y] = connect;///记录下来点next属于连通块connect
                ans[connect]++;///连通块connect中总点数+1
                q.push(next);
            }
        }
    }
    return ans[connect++];///所有属于connect的点都搜完了，返回答案，并使connect++，表示接下来要扫的是新的连通块
}

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/2019-07-04-P1141-01%E8%BF%B7%E5%AE%AB/

Publish date：July 4th 2019, 12:00:00 am

Update date：October 7th 2019, 5:02:22 am

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

CATALOG
  1. 1. BFS找连通块
Total : 66
2023
2022
2021
2020
2019
NOI CS2112 Logistics Cornell Review CS3110 Manual Journal Tsinghua Book