BFS

背景

输入n*m矩阵，然后从（1，1）搜索至（n,m)

输出最短路径

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

注意

DP一般能解决搜素问题

所有边等权重时，才能用BFS求最短路

算法核心

初始化一个queue

while(!queue.isempty()){

t=queue.front();

//拓展 t

}

插曲

C++ pair 用法

类模板：template<class T1,class T2> struct pair

参数：T1是第一个值的数据类型，T2是第二个值的数据类型。

功能：pair将一对值(T1和T2)组合成一个值，

        这一对值可以具有不同的数据类型（T1和T2），

        两个值可以分别用pair的两个公有函数first和second访问。

pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员

C++ memset用法（初始化）

memset(dp,0,sizeof(dp));  

int类型的变量一般占用4个字节，对每一个字节赋值0的话就变成了“00000000 00000000 000000000 00000000” （即10进制数中的0）

赋值为-1的话，放的是 “11111111 11111111 11111111 11111111 ”（十进制的-1）

我们在很多程序中都会看到memset(a,127,sizeof(a));这样的代码，127是什么特别的数字呢？通过基础的进制转换可以得知127的二进制表示是01111111，那么在dp数组里放的内容就是“01111111 01111111 01111111 01111111”，（10进制的2139062143），这样就实现了将数组里的全部元素初始化为一个很大的数的目的了，在最短路径问题以及其他很多算法中都是需要用到的。值得注意的是，int类型的范围为2^31-1，大约是2147483647的样子（如果我没有记错的话），所以初始化int类型的数组也可以使用127这个数值。

如果是128呢？因为128的二进制是10000000，那么放的内容就是10000000 10000000 10000000 10000000，经过计算可得这个数是-2139062144。这样就可以将数组初始化为一个很小的数了。

题解（c++）

模拟队列版

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=110;

typedef pair<int,int>PII;//数对，相当于二维数组 
int n,m;
int g[N][N];// map
int d[N][N];// distance
PII q[N*N];// 模拟队列 

int bfs(){
    int hh=0,tt=0;
    memset(d,-1,sizeof d);//全部初始化为-1 
    d[0][0]=0;
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    while(hh<=tt){
        auto t=q[hh++];//出队 
        for(int i=0;i<4;i++){
            int x=t.first+dx[i],y=t.second+dy[i];//四个方向遍历 
            if(x>=0&&y>=0&&y<m&&x<n&&g[x][y]==0&&d[x][y]==-1){//非路障且未经过 
                d[x][y]=d[t.first][t.second]+1;//距离加一 
                q[ ++tt ]={x,y};//新元素入队 
            }
        }
    }
    return d[n-1][m-1];//返回终点最短路径长度 
} 


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

队列版

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N=110;
typedef pair<int,int> PII;
int g[N][N],d[N][N];
int m,n;
queue <PII> que;

int bfs(){
    memset(d,-1,sizeof d);//初始化地图 
    d[0][0]=0;//起点标记 
    que.push({0,0});//起点入队 
    int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};//定义四个方向
    while(que.size()){//当队列不为空时 
        auto t=que.front();//取出队头
        que.pop();//队头出队 
        for(int i=0;i<4;i++){
            int x=t.first+dx[i],y=t.second+dy[i];//四个方位遍历获取当前坐标 
            if(x<n&&y<m&&x>=0&&y>=0&&g[x][y]==0&&d[x][y]==-1){
                d[x][y]=d[t.first][t.second]+1;//距离+1 
                que.push({x,y});//将当前坐标入队 
            }
        } 
    } 
    return d[n-1][m-1];
}

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

DFS

普遍来说，BFS要比DFS简单很多，虽然两个都是常规的搜索方法，但是BFS通常用于求最短路之类的最优解，有属于它的模板，而且，只需要简单的进行剪枝（例如记录走过的路，下次不再走），

而DFS不一样，DFS不只是简单求最优解，而是求加上了不少限制条件的答案，因此难度系数剧增，很多时候我们最开始能想到的是通过暴力的枚举来进行求解，但是这样的时间成本过高，因此我们通常选择对不同的体型进行对应的剪枝，

例如本题

背景

小狗在一个古老的迷宫里发现了一根骨头，这让他非常着迷。然而，当他把它捡起来时，迷宫开始摇晃，小狗能感觉到地面在下沉。他意识到骨头是个陷阱，他拼命想走出这个迷宫。迷宫是一个长方形，大小为N乘M。迷宫里有一扇门。开始时，门是关闭的，它会在第T秒打开一小段时间（不到1秒）。因此，小狗必须准确地在第T秒到达门口。在每秒钟内，他可以将一个街区移动到上、下、左、右相邻街区中的一个。一旦他进入一个街区，这个街区的地面就会开始下沉，并在下一秒钟消失。他不能在一个街区停留超过一秒钟，也不能搬进去过的街区。可怜的小狗能活下来吗？请帮帮他。

输入

输入由多个测试用例组成。每个测试用例的第一行包含三个整数N、M和T（1<N，M<7；0<T<50），分别表示迷宫的大小和门打开的时间。接下来的N行给出了迷宫布局，每行包含M个字符。字符是以下之一：“X”：一块墙，小狗不能进入；“S”：小狗的起点；‘D’：门；或者“.”：一个空块。输入以三个0结束。此测试用例不被处理。

输出

对于每个测试案例，如果小狗能活下来，在一行中打印“是”，否则打印“否”。

样例

4 4 5

S.X.

..X.

..XD

....

3 4 5

S.X.

..X.

...D

0 0 0

->

NO

YES

题解

核心代码

void dfs(int si,int sj,int Tn){
    if(si>N||sj>M||si<=0||sj<=0)return ;
    if(Tn==T&&si==di&sj==dj)escape=1;
    if(escape)return ;//一旦找出解，全部返回，不再判断 
    int temp=T-Tn-abs(si-di)-abs(sj-dj);
    //检测时间和哈夫曼距离奇偶性是否相同
    if(temp<0||temp%2==1) return ;//奇偶性剪枝
    for(int i=0;i<4;i++){
        if(map[si+vec[i][0]][sj+vec[i][1]]!='X'){
            map[si+vec[i][0]][sj+vec[i][1]]='X';//常规剪枝
            dfs(si+vec[i][0],sj+vec[i][1],Tn+1);
            map[si+vec[i][0]][sj+vec[i][1]]='.';//回溯
        }
    }
    return;
}

剪枝与回溯解释

常规剪枝操作有

if(si>N||sj>M||si<=0||sj<=0)return ;

map[si+vec[i][0]][sj+vec[i][1]]='X';这里的剪枝，类似于BFS当中的记录是否访问过

if(M*N>=T)dfs(si,sj,0);

判断总距离最大值是否大于时间

特殊剪枝

奇偶性剪枝：

因此在迭代中可以随时检验奇偶性是否相同，以此实现剪枝目的

回溯

从DFS每次出发作为视角，每次路走不通的时候，我们都需要把走过的路设置为未走过，因此才不会影响下一次的搜索。（恢复现场）

只有当DSF->return之后才会执行刷新路径操作

附加（简单题）：全排列问题

input：3

output: 123|321|132|213|231|312

n位数字，从第一位开始填，每一位不能和之前的相同

类似树形结构,但不是层层遍历，而是追求深度，一条路走到黑，如果走不通，就回溯，回到上一个状态，看看能不能走另一条路

#include <iostream>

using namespace std;
const int N=10000;
int m,n;
int map[N];
int re[N];
void dfs(int n,int m){
    if(m==n+1){
        for(int i=1;i<=n;i++){
            cout<<re[i]<<" ";
            re[N]=0;
        }
        cout<<endl;
        return;
    }else{
        for(int j=1;j<=n;j++){
        if(map[j]!=0){
            re[m]=j;
            map[j]=0;//标记走过
            dfs(n,m+1);
            map[j]=j;    //回溯
            }
        }
    }
}

int main(){
    while(cin>>n){
        for(int i=1;i<=n;i++)map[i]=i;//初始化
        dfs(n,1);
    }
    return 0;
}

题目很经典也很简单，适合了解回溯，了解DFS运行机制

最近发生了很多事情，有好有坏，庆幸在不开心的时候有人陪伴倾诉，庆幸在开心的时候没有过度喜悦。不管是科研、开发、绩点、比赛and so on，希望每件事都能够做到不让自己后悔