BFS及其变形

相较于深度搜索的一条路走到黑，广度搜索如其名是逐层搜索，一次把整一层搜完。我们用一个队列来实现，每次取出队头，对于队头状态的所有分支，把沿着分支所能达到的下一个状态（如果这个状态没被访问过或者可以形成更优的解）插入队尾，直到队列为空。

复习：#150 骑士游历

一个比较典型的棋盘问题，题目先规定了大致的方向，否则的话，应该有8个方向进行遍历；

先规定一个next数组，表示走到下一个点需要的运算；

用book来表示是否已经走过；

当第一次走到终点的时候直接输出；

否则搜索完毕之后输出no solution；

#include <iostream>
using namespace std;
struct queue{
    int x;
    int y;
    int step;
}q[2510];
int next[4][2]={{2,1},{2,-1},{1,2},{1,-2}};
int book[51][51],nx,ny;
int main(){
    int head=1,tail=1,k,n,m;
    cin>>n>>m;
    book[1][1]=1,q[head].x =1;q[head].y=1,q[head].step =0;
    tail++;
    book[1][1]=0;
    k=0;
    while(head!=tail){
        for(int i=0;i<=3;i++){
            nx=q[head].x +next[i][0];
            ny=q[head].y +next[i][1];
            if(nx<1||nx>n||ny<1||ny>m) continue;
            if(book[nx][ny]==0){
               book[nx][ny]=1;
               q[tail].x =nx;
               q[tail].y =ny;
               q[tail].step =q[head].step +1;
               tail++;
            }
            if(nx ==n&&ny ==m){
                k=1;
                break;
            }
        }
        if(k==1) break;
        head++;
    }
    if(k==1) cout<<q[tail-1].step;
    else cout<<"No solution!";
    return 0;
}

给一道例题：矩阵距离（ch2501）

描述

给定一个N行M列的01矩阵 A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为：
dist(A[i][j],A[k][l])=|i-k|+|j-l|

输出一个N行M列的整数矩阵B，其中：
B[i][j]=min(1≤x≤N,1≤y≤M,A[x][y]=1)⁡{dist(A[i][j],A[x][y])}
即求与每个位置曼哈顿距离最近的1
N,M≤1000。

输入格式

第一行两个整数n,m。

接下来一个N行M列的01矩阵，数字之间没有空格。

输出格式

一个N行M列的矩阵B，相邻两个整数之间用一个空格隔开。

题目所求的意思就是 ：

离 （i，j) 这个点最近的 “1” 的曼哈顿距离；

然后输出这个矩阵；

我们先来思考一个问题：

给一个地图，全是0、1； 从一个起点出发，1表示不能走，0表示可以走。就可以求得起点到每一个可到达的点 的最小步数。

这样的问题我们形象的称它为倒水 、

于是本题便可以看作是一个有着多个起点（start) 的倒水问题；

在开始搜索前将所有的起点入队，然后用广搜。

当（x，y）这个节点第一次被访问时，便是离它最近的一个起点搜索到了它，这时候用的步数即为b[x][y];

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
char s[1020][1020];
int d[1020][1020], n, m;
queue<pair<int, int>> q;
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    memset(d, -1, sizeof(d));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (s[i][j] == '1') q.push(make_pair(i, j)), d[i][j] = 0;
    while (q.size()) {
        pair<int, int> now = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
            pair<int, int> next(now.first + dx[k], now.second + dy[k]);
            if (next.first<1 || next.second<1 || next.first>n || next.second>m) continue;
            if (d[next.first][next.second] == -1) {
                d[next.first][next.second] = d[now.first][now.second] + 1;
                q.push(next);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) printf("%d ", d[i][j]);
        puts("");
    }
}

BFS 的变形

例题：电路维修（ch2601）

这道题我们输入存储数据的时候有一个小技巧。

将每个电路图中的格点当作无向图中的节点。

对于两个节点x，y；

如果他们是在同一个格子的两个角上，就将它连一条边，如果x到y有一根导线，就将x到y的边权设为0

反之 如果是垂直的话，就设为1（这表示需要旋转一次才能够连上）

然后我们只需要求出从左上角到右下角的最短距离；

进行bfs的时候，我们将边权为0的边延伸出来的节点从队头入队；

为1的边延伸出来的节点从队尾入队；

因为如果这样做，我们就能保证每当一个节点第一次出队时，这时的总权值是最优解；

这种bfs变形叫做 双端队列；

#include <deque>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 506;
int r, c, d[N][N];
bool v[N][N];
char s[N][N];
vector<pair<pair<int, int>, int> > p[N][N];
deque<pair<int, int> > q;

void add(int x1, int y1, int x2, int y2, int z) {
    p[x1][y1].push_back(make_pair(make_pair(x2, y2), z));
}

void dlwx() {
    cin >> r >> c;
    for (int i = 1; i <= r; i++) cin >> (s[i] + 1);
    if ((r & 1) != (c & 1)) cout << "NO SOLUTION" << endl;
    for (int i = 0; i <= r; i++)
        for (int j = 0; j <= c; j++)
            p[i][j].clear();
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            if (s[i][j] == '/') {
                add(i - 1, j - 1, i, j, 1);
                add(i, j, i - 1, j - 1, 1);
                add(i, j - 1, i - 1, j, 0);
                add(i - 1, j, i, j - 1, 0);
            } else {
                add(i - 1, j - 1, i, j, 0);
                add(i, j, i - 1, j - 1, 0);
                add(i, j - 1, i - 1, j, 1);
                add(i - 1, j, i, j - 1, 1);
            }
    memset(d, 0x3f, sizeof(d));
    d[0][0] = 0;
    memset(v, 0, sizeof(v));
    q.clear();
    q.push_back(make_pair(0, 0));
    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop_front();
        v[x][y] = 1;
        if (x == r && y == c) {
            cout << d[r][c] << endl;
            return;
        }
        for (unsigned int i = 0; i < p[x][y].size(); i++) {
            int nx = p[x][y][i].first.first;
            int ny = p[x][y][i].first.second;
            int nz = p[x][y][i].second;
            if (v[nx][ny]) continue;
            if (nz) {
                if (d[nx][ny] > d[x][y] + 1) {
                    d[nx][ny] = d[x][y] + 1;
                    q.push_back(make_pair(nx, ny));
                }
            } else {
                if (d[nx][ny] > d[x][y]) {
                    q.push_front(make_pair(nx, ny));
                    d[nx][ny] = d[x][y];
                }
            }
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) dlwx();
    return 0;
}

优先队列 bfs 

其实双端队列算是优先队列dfs的一个特殊情况，因为权值只有0、1；

对于更加普适性的情况，我们可以用到优先队列；

这时优先队列是一个二叉堆，每次取出当前代价最小的节点进行扩展；

说白了：在最短路中就是堆优化的dijstra算法

 

双向的bfs

 就是有两个节点同时bfs，当一个点是第一次被搜索到既能被一个起点到达，也能被另一个点到达，则当前轮数就是最短的两点会和时间；