天天看點
傳回

DFS與BFS

DFS與BFS

dfs又稱深度優先搜尋，即一路走到底（一個執着的人），當走到底（到達葉子節點）時要回溯。注：回溯不是直接回到頭，而是邊回去邊看，能不能再往下走，隻有當我們明确目前節點所有的路都走不通時才回退一步！

BFS又稱廣度優先搜尋，即一層一層的搜尋，隻有當每一層搜尋完之後才搜尋下一層（一個穩重的人）

對比：

​ 資料結構 空間 特點

DFS ： stack O(h)與高度成正比 不具有最短性

BFS： queue O(2的h次方) 具有最短性

都可以畫搜尋樹進行了解！

DFS：

DFS即暴力搜尋：最重要的是把順序弄清楚——要以一個怎樣的順序把所有方案周遊一遍，類似于樹的先序周遊

回溯鍵值

數字排列

如何用 dfs 解決全排列問題？

dfs 最重要的是搜尋順序。用什麼順序周遊所有方案。

對于全排列問題，以 n = 3 為例，可以這樣進行搜尋：

DFS與BFS
#include<iostream>

using namespace std;

const int N = 10;
int path[N];
bool vis[N];
int n;

void dfs(int u)
{
    if(u == n) //到達葉子節點(數字填完了)
    {
        for(int i = 0; i < n; i++) cout<<path[i]<<" ";
        cout<<endl;
    }
    // 枚舉所有方案 空位上可以選擇的數字為:1 ~ n
    for(int i = 1; i <= n; i++)
    {
        if(!vis[i]) //沒有被通路過
        {
            path[u] = i;
            vis[i] = 1; // 數字被使用，狀态修改
            dfs(u + 1); // 填下一位
            //(到達葉子節點要回溯時——恢複現場)
            vis[i] = false; // 恢複現場
            
        }
    }
}

int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

n皇後問題 

#include <iostream>
using namespace std;
const int N = 20; 

// bool數組用來判斷搜尋的下一個位置是否可行
// col列，dg對角線，udg反對角線
// g[N][N]用來存路徑

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u) {
    // u == n 表示已經搜了n行，故輸出這條路徑
    if (u == n) {
        for (int i = 0; i < n; i ++ ){
            for(int j = 0; j < n; j++){
                cout<<g[i][j];
            }
            puts("");
        }
        puts("");  // 換行
        return;
    }

    //對n個位置按行搜尋
    for (int i = 0; i < n; i ++ )
        // 剪枝(對于不滿足要求的點，不再繼續往下搜尋)  
        // udg[n - u + i]，+n是為了保證下标非負
        if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false; // 恢複現場 這步很關鍵
            g[u][i] = '.';

        }
}

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

    dfs(0);

    return 0;
}

DFS迷宮問題(求解方案數)

無障礙物：

#include<iostream>
using namespace std;
int count,n;
bool st[100][100];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void dfs(int x,int y){
    if(x == n && y == n)
    {
        count ++;
        return ;
    }
	
	for(int i = 0; i <= 3; i++) // 上下左右四個方向
	{
	    int ix = x + dx[i];
	    int iy = y + dy[i];
	    if(!st[ix][iy] && ix >=1 && iy >= 1 && ix <= n && iy <= n)
	    {
    	    st[ix][iy] = true;
    	    dfs(ix, iy);
    	    st[ix][iy] = false;
	    }

	}

}
int main(){
	cin>>n;
	st[1][1] = true; // 起點标記為1
	dfs(1,1);
	cout<<count<<endl;

	return 0;
} 

           
#include<iostream>
using namespace std;
int count,n;
bool st[10][10];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int qx[100],qy[100];//存坐标 
void dfs(int x,int y,int u){//u是第幾步 
	if(x==n&&y==n){//結束條件 
	count++; // 方案數
// 	for(int i=0;i<u;i++){
// 			cout<<'('<<qx[i]<<','<<qy[i]<<')';
// 	}
		return ;
	} 
	for(int i=0;i<=3;i++){//枚舉所有可能 情況 
	int ix=x+dx[i];
	int iy=y+dy[i];
		if(st[ix][iy]||ix<1||iy<1||ix>n||iy>n) continue;//判斷目前情況是否合法 剪枝
		qx[u]=ix;
		qy[u]=iy; 
		st[ix][iy]=true;
		dfs(ix,iy,u+1);
		st[ix][iy]=false;//恢複現場 
		
	}
}
int main(){
	cin>>n;
	st[1][1]=true;//注：标記好 
	qx[0]=1;
	qy[0]=1;
	dfs(1,1,1);
	cout<<count<<endl;
	return 0;
}

有障礙物：

DFS與BFS
#include<iostream>
using namespace std;

bool st[100][100]; // 标記位置是否被用過
bool map[100][100]; // 标記障礙物

// 上下左右四個方向
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int count; // 計數
int n, m, t;
int sx, sy, fx, fy; // 起點終點坐标：(sx,sy)(fx,fy)

void dfs(int x,int y){
    if(x == fx && y == fy)
    {
        count ++;
        return ;
    }
	
	for(int i = 0; i <= 3; i++) // 上下左右四個方向
	{
	    int ix = x + dx[i];
	    int iy = y + dy[i];
	    if(!st[ix][iy] && !map[ix][iy] && ix >=1 && iy >= 1 && ix <= n && iy <= m)
	    {
    	    st[ix][iy] = true;
    	    dfs(ix, iy);
    	    st[ix][iy] = false;
	    }

	}

}
int main(){
	cin>> n>> m>> t>> sx>> sy>> fx>> fy;
	while(t --) // 輸入障礙物
	{
	    int x, y;
	    cin>>x >> y;
	    map[x][y] = true; // 障礙物位置标記為1
	}
	st[1][1] = true; // 起點标記為1
	dfs(1,1);
	cout<<count<<endl;

	return 0;
}

單詞方陣

單詞接龍

加分二叉樹

蟲食算

BFS

最短路問題：寬搜的優勢是能找到最短（最小）路！（所有邊權重都一樣才可以用！）——一層一層的搜尋（類似于樹的層次周遊）。深搜可以保證我們走到終點，但不能確定是最短路。

搜尋過程（層次周遊）如下：

（1）從圖中的某個頂點出V發，通路V

（2）依次通路V的各個未曾通路過的鄰接點

（3）分别從這些鄰接點出發依次通路它們的鄰接點，并使“先被通路的頂點的鄰接點”先于“後被通路的頂點的鄰接點”被通路

（4）重複步驟（3）直至所有已被通路的頂點的鄰接點都被通路到

DFS與BFS

圖的BFS和樹幾乎一模一樣，唯一的差別是樹有根節點，而圖沒有，是以在周遊圖時要選一個根節點。下圖以A作為根節點：

DFS與BFS

D和E是不能颠倒過來的，因為我們先周遊到的頂點是B，下一次展開的時候必須找與B直接相連的節點，即必須在找與C相連的節點之前把所有與B相連的節點找出來，由于A和C都走過了，是以唯一能走的點就是D。是以B先走完！

DFS與BFS

BFS的資料結構實作形式是隊列，通過隊列儲存已被通路過的節點，利用其先進先出的特點：保證了先通路的頂點的鄰接點亦先被通路

即隊列保證了下圖中B的鄰接點比C的鄰接點要先出現：

DFS與BFS

填塗顔色

馬的周遊

走迷宮（acwing 844）

給定一個 n×mn×m 的二維整數數組，用來表示一個迷宮，數組中隻包含 00 或 11，其中 00 表示可以走的路，11 表示不可通過的牆壁。

最初，有一個人位于左上角 (1,1)(1,1) 處，已知該人每次可以向上、下、左、右任意一個方向移動一個位置。

請問，該人從左上角移動至右下角 (n,m)(n,m) 處，至少需要移動多少次。

資料保證 (1,1)(1,1) 處和 (n,m)(n,m) 處的數字為 00，且一定至少存在一條通路。

輸入格式

第一行包含兩個整數 nn 和 mm。

接下來 nn 行，每行包含 mm 個整數（00 或 11），表示完整的二維數組迷宮。

輸出格式

輸出一個整數，表示從左上角移動至右下角的最少移動次數。

資料範圍

1≤n,m≤1001≤n,m≤100

輸入樣例：

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

輸出樣例：
8

【參考代碼】

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

using namespace std;

typedef pair<int, int> PII; // 用pair來存儲坐标

const int N = 110;
// g[N][N]初始化輸入資料, d[N][N]目前位置到原點的距離
int g[N][N], d[N][N]; 
// 下一個節點可能的位置
 int dx[4] = {-1, 0, 1, 0};
 int dy[4] = {0, 1, 0, -1};
int n, m;

int bfs()
{
    queue<PII> q; // 隊列存儲通路過的點已經該頂點的鄰接點
    memset(d, -1, sizeof d); // 距離初始化為- 1表示沒有走過
    d[0][0] = 0;
    q.push({0,0}); // 開始時根節點先入隊
    
    while(q.size())
    {
        auto t = q.front(); // t指向隊頭元素(隊首元素還有用)
        q.pop(); // 隊頭元素出隊
        
        // 枚舉出隊的隊首元素的所有鄰接點
        for(int i = 0; i < 4; i ++)
        {
            int x = t.first + dx[i];
            int y = t.second + dy[i];
            // d[x][y] == -1 表示該位置還沒被通路過
            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1; // 距離加1
                q.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;        
}

數組模拟隊列：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110; 
typedef pair<int, int> PII;
int n, m;
int g[N][N];//存放地圖
int d[N][N];//存 每一個點到起點的距離
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//x 方向的向量和 y 方向的向量組成的上、右、下、左
PII q[N * N];//手寫隊列
int bfs()
{
    int hh = 0, tt = 0;
    q[0] = {0, 0};

    memset(d, - 1, sizeof d);//距離初始化為- 1表示沒有走過

    d[0][0] = 0;//表示起點走過了

    while(hh <= tt)//隊列不空
    {
        PII t = q[hh ++ ];//取隊頭元素

        for(int i = 0; i < 4; i ++ )//枚舉4個方向
        {
            int x = t.first + dx[i], y = t.second + dy[i];//x表示沿着此方向走會走到哪個點
            if(x >= 0 && x < n && y >= 0 && y < m && 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() << endl;

    return 0;
}

奇怪的電梯

字元串變換

機器人搬重物

memset()函數的使用

  1. memset()函數原型是: 
extern void *memset(void *buffer, int c, int count)        

  //buffer：為指針或是數組,

  //c：是賦給buffer的值,

  //count：是buffer的長度.

這個函數在socket中多用于清空數組.如:原型是:

memset(buffer, 0, sizeof(buffer))

2.memset 用來對一段記憶體空間（數組）進行初始化；

int arr[N][N];

memset(arr, -1, sizeof(arr));
注：memset()可以初始化整數數組，但是初始化的值隻能為0或者-1。
上一篇: 字元串比對
下一篇: 區間合并