(宽度优先搜索)bfs（包含所有模型）

持续更新中

首先,我们要了解什么是bfs:

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型.

其实bfs是盲目的搜索周围,知道搜到目的地为止

我们可以用一张图来了解bfs:

首先从A出发,查看所有能到达的点,然后把周围的都加入队列,然后取出队头,在找出所有能到达的点

并加入队列

这样一定能到达所有的点

 BFS(int x) {	queue q; // 定义队列q
	将x入队; 
	vis[x] = true; //vis数组为bool型数组，用来判断该点是否加入过。
	while (q非空) { //队列不为空就一直循环
	    取出q的队首元素t进行访问; 
	     for (从t出发可达到的所有顶点i)  //将t能达到的点枚举加入到队列
	     if (!vis[i]) {  //判断i是否加入过队列
	        将i入队;
	        vis[i] = true; //设置i已经加入队列了
	}
}
}

直接看一个题吧

农夫约翰有一片 N∗M 的矩形土地。

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。

在bfs中，如果对于之后的某个合法位置，应该入队，那么标记数组会有两种方法，第一种是在每次取队首元素的时候，标记已经遍历过当前点了，还有一种方法是在入队之后就马上标记。之前没太注意这个，但是是完全不一样的，对于8个方向，比如向左走一步是合法的，然后不马上标记的话，例如当前向下和向左都是合法的，那么当向下走时候(比如向下先入队了)，那么向左走还会被记录一次

#include 
using namespace std;
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const int maxn = 2e3 + 6;

int n, m;
int mp[maxn][maxn];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
queue >q;

void bfs(int x, int y){
    mp[x][y] = 0;
    while(q.size()) q.pop();
    q.push({x, y});
    while(q.size()){
        auto now = q.front(); q.pop();
        for(int i = 0;i < 8;++i){
            int nx = now.first + dx[i];
            int ny = now.second + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || mp[nx][ny] == 0) continue;
            q.push({nx, ny});
            mp[nx][ny] = 0;
        }
    }
}

int main(){
    sd(n), sd(m);
    for(int i = 0;i < n;++i){
        for(int j = 0;j < m;++j){
            char c; cin >> c;
            if(c == 'W') mp[i][j] = 1;
            else mp[i][j] = 0;
        }
    }
    int cnt = 0;
    for(int i = 0;i < n;++i){
        for(int j = 0;j < m;++j){
            if(mp[i][j] == 1){
                bfs(i, j);
                cnt++;
            }
        }
    }
    cout << cnt << endl;

    return 0;
}

山峰和山谷

FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。

为了能够对旅程有一个安排，他想知道山峰和山谷的数量。

给定一个地图，为FGD想要旅行的区域，地图被分为 n×n 的网格，每个格子 (i,j) 的高度 w(i,j) 是给定的。

若两个格子有公共顶点，那么它们就是相邻的格子，如与 (i,j) 相邻的格子有(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)。

我们定义一个格子的集合 S 为山峰（山谷）当且仅当：

S 的所有格子都有相同的高度。
S 的所有格子都连通。
对于 s 属于 S，与 s 相邻的 s′ 不属于 S，都有 ws>ws′（山峰），或者 ws 如果周围不存在相邻区域，则同时将其视为山峰和山谷。
你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。

输入格式
第一行包含一个正整数 n，表示地图的大小。

接下来一个 n×n 的矩阵，表示地图上每个格子的高度 w。

思路:看一个格子周围是否有比他大的小的

#include
#include
using namespace std;

const int N = 1010;
int g[N][N];
struct node{
    int px,py;
};
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int n;
int w[N][N];
int vis[N][N];

int cnt1=0,cnt2=0;
    
void bfs(int x,int y ){
    vis[x][y]=1;
    int h = w[x][y];
    queueq;
    q.push({x,y});
    int flag1=0,flag2=0;
    while(q.size()){
        auto t = q.front();
        q.pop();
        for(int i=0;i<8;i++){
            int nx = t.px+dx[i];
            int ny = t.py+dy[i];
            
            if(nx<0||nx>=n||ny<0||ny>=n)continue;
            
            if(h>w[nx][ny]) flag1=1;
           else if(h>n;
    for(int i=0;i>w[i][j];
        }
    }

    for(int i=0;i 


  
 
 1   2   3   4   5   6   7  
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #
   #---#########---#####---#---#
 4 #   #   |   |   |   |   #   #
   #############################
           (图 1)

   #  = Wall   
   |  = No wall
   -  = No wall
 
 
 
   
 
 
方向：上北下南左西右东。
 图1是一个城堡的地形图。
 
 
请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。
 
 
城堡被分割成 m∗n个方格区域，每个方格区域可以有0~4面墙。
 
 
注意：墙体厚度忽略不计。
 
 
输入格式
 第一行包含两个整数 m 和 n，分别表示城堡南北方向的长度和东西方向的长度。
 
 
接下来 m 行，每行包含 n 个整数，每个整数都表示平面图对应位置的方块的墙的特征。
 
 
每个方块中墙的特征由数字 P 来描述，我们用1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和。
 
 
例如，如果一个方块的 P 为3，则 3 = 1 + 2，该方块包含西墙和北墙。
 
 
城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。
 
 
输入的数据保证城堡至少有两个房间。
 
 
思路:我们可以用二进制判断该位置有不有墙,
 
看代码吧
 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef pair PII;

const int N = 55, M = N * N;

int n, m;
int g[N][N];
PII q[M];
bool st[N][N];

int bfs(int sx, int sy)
{
    int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

    int hh = 0, tt = 0;
    int area = 0;

    q[0] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        PII t = q[hh ++ ];
        area ++ ;

        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b]) continue;
            if (g[t.x][t.y] >> i & 1) continue;//如果有,为一,因为1,2,4,8,的二进制,所以很简单的能判断

            q[ ++ tt] = {a, b};
            st[a][b] = true;
        }
    }

    return area;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> g[i][j];

    int cnt = 0, area = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (!st[i][j])
            {
                area = max(area, bfs(i, j));
                cnt ++ ;
            }

    cout << cnt << endl;
    cout << area << endl;

    return 0;
}


 
最短路模型
 
利用bfs打印路径的问题
 
题目描述： 
 
 
 

 给定一个 n×n 的二维数组，如下所示：
 
 
int maze[5][5] = {
 
 
0, 1, 0, 0, 0,
 
 
0, 1, 0, 1, 0,
 
 
0, 0, 0, 0, 0,
 
 
0, 1, 1, 1, 0,
 
 
0, 0, 0, 1, 0,
 
 
};
 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
 
 
数据保证至少存在一条从左上角走到右下角的路径。
 
 
直接上代码吧：
 
#include
#include
#include
#define x first
#define y second
using namespace std;
const int N = 1010;
int g[N][N];
int n;
typedef pairpii;
int vis[N][N];
int dis[N][N];
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
pii path[N][N];
void bfs(int sx,int sy){
    vis[sx][sy]=1;
    dis[sx][sy]=0;
    queueq;
    q.push({sx,sy});
    path[sx][sy] = {0,0};
    while(q.size()){
        auto t = q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int nx = t.x+dx[i],ny = t.y+dy[i];
            if(nx<0||nx>=n||ny<0||ny>=n||vis[nx][ny])continue;
            if(dis[nx][ny]!=0x3f3f3f3f||g[nx][ny]==1)continue;
            vis[nx][ny]=1;
            dis[nx][ny] = dis[t.x][t.y]+1;
            
            q.push({nx,ny});
            path[nx][ny] = t;
        }
    }
}
int main(){
    memset(dis,0x3f,sizeof dis);
    cin>>n;
    for(int i=0;i>g[i][j];
        }
    }
    
    bfs(n-1,n-1);
 pii end(0, 0);

    while (true)
    {
        printf("%d %dn", end.x, end.y);
        if (end.x == n - 1 && end.y == n - 1) break;
        end = path[end.x][end.y];
    }
  
}
 
 题目描述：
 
 
 

 农民 John 有很多牛，他想交易其中一头被 Don 称为 The Knight 的牛。
 
 
这头牛有一个独一无二的超能力，在农场里像 Knight 一样地跳（就是我们熟悉的象棋中马的走法）。
 
 
虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个 x，y 的坐标图来表示。
 
 
这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了 The Knight 的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。
 
 
现在你的任务是，确定 The Knight 要想吃到草，至少需要跳多少次。
 
 
The Knight 的位置用 K 来标记，障碍的位置用 * 来标记，草的位置用 H 来标记。
 
 
这里有一个地图的例子：
 
 
             11 | . . . . . . . . . .
              10 | . . . . * . . . . . 
               9 | . . . . . . . . . . 
               8 | . . . * . * . . . . 
               7 | . . . . . . . * . . 
               6 | . . * . . * . . . H 
               5 | * . . . . . . . . . 
               4 | . . . * . . . * . . 
               3 | . K . . . . . . . . 
               2 | . . . * . . . . . * 
               1 | . . * . . . . * . . 
               0 ----------------------
                                     1 
                 0 1 2 3 4 5 6 7 8 9 0 
 The Knight 可以按照下图中的 A,B,C,D… 这条路径用 5 次跳到草的地方（有可能其它路线的长度也是 5）：
 
 
             11 | . . . . . . . . . .
              10 | . . . . * . . . . .
               9 | . . . . . . . . . .
               8 | . . . * . * . . . .
               7 | . . . . . . . * . .
               6 | . . * . . * . . . F<
               5 | * . B . . . . . . .
               4 | . . . * C . . * E .
               3 | .>A . . . . D . . .
               2 | . . . * . . . . . *
               1 | . . * . . . . * . .
               0 ----------------------
                                     1
                 0 1 2 3 4 5 6 7 8 9 0
 注意： 数据保证一定有解。
 
 
思路：就是一个板子题
 
#include
#define x first
#define y second
using namespace std;

const int N = 200;
char g[N][N];
char vis[N][N];
int dis[N][N];
int n,m;
int dx[8]={2,1,-1,-2,-2,-1,1,2};//方向数组
int dy[8]={1,2,2,1,-1,-2,-2,-1};//方向数组
typedef pairpii;
int res=0;
void bfs(int sx,int sy){
    queueq;
    q.push({sx,sy});
    dis[sx][sy]=0;
    while(q.size()){
        auto t = q.front();
        q.pop();
        for(int i=0;i<8;i++){
            int nx = t.x+dy[i];
            int ny = t.y+dx[i];
            if(nx>=n||nx<0||ny<0||ny>=m)continue;
            if(vis[nx][ny])continue;
            vis[nx][ny]=1;
            if(g[nx][ny]=='*'){
                continue;
            }
            if(g[nx][ny]=='H'){
                res= dis[t.x][t.y]+1;
               return;
            }
            dis[nx][ny] = dis[t.x][t.y]+1;
            q.push({nx,ny});
        }
    }
}

int main(){
    cin>>m>>n;
    int x,y;
    for(int i=0;i>g[i][j];
            if(g[i][j]=='K'){
                x =i,y=j;
            }
        }
    }
    
  
    
    
    bfs(x,y);
    cout< 
 

 农夫知道一头牛的位置，想要抓住它。
 
农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。
 
农夫有两种移动方式：
 
从 X 移动到 X−1 或 X+1，每次移动花费一分钟
 从 X 移动到 2∗X，每次移动花费一分钟
 假设牛没有意识到农夫的行动，站在原地不动。
 
农夫最少要花多少时间才能抓住牛？
 
 
思路：看代码，其实就是bfs的板子题
 
#include
#include
using namespace std;

const int N = 1e5+10;
int g[N],vis[N];
int dis[N];
  int n,k;
int dx[] = {-1,1,2};
void bfs(int s){
    queueq;
    q.push(s);
    dis[s]=0;
    vis[s]=0;
    while(q.size()){
        auto t = q.front();
        q.pop();
            for(int i=0;i<3;i++){
                int nx=0;
                 if(i==2){
                      nx = 2*t;
                 }
                 else{
                      nx = t+dx[i];
                 }
                 if(nx<0||nx>=100010||vis[nx])continue;
                 vis[nx]=1;
                 dis[nx] = dis[t]+1;
                 if(nx==k)return;
                 q.push(nx);
            }
    }
}

int main(){
  
    cin>>n>>k;
    if(n==k){
        cout<<0< 
多源最短路模型 
 
 
 思路：AcWing 173. 矩阵距离 - AcWing
 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef pair PII;

const int N = 1010, M = N * N;

int n, m;
char g[N][N];
PII q[M];
int dist[N][N];

void bfs()
{
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    memset(dist, -1, sizeof dist);

    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (g[i][j] == '1')
            {
                dist[i][j] = 0;
                q[ ++ tt] = {i, j};
            }

    while (hh <= tt)
    {
        auto t = q[hh ++ ];

        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 1 || a > n || b < 1 || b > m) continue;
            if (dist[a][b] != -1) continue;

            dist[a][b] = dist[t.x][t.y] + 1;
            q[ ++ tt] = {a, b};
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%s", g[i] + 1);

    bfs();

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ ) printf("%d ", dist[i][j]);
        puts("");
    }

    return 0;
}