MOOC算法学习笔记 - 深度优先搜索（一）

##

例题一 城堡问题

//1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次

接触的第一个深搜代码：

#include<iostream>
#include<stack>
#include<cstring>    //memset函数所在库
using namespace std;
int color[60][60];    //存放每个点的颜色编号
int room[60][60];    //存放每个房间的墙壁信息
int roomNum =  0;    
int R,C;
int roomArea,maxRoomArea= 0;    //每个房间的大小和最大房间大小
void Dfs(int i,int k){        //深搜函数
    if(color[i][k])        //如果颜色不为0 说明已设置过 直接return
        return;
    ++roomArea;        //每进行一个Dfs，即搜过一个房间，即面积+1
    color[i][k] = roomNum;    //用房间编号来编颜色
    if((room[i][k] & 1) == 0)    //决定下一步往哪走 
        Dfs(i,k-1);
    if((room[i][k] & 2) == 0)
        Dfs(i-1,k);
    if((room[i][k] & 4) == 0)
        Dfs(i,k+1);
    if((room[i][k] & 8) == 0)
        Dfs(i+1,k);
}
int main()
{
    cin >> R >> C;
    for(int i=1; i <= R; i++)
        for(int j = 1; j <= C; j++)
           cin >> room[i][j];        //存下房间信息搜索都搜到底 即是一个房间
    memset(color,0,sizeof(color));    //对color数组全部初始化为0
    for(int i = 1; i <= R; i++)    //两个for循环遍历每一个点
        for(int j = 1; j <= C; j++)
            if(!color[i][j]){        //如果color为0 即没有搜过 执行此步 
                roomNum++;    //每一次这样的
                roomArea = 0;    //每个房间面积初始为0 将在Dfs函数中增加面积
                Dfs(i,j);
                maxRoomArea = max(roomArea,maxRoomArea);    //更新最大面积
            }
    cout << roomNum << endl;
    cout <<maxRoomArea << endl;
    return 0;
}

> 2018/4/5反思：

1.  对main里遍历每个房间的for里面，初始化不清楚，
2.  写dfs函数时 返回条件都不记得了！！
3.  通过进制运算的还不会！

> 讲一下&运算符 A = 0011 1100 B = 0000 1101

—————– A&B = 0000 1100 A|B = 0011 1101 A^B = 0011 0001 ~A = 1100 0011

在上面的题目中 1的二进制数为0000 0001 2为0000 0010 4为0000 0100 8为0000 1000
将room[i][k]&2 ==0 即代表room[i][k] 的二进制数的第2位不为1 （&的含义其实就是如果二进制对应位数都是1才为1
有0则为0）即没这堵墙

例题二 踩方格

——————————————– 一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b. 走过的格子立即塌陷无法再走第二次；
c. 只能向北、东、西三个方向走；

请问：如果允许在方格矩阵上走n（n <= 20）步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。

---

（1）
下面的代码其实记忆递归型动规
但是也可以理解为图的深搜

#include<iostream>
#include<cstring>
using namespace std;
int visited[30][50];
int ways(int i, int j, int n){
    if(n==0)
        return 1;
    visited[i][j] = 1;
    int num = 0;
    if(!visited[i+1][j]){
        num+=ways(i+1,j,n-1);
    }
    if(!visited[i][j-1]){
        num+=ways(i,j-1,n-1);
    }
    if(!visited[i][j+1]){
        num+=ways(i,j+1,n-1);
    }
    visited[i][j] = 0;
    return num;
}
int main()
{
    int n;
    cin >> n;
    memset(visited,0,sizeof(visited));
    cout << ways(0,25,n) << endl;
    return 0;
}

4/5 反思：

1.  很多深搜的套路都忘了，在求次数的问题中 一般边界条件都是return 1
2.  记得vis记忆化搜索和回溯。
3.  sum时三种走法（即三个dfs的总和）。

（2）
递推思路如下：
f[i]代表走i步的方法数；
思路一：（这种思路是网上搜到的，引出了思路二）
1.第i步向北走，有f[i-1]种方法；
2.第i-1步向北走的，第i步可以向东西走，那么有2f[i-2]种方法；
3.第i-1步向北走的有f[i-2]种，第i-1步向东或者西走，然后第i步不向北走有f[i-1]-f[i-2]种；
最终有f[i]=f[i-1]+2f[i-2]+(f[i-1]-f[i-2])种方法；
思路二：（其实就是思路一化简）
1.第i步至少可以向两个方向移动有2f[i-1]种方法；
2.第i-1步向北的，第i步多一种方法，就是f[i-2]种；
最终有2f[i-1]+f[i-2]种方法；

#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
        int n,i,f[25]={1,3};  
        cin>>n;  
        for(i=2;i<=n;i++)  
        {  
                f[i]=2*f[i-1]+f[i-2];   //f[i]=f[i-1]+2*f[i-2]+(f[i-1]-f[i-2])  
        }  
        cout<<f[n]<<endl;  
}  

（3）
dp[i][0]表示可以走i步且旁边两个砖块没有塌陷。

dp[i][1]表示可以走i步且旁边两个砖块有一个有塌陷。

#include<cstdio> 
#include<cstring> 
#include<cmath> 
#include<string> 
#include<algorithm> 
using namespace std;
int dp[21][2]={0}; 
int main()
{ 
int n; 
scanf("%d",&n); 
dp[1][0]=3;
dp[1][1]=2; 
for(int i=2;i<=n;i++){ 
    dp[i][1]=dp[i-1][0]+dp[i-1][1]; 
    dp[i][0]=dp[i-1][0]+2*dp[i-1][1]; 
} 
printf("%d",dp[n][0]); 
return 0; 
}

例题三 寻路问题

—————————————- N个城市，编号1到N。城市间有R条单向道路。 每条道路连接两个城市，有长度和过路费两个属性。 Bob只有K块钱，他想从城市1走到城市N。
问最短共需要走多长的路。
如果到不了N，输出-1
2<=N<=100 0<=K<=10000 1<=R<=10000 每条路的长度 L, 1 <= L <= 100 每条路的过路费T , 0<= T <= 100

sample input K N R s1 e1 L1 R1

5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2 sample
output 11

---

思路：
需要用一个邻接表来存放数据，用动态数组 vector< vector >G(110); 来表示邻接表，实质上这是一个二维数组，G[s] 是一维数组，输入的每个下标是起点。
优化的方法：

1.可行性剪枝
如果走的这条路花的钱已经大于所有的钱 即跳出此路
2.最优性剪枝
如果走的这条路的长度已经大于最短的路， 即跳出此路
3.保存中间结果 进行最优性剪枝
如果在相同的节点，之前来过 ，之前在这个节点走的路很短，且在二者所花钱一样，那么就跳出此路。

#include<iostream>
#include<cstring>
#include<vector>    //动态数组
using namespace std;
int K,N,R;
struct Road{       //含路的三个信息  类似于图中的边
    int d,L,t;
};
vector< vector<Road> >G(110);    //用vector定义的二维数组
int minL[110][10010];    //存放某个节点所走过的最短路
int minLen;
int totalLen;
int totalCost;
int visited[110];    //存放某个节点是否走过
void Dfs(int s){
    if( s==N ){                    //起点==终点  即搜索完毕
        minLen = min(minLen,totalLen);    //刷新minLen
        return ;
    }
    for(int i = 0; i < G[s].size(); i++){    //遍历一维G[s]数组的每一个数
        Road r = G[s][i];                 //这里是指遍历G[s]中的每一个G[s][i]
        if(totalCost + r.t > K)    //（剪枝）如果花的钱大于总钱数 跳出
            continue;
        if(!visited[r.d]){        //只有没被访问过的才进去
            if(r.L + totalLen >= minLen)    //（剪枝）如果走的路已经大于最短路径 跳出
                continue;
            if(totalLen + r.L >= minL[r.d][totalCost + r.t])
                continue;                    //（剪枝）如果这个点相同钱数比以前要走的路多 跳
            minL[r.d][totalCost + r.t] = totalLen + r.L;    //更新每个点已走的路
            totalLen += r.L;        //这路走了 开始增加信息
            totalCost += r.t;
            visited[r.d] = 1;
            Dfs(r.d);        //遍历下一个节点，即Road中的终点r.d;
            visited[r.d] = 0;    //要注意 记得换其他路的时候把已尝试的路信息减掉
            totalLen -= r.L;
            totalCost -= r.t;
        }
    }
}
int main()
{
    cin >> K >> N >> R;
    for(int i=0; i < R; i++){        //读入路的信息
        int s;    
        Road r;
        cin >> s >> r.d >> r.L >> r.t;
        if( s != r.d)
            G[s].push_back(r);        //c++ 在动态数组末尾添加值
    }
    memset(visited, 0, sizeof(visited));
    totalLen = 0;
    for(int i= 0; i < 110; i++)     //将minL（存放每个点经历的最短路）初始化为无穷大
        for(int j = 0; j < 10001; j++)
            minL[i][j] = 1 << 30;

    minLen = 1 << 30;    //最短路初始化 为无穷大
    totalCost = 0;
    visited[1] = 1;    //之前要把此路设置成走过
    Dfs(1);
    if(minLen < (1 << 30))
        cout << minLen << endl;
    else
        cout << "-1" << endl;
}