//给一个地图由起点到点最短步数 .通*不通
//标准广搜模版题
#include<bits/stdc++.h>
using namespace std;
char mp[103][103];          //地图大小
int vis[103][103];          //访问标记
typedef struct point pt;    //点重命名
struct point{int x;int y;}; //点结构体
typedef pair<pt,int> p;     //pair存点与距离，方便队列
int dx[4]={0,0,-1,1};       //X偏移，上下左右
int dy[4]={1,-1,0,0};       //Y偏移，上下左右
int main(){
    int n,m;cin>>n>>m;      //地图大小
    pt s,g;                 //定义起点与终点
    for(int i=1;i<=n;i++){  //遍历行
        for(int j=1;j<=m;j++){  //遍历列
            cin>>mp[i][j];      //输入
            if(mp[i][j]=='s'){  //如果是起点
                s.x=i;      //记下X
                s.y=j;      //记下Y
            }
            if(mp[i][j]=='g'){//如果是终点
                g.x=i;      //记下X
                g.y=j;      //记下Y
            }

        }
    }
    queue<p>qu;             //开队列
    qu.push(p(s,0));        //压入起点
    while(!qu.empty()){     //非空
        pt nowp=qu.front().first;   //读出队首点
        int dis=qu.front().second;  //读出队首点到起点步数
        vis[nowp.x][nowp.y]=1;      //打上已访问标记
        qu.pop();                   //弹出队首
        if(nowp.x==g.x&&nowp.y==g.y){cout<<dis<<endl;return 0;}     //到终点跳出
        for(int i=0;i<4;i++){   //未到终点则四个方向偏移
            pt newp;            //定义新点
            newp.x=nowp.x+dx[i];if(newp.x<1 || newp.x>n)continue;   //得新X，超限跳过
            newp.y=nowp.y+dy[i];if(newp.y<1 || newp.y>m)continue;   //得新Y，超限跳过
            if(vis[newp.x][newp.y]==0&&mp[newp.x][newp.y]!='*'){    //未访问且可行
                qu.push(p(newp,dis+1));                             //新点压入队列
            }
        }
    }
    cout<<"impossible"<<endl;   //队空都走不到，就肯定走不到了
    return 0;
}
/*
in
3 3
s..
...
g..
out
2
in
3 3
s..
**.
g..
out
6
in
3 3
s..
***
g..
out
impossible
*/

题意

给定一个有向无子环无重边的图，给定起点和终点，给定a,b,c三种路径长度，求最小次数ans，使得无论如何从a,b,c中选择ans次，均能在ans次之内走到终点

思路

1.预处理出某个点走a,b,c步后能否到达某个点 

2.从终点bfs，倒着扩展能到达的其他点，因为若一个点走a,b,c步后均能到达必胜点则从该点出发也能达到终点，且步数为能到达的必胜点中最大的+1

code

Sibling Rivalry

在上一篇的基础上，发现 BFS 只能对与边权相同的图求最短路。实际上，在这篇要记录的题目中可以知道一张图中如果只有两种边权，那么最短路也是可以用 BFS 来求的，并且时间复杂度较低。
题目：

达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。翰翰的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障，导致无法启动。电路板的整体结构是一个 $R$ 行 $C$ 列的网格$（R,C≤500）$，如下图所示。


每个格点都是电线的接点，每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后，它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。

达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。

注意：只能走斜向的线段，水平和竖直线段不能走。
输入格式

输入文件包含多组测试数据。

第一行包含一个整数 $T$ ，表示测试数据的数目。

对于每组测试数据，第一行包含正整数 $R$ 和 $C$ ，表示电路板的行数和列数。

之后R行，每行 $C$ 个字符，字符是"/“和”"中的一个，表示标准件的方向。
输出格式

对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。

如果无论怎样都不能使得电源和发动机之间连通，输出NO SOLUTION。
数据范围

$1≤R,C≤500,$

$1≤T≤5$

测评地址
解法：把网格图的每个格点看成节点，当想从一个节点走到别的节点上时，如果原图中的线路允许则边权为0，如果需要旋转则为1。此时，再用 BFS 来求最短路，不过在搜索树上，边权为0的点应该在边权为1的点前被扩展，因此采取双端队列，若边权为0，则插入队头，否则插入队尾。

注意：

1、输入的“\”和“/”的处理要细心！

2、其实图中有一些节点是永远不可能走到的，因为走一步横纵坐标均变化1，因此必须与起点奇偶性相同才可以，这样也可以判断 NO SOLUTION 的情况。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>

#define x first
#define y second

using namespace std;

const int N=510;

typedef pair<int ,int> pii;

int T;
int n,m;
deque<pii> q;
char g[N][N];
int dist[N][N];
bool v[N][N];

void bfs(){

    q.push_back({0,0});
    
    int dx[4]={-1,1,-1,1};
    int dy[4]={-1,-1,1,1};
    int ix[4]={-1,0,-1,0};
    int iy[4]={-1,-1,0,0};  //*details!!
    
    char s[5]="\\//\\";  //det!
    
    memset(v,0,sizeof(v));
    memset(dist,0x3f,sizeof(dist));
    dist[0][0]=0;
    
    while(q.size()){
        
        pii t=q.front(); //*
        q.pop_front(); //*
        
        //if(t.x==n && t.y==m) return ;
        if(v[t.x][t.y]) continue;
        v[t.x][t.y]=1;
        
        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>m) continue;
            
            int gx=t.x+ix[i],gy=t.y+iy[i];
            int w=(g[gx][gy]!=s[i]);
            int d=dist[t.x][t.y]+w;
            if(d<=dist[nx][ny]){
                dist[nx][ny]=d;
                if(!w) q.push_front({nx,ny});
                else q.push_back({nx,ny});
            }
        }
    }
    
}

int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>g[i];
        bfs();
        if((n+m)%2) cout<<"NO SOLUTION"<<endl;
        else cout<<dist[n][m]<<endl;
    }
    return 0;
}

上一篇搜索的博客讲了 BFS 一个经典的应用模型，这篇讲述另一个经典模型的一点小扩展。另一个 BFS 的经典应用模型是求一张具有相同边权的图上的单源点最短路，如果是多源点的最短路，实际上也是可以用 BFS 来解决的，

先看题目：
给定一个 $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$

测试地址
人话：求每一个0到离她最近的1的曼哈顿距离。
做法：将所有为零的点加入队列再进行 BFS 求最短路即可。

解释：BFS实际上就是最多在一颗搜索树的两层上扩展更新。而原先的单源点求最短路是以唯一的起点为根节点进行 BFS，在这道题里，我们可以不去管根节点是否只有一个，或者说加一个虚拟的超级根节点，她到每个0的边的权为0，然后再进行正常的 BFS 即可。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int,int> pii;

const int N=1010;

int g[N][N],n,m;
pii q[N*N];
int d[N][N];

void bfs(){
    int hh=0,tt=-1;
    memset(d,-1,sizeof(d));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(g[i][j]==1){
                d[i][j]=0;
                q[++tt]={i,j};
            }
    
    int dx[4]={0,1,0,-1};
    int dy[4]={-1,0,1,0};
            
    while(hh<=tt){
        pii t=q[hh++];
        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>m) continue;
                if(d[nx][ny]!=-1) continue;
                d[nx][ny]=d[t.x][t.y]+1;
                q[++tt]={nx,ny};
            }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%1d",&g[i][j]);
            
    bfs();
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            printf("%d ",d[i][j]);
        printf("\n");
    }
    
    return 0;
}