国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<kbd id="wtphj"></kbd>

<optgroup id="wtphj"></optgroup>

<b id="wtphj"><abbr id="wtphj"></abbr></b>

【數(shù)據(jù)結(jié)構(gòu)與算法】搜索算法（深度優(yōu)先搜索 DFS和廣度優(yōu)先搜索 BFS）以及典型算法例題

1年前作者：Chen_devy分類：Toy博客閱讀(30)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)與算法】搜索算法（深度優(yōu)先搜索 DFS和廣度優(yōu)先搜索 BFS）以及典型算法例題。希望對大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

【數(shù)據(jù)結(jié)構(gòu)與算法】系列文章鏈接: 【數(shù)據(jù)結(jié)構(gòu)與算法】遞推法和遞歸法解題（遞歸遞推算法典型例題）
【數(shù)據(jù)結(jié)構(gòu)與算法】系列文章鏈接: 【數(shù)據(jù)結(jié)構(gòu)與算法】C++的STL模板（迭代器iterator、容器vector、隊(duì)列queue、集合set、映射map）以及算法例題
【數(shù)據(jù)結(jié)構(gòu)與算法】系列文章鏈接: 【數(shù)據(jù)結(jié)構(gòu)與算法】二分查找算法

搜索算法（深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS）以及典型算法例題

深度優(yōu)先搜索（Depth First Search 簡稱 DFS）

注意：深度優(yōu)先搜索算法（DFS）的時(shí)間復(fù)雜度較高，深度優(yōu)先搜索是 O(n!) 的階乘級算法，它的效率非常低，在數(shù)據(jù)規(guī)模變大時(shí)，此算法就難以解決當(dāng)前的問題了。

DFS 的設(shè)計(jì)步驟

確定題目的狀態(tài)以及邊界
確定狀態(tài)的轉(zhuǎn)移方式
找到問題的出口，計(jì)數(shù)或某個(gè)狀態(tài)
設(shè)計(jì)搜索
DFS的通用模板

int check(這里輸入相關(guān)參數(shù)){
	if(condition)//括號中寫上對應(yīng)的滿足條件
		return 1;//滿足條件后輸出 1 
	return 0;
}
bool pd(輸入判斷的相關(guān)參數(shù)){
	//根據(jù)題中 進(jìn)行具體的操作
}

void dfs(int step)
{
        //判斷邊界pd()
        {
            //不在邊界內(nèi)，即回溯
        }
        //嘗試每一種可能
        {
               //滿足check條件

               //標(biāo)記

               //繼續(xù)下一步
               dfs(step+1)；

               //恢復(fù)初始狀態(tài)（回溯的時(shí)候要用到）
        }
}

深度優(yōu)先搜索（DFS）算法例題

例題一：N皇后問題

【數(shù)據(jù)結(jié)構(gòu)與算法】搜索算法（深度優(yōu)先搜索 DFS和廣度優(yōu)先搜索 BFS）以及典型算法例題,深度優(yōu)先,算法,寬度優(yōu)先,數(shù)據(jù)結(jié)構(gòu),矩陣
輸入示例：

輸出示例：

題目分析：

第一步：
設(shè)：當(dāng)前行為第一行，當(dāng)前列為第一列，從第一列開始搜索，即只能讓皇后從第一行放到第n行。
這樣做的好處是，我們不需要去判斷皇后是否同行，我們只需要去判斷皇后是否在斜線和是否同列就行。
判斷邊界
在當(dāng)前行，當(dāng)前列的位置上判斷是否滿足條件（也就是保證經(jīng)過這一點(diǎn)的行，列與斜線上都沒有兩個(gè)皇后），如果不滿足，跳到第五步（不符合邊界條件）
判斷條件為：
我們使用數(shù)值x[a]=i來表示第a個(gè)皇后的位置在第a行的第i列。
判斷是否同列的方法是：循環(huán)判斷x[a]==x[i]是否為真。
判斷是否在同一斜線上的方法：循環(huán)判斷abs(x[k]-x[i]) == abs(k-i) 是否為真
搜索過程
調(diào)用check()函數(shù)
如果完成（滿足）題意的任務(wù) 加一，就繼續(xù)調(diào)用函數(shù) 放下一個(gè)皇后
check()函數(shù)
如果搜索到第N+1行的時(shí)候。求得結(jié)果（可行方案數(shù)量）記錄加一。
當(dāng)前位置不滿足，進(jìn)行回溯。

邊界判斷函數(shù)PD(int k) 判斷是否越界：

int PD(int k)//邊界判斷
{

    for(int i=1; i<k; i++)
    {
        if(abs(k-i)==abs(x[k]-x[i]))
            return 0;
        else if (x[k]==x[i])
            return 0;
        //即判斷是否符合條件來放,i表示皇后所在的行數(shù)，x[i]表示所在的列數(shù)，
        //所以前面那個(gè)條件用來判斷兩個(gè)皇后是否在對角線上,后面用來判斷是否在同一列上。
        //行數(shù)不需要判斷，因?yàn)樗麄儽旧淼膇就代表的是行數(shù)
    }
    return 1;
}

檢查是否完成題中任務(wù)的函數(shù)check(int a)：

bool check(int a)
{

    if(a>n)
        sum++;
    else
        return 0;
    return 1;
}

深度優(yōu)先搜索的函數(shù) DFS(int a)：

void DFS(int a)
{
    if(check(a))
        return ;
    else
        for(int i=1; i<=n; i++)
        {
            x[a]=i;
                //第a個(gè)皇后放的列數(shù)
            if(PD(a))
                    //判斷是否能放這步
                DFS(a+1);
                    //能的話進(jìn)行下一個(gè)皇后的放置
            x[a]=i;
            else continue ;
                    //不能就下一列
        }
}

題解代碼示例：


#include <iostream>
#include <cstdio>
using namespace std;
int x[15] = {0};//數(shù)組稍微建立大一點(diǎn) 防止某些不影響結(jié)果的越界報(bào)錯(cuò)
int sum,n;//

int PD(int k)//邊界判斷
{

    for(int i=1; i<k; i++)
    {
        if(abs(k-i)==abs(x[k]-x[i]))
            return 0;
        else if (x[k]==x[i])
            return 0;
        //即判斷是否符合條件來放,i表示皇后所在的行數(shù)，x[i]表示所在的列數(shù)，
        //所以前面那個(gè)條件用來判斷兩個(gè)皇后是否在對角線上,后面用來判斷是否在同一列上。
        //行數(shù)不需要判斷，因?yàn)樗麄儽旧淼膇就代表的是行數(shù)
    }
    return 1;
}

//檢查
bool check(int a)
{

    if(a>n)
        sum++;
    else
        return 0;
    return 1;
}

void DFS(int a)
{
    if(check(a))
        return ;
    else
        for(int i=1; i<=n; i++)
        {
            x[a]=i;
                //第a個(gè)皇后放的列數(shù)
            if(PD(a))
                    //判斷是否能放這步
                DFS(a+1);
                    //能的話進(jìn)行下一個(gè)皇后的放置
            x[a]=i;
            else continue ;
                    //不能就下一列
        }
}
int main()
{
    cin>>n;
    //表示幾個(gè)皇后
    DFS(1);
    //每次都從第一個(gè)皇后開始
    cout<<sum<<endl;
    return 0;
}

例題二：路徑之謎問題

【數(shù)據(jù)結(jié)構(gòu)與算法】搜索算法（深度優(yōu)先搜索 DFS和廣度優(yōu)先搜索 BFS）以及典型算法例題,深度優(yōu)先,算法,寬度優(yōu)先,數(shù)據(jù)結(jié)構(gòu),矩陣
輸入示例：

4
2 4 3 4
4 3 3 3

輸出示例;

0 4 5 1 2 3 7 11 10 9 13 14 15

題目分析：
方法一：采用逆推法，逆向思維，從終點(diǎn)開始走，每走一格拔下來一個(gè)箭（采用方法一判斷條件方便）
方法二：走一格射兩個(gè)箭。

設(shè)當(dāng)前位置為第一行，當(dāng)前列為第一列從左上角開始搜索（尋路）。
判斷邊界：
在當(dāng)前行，當(dāng)前列的位置上判斷是否滿足條件，若不滿足條件跳到第五步。
判斷條件：
flag[x][y]==1標(biāo)記數(shù)組已經(jīng)被走過
x<1 || x>n || y<1 || y>n分別表示從左側(cè)走出方格、從右側(cè)走出方格、從上出走出方格、從下處走出方格
col[x]<=0箭用完了
rol[y]<=0箭用完了
搜索過程
調(diào)用check()函數(shù)。判斷是否走到終點(diǎn)，如果走到終點(diǎn)是否完成任務(wù)
check()函數(shù)：
如果當(dāng)搜索到x=n,y=n時(shí)，且箭靶上的箭都沒了
在當(dāng)前位置上不滿足條件的情況，進(jìn)行回溯，并且還原現(xiàn)場。

check()函數(shù)：判斷是否走到終點(diǎn)，如果走到終點(diǎn)是否完成任務(wù)

bool  check(int x, int y) //判斷走過的路徑的箭靶數(shù)是否與目標(biāo)相同
{
    if(x==n && y==n)//走到了終點(diǎn) 
    {
        for(int i=1; i<=n; i++)
        {//判斷每一列是否為零 
            if(col[i]!=0)
            {
                return false;
            }
            //如果箭靶上的數(shù)目不為0，根據(jù)逆推，我們通過當(dāng)前路徑得不到箭靶上的結(jié)果
        }
        for(int i=1; i<=n; i++)
        {//判斷每一行是否為零
            if(rol[i]!=0)
            {
                return false;
            }
            //如果箭靶上的數(shù)目不為0，根據(jù)逆推，我們通過當(dāng)前路徑得不到箭靶上的結(jié)果
        }
        //如果都為零了 就說明這條路對了  然后把這條路線輸出出來
        for(int i=0; i<res.size(); i++)
        {
            int x=res[i].first;
            //x 軸坐標(biāo)
            int y=res[i].second;
            //y 軸坐標(biāo)
            int sum=n*(x-1)+y-1 ;
            // 通過計(jì)算的到為題目要求的坐標(biāo)系
            cout <<sum<< " ";
        }
        
        cout << endl;
        return false;
        // 成功終止
    }
    //沒走到終點(diǎn)
    return true; //繼續(xù)搜索
    //關(guān)于終止還是繼續(xù)我們交給判定即可
}

判斷是否超出邊界的函數(shù)pd()：

//邊緣判斷條件
bool pd(int x2,int y2) //邊界判斷
{
    if(flag[x2][y2]==1)
        return 0;
    //已被走過，不能再走，超出邊界
    else if(x2<1)
        return 0;
    //從左側(cè)走出方格
    else if(x2>n)
        return 0;
    //從右側(cè)走出方格
    else if(y2<1)
        return 0;
    //從上側(cè)走出方格
    else if(y2>n)
        return 0;
    //從下側(cè)走出方格
    
    //剪枝
    else if(col[x2]<=0)
        return 0;
    //沒走到右下角，箭用完了
    else if(rol[y2]<=0)
        return 0;
    //沒走到右下角，箭用完了
    
    
    else return 1;
    //符合邊界條件，可以繼續(xù)執(zhí)行搜索
}

#include <bits/stdc++.h>

using namespace std;

struct PII
{
    int first;//x坐標(biāo)
    int second;//y坐標(biāo)
};

const int N = 30;
int rol[N];//行 也就是y軸
int col[N];//列 也就是x軸
int n;//格子數(shù) 長寬從1到n
bool flag[N][N]; //用來標(biāo)記是否走過
vector<PII> res;//


//---------圖的路徑搜索常用方向移動(dòng)表示-------

int dx[4]= {0,1,-1,0};
int dy[4]= {1,0,0,-1};
//我們做一下約定：
// 兩兩組合形成上下左右四個(gè)方向
//      1------------------> x
//      |
//      |
//      |
//      |
//      |
//      |
//      |
//      ↓
//      y

// dx[0]=0 dy[0]=1 那么代表向下的方向
// dx[1]=1 dy[1]=0 那么代表向右的方向
// dx[2]=-1 dy[0]=0 那么代表向左的方向
// dx[3]=0 dy[1]=-1 那么代表向上的方向

//--------------------------------------------

bool  check(int x, int y) //判斷走過的路徑的箭靶數(shù)是否與目標(biāo)相同
{
    if(x==n && y==n)//走到了終點(diǎn) 
    {
        for(int i=1; i<=n; i++)
        {//判斷每一列是否為零 
            if(col[i]!=0)
            {
                return false;
            }
            //如果箭靶上的數(shù)目不為0，根據(jù)逆推，我們通過當(dāng)前路徑得不到箭靶上的結(jié)果
        }
        for(int i=1; i<=n; i++)
        {//判斷每一行是否為零
            if(rol[i]!=0)
            {
                return false;
            }
            //如果箭靶上的數(shù)目不為0，根據(jù)逆推，我們通過當(dāng)前路徑得不到箭靶上的結(jié)果
        }
        //如果都為零了 就說明這條路對了  然后把這條路線輸出出來
        for(int i=0; i<res.size(); i++)
        {
            int x=res[i].first;
            //x 軸坐標(biāo)
            int y=res[i].second;
            //y 軸坐標(biāo)
            int sum=n*(x-1)+y-1 ;
            // 通過計(jì)算的到為題目要求的坐標(biāo)系
            cout <<sum<< " ";
        }
        
        cout << endl;
        return false;
        // 成功終止
    }
    //沒走到終點(diǎn)
    return true; //繼續(xù)搜索
    //關(guān)于終止還是繼續(xù)我們交給判定即可
}


//邊緣判斷條件
bool pd(int x2,int y2) //邊界判斷
{
    if(flag[x2][y2]==1)
        return 0;
    //已被走過，不能再走，超出邊界
    else if(x2<1)
        return 0;
    //從左側(cè)走出方格
    else if(x2>n)
        return 0;
    //從右側(cè)走出方格
    else if(y2<1)
        return 0;
    //從上側(cè)走出方格
    else if(y2>n)
        return 0;
    //從下側(cè)走出方格
    
    //剪枝
    else if(col[x2]<=0)
        return 0;
    //沒走到右下角，箭用完了
    else if(rol[y2]<=0)
        return 0;
    //沒走到右下角，箭用完了
    
    
    else return 1;
    //符合邊界條件，可以繼續(xù)執(zhí)行搜索
}


void dfs(int x,int y)
{
    if(!check(x,y))
    {
        return ;
        //包含不符合規(guī)則的地方，回溯，用于剪枝
    }
    else
    {
        for(int i=0; i<4; i++)
        {
            int xt=dx[i]+x;
            int yt=dy[i]+y;
            if(!pd(xt,yt))
            {
                continue ;
                //不符合要求繼續(xù)換方向搜索
            }
            else
            {
                //因?yàn)橐M(jìn)行位置轉(zhuǎn)移，我們給它起個(gè)名字，叫作案現(xiàn)場
                //比如向下移動(dòng)
                flag[xt][yt]=true;
                col[xt]--;
                rol[yt]--;
                res.push_back({xt,yt});
                dfs(xt,yt);
                //搜索回溯后，因?yàn)闆]有找到正確答案，所以要回復(fù)作案現(xiàn)場，返回到搜索之前
                res.pop_back();
                flag[xt][yt]=false;
                col[xt]++;
                rol[yt]++;
            }
        }
    }
}

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> rol[i];
    for(int i=1; i<=n; i++)
        cin >> col[i];
    flag[1][1]=true;
    col[1]--;//先拔一根箭
    rol[1]--;//先拔一根箭
    res.push_back({1,1});
    dfs(1,1);
    return 0;
}

例題三：最大數(shù)字

【數(shù)據(jù)結(jié)構(gòu)與算法】搜索算法（深度優(yōu)先搜索 DFS和廣度優(yōu)先搜索 BFS）以及典型算法例題,深度優(yōu)先,算法,寬度優(yōu)先,數(shù)據(jù)結(jié)構(gòu),矩陣
輸入樣例：

123 1 2

輸出樣例：

【數(shù)據(jù)結(jié)構(gòu)與算法】搜索算法（深度優(yōu)先搜索 DFS和廣度優(yōu)先搜索 BFS）以及典型算法例題,深度優(yōu)先,算法,寬度優(yōu)先,數(shù)據(jù)結(jié)構(gòu),矩陣
題目分析：

從左到右以此判斷，從左邊開始枚舉。處理的時(shí)候的目的就是保證當(dāng)前正在處理的數(shù)盡可能的變大。
使用的時(shí)候?qū)τ谝粋€(gè)數(shù)要么使用方法一，要么使用方法二，因?yàn)樗鼈兪堑窒男Ч?br> 對于一個(gè)數(shù)字:
**操作二的使用情況：**如果這個(gè)數(shù)大于m（操作二的最大執(zhí)行次數(shù)）,那么就沒必要執(zhí)行操作二了，這樣反而讓這個(gè)數(shù)據(jù)更小。因此執(zhí)行操作二的條件是:x<m.
**操作一的使用情況：**如果這個(gè)數(shù)據(jù)x>=m我們就執(zhí)行操作一，一直加盡量加到9，那么需要進(jìn)行 9-x 次操作一。當(dāng)然可能此時(shí) 1 號操作并不足以讓我們將 x 變成 9，但我們還是使用剩余的全部的次數(shù)將其變大，也就是變?yōu)?code>x+t。因此，本次使用了操作一的次數(shù)為t=min(n,9-x).

題解代碼示例：

#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;

char c[20];
LL ans=0;

//n:1號操作剩余次數(shù)  m:2號操作剩余次數(shù)
int n,m;
void dfs(int i,LL v){
	//從左往右	 
    int x=c[i]-'0';//數(shù)據(jù)轉(zhuǎn)化 
    
    if(c[i]){//檢查 c[i] 是否存在且不為空字符 
    	
        //應(yīng)該使用的操作次數(shù)
        int t=min(n,9-x);
        n-=t;
        dfs(i+1,v*10+x+t);//遞歸調(diào)用
        //回溯
        n+=t;
        
        //考慮操作2是否能夠使用
        //目的是減小到9 
        if(m>x){//只有在m>x 的情況下才使用
            m-=(x+1);
            dfs(i+1,v*10+9);//遞歸調(diào)用
            //回溯
            m+=(x+1);
        }
        
    }
    
	else{
        //答案取max
        ans=max(ans,v);
    }
}
int main()
{
    scanf("%s%d%d",c,&n,&m);
    dfs(0,0);
    printf("%lld\n",ans);
    return 0;
}

方法二：（方法二存在樣例不通過的情況）

#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;

char c[20];
LL ans=0;

//n:1號操作剩余次數(shù)  m:2號操作剩余次數(shù)
int n,m;
void find_max(int i,LL v){
	//從左往右	 
    int x;//數(shù)據(jù)轉(zhuǎn)化 
    int t;
    //用的是字符串 '\0' 
    while(c[i]){//檢查 c[i] 是否存在且不為空字符 
    	x=c[i]-'0';//轉(zhuǎn)換數(shù)字
		 
    	if(m<=x){//如果這個(gè)數(shù) 大于或等于 減一的操作次數(shù)  
        
			//應(yīng)該使用的操作次數(shù)
        	t=min(n,9-x);//
        	n-=t;
        	v=v*10+x+t;//記錄下來 x+t 加完后的數(shù) 
        	i++;
        	ans=max(ans,v);
    	}
        //考慮操作2是否能夠使用
        //目的是減小到9 
        else{
        	v=v*10+9;
            m-=(x+1);
            i++;
            ans=max(ans,v);
	    }
	}
	
    
}
int main()
{
    scanf("%s%d%d",c,&n,&m);
    find_max(0,0);
    printf("%lld\n",ans);
    return 0;
}

廣度優(yōu)先搜索（Breadth First Search 簡稱 BFS）

廣度優(yōu)先搜索（Breadth First Search，簡稱BFS）：從某個(gè)狀態(tài)開始，將所有節(jié)點(diǎn)加入一個(gè)先進(jìn)先出的隊(duì)列，然后一層層進(jìn)行狀態(tài)轉(zhuǎn)移，并且展開節(jié)點(diǎn)。

廣度優(yōu)先搜索基本概念

偽代碼：

int check(參數(shù))
{
    if(滿足條件)
        return 1;
    return 0;
}
bool pd(參數(shù)){
    相應(yīng)操作
}
void bfs()
{
    1. 把根節(jié)點(diǎn)放入隊(duì)列尾端
    2. 每次從隊(duì)列中取出一個(gè)節(jié)點(diǎn)
    3. Check 判斷是不是答案，如果是結(jié)束算法 return;
    4. 把當(dāng)前取出的節(jié)點(diǎn)擴(kuò)展，如果擴(kuò)展后的節(jié)點(diǎn)經(jīng)Pd()后符合要求，就放入隊(duì)列，不符合就不放。
    5. 轉(zhuǎn)到步驟2，循環(huán)執(zhí)行
}

如果所有節(jié)點(diǎn)被擴(kuò)展完了，沒有找到答案就無解。

廣度優(yōu)先搜索（BFS）算法例題

例題一：長草問題

【數(shù)據(jù)結(jié)構(gòu)與算法】搜索算法（深度優(yōu)先搜索 DFS和廣度優(yōu)先搜索 BFS）以及典型算法例題,深度優(yōu)先,算法,寬度優(yōu)先,數(shù)據(jù)結(jié)構(gòu),矩陣

輸入示例：

4 5
.g...
.....
..g..
.....
2

輸出示例：

gggg.
gggg.
ggggg
.ggg.

解題思路：使用 $N \times M$ 的矩陣來表示草地。

將字母g的位置加入隊(duì)列
判斷邊界：
判斷是否長草，是否超出范圍
搜索
不斷從隊(duì)列中取出一個(gè)節(jié)點(diǎn)，進(jìn)行上下左右的擴(kuò)展，執(zhí)行2的判斷邊界條件，符合的就放入隊(duì)列，不符合就跳過。
執(zhí)行K次擴(kuò)展，輸出草地狀態(tài)
check()函數(shù)：
本題輸出最終狀態(tài) 因此不用這個(gè)函數(shù)

在廣度優(yōu)先搜索（BFS）中，我們通常需要對隊(duì)列中的節(jié)點(diǎn)進(jìn)行擴(kuò)展，也就是對當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)進(jìn)行處理。處理完一個(gè)節(jié)點(diǎn)后，我們應(yīng)該將其從隊(duì)列中移除，以避免重復(fù)處理相同的節(jié)點(diǎn)，確保每個(gè)節(jié)點(diǎn)只被處理一次。
因此需要：

	tempPair = q.front();
    q.pop();
    //這兩步是取出隊(duì)首的節(jié)點(diǎn)

題解代碼示例：



#include <bits/stdc++.h>
using namespace std;
const int M = 1005;

struct PII//坐標(biāo)
{
    int first;
    int second;
};

// C++ 有個(gè)數(shù)據(jù)類型叫 pair 上面的就可以定義為 pair<int,int> 用起來比較方便。
PII tempPair;//臨時(shí)結(jié)點(diǎn)

char Map[M][M];

//---------圖的路徑搜索常用方向移動(dòng)表示-------
int dx[4]= {0,1,-1,0};
int dy[4]= {1,0,0,-1};
// 兩兩組合形成上下左右四個(gè)方向
//      1------------------> x
//      |
//      |
//      |
//      |
//      |
//      |
//      |
//      ↓
//      y

// dx[0]=0 dy[0]=1 那么代表向下的方向

// dx[1]=1 dy[1]=0 那么代表向右的方向

// dx[2]=-1 dy[0]=0 那么代表向左的方向

// dx[3]=0 dy[1]=-1 那么代表向上的方向

int n;// n 行
int m;// m 列
int k;// k 次

//記錄 坐標(biāo)位置
queue<PII > q; //廣度優(yōu)先搜索所用的隊(duì)列

int len;//記錄節(jié)點(diǎn)數(shù)量方便后續(xù)k的計(jì)算

bool pd(int x, int y)
{
    if(x<1)
        return 0;
    // /x 軸坐標(biāo) 左側(cè)越界
    else if(x>n)
        return 0;
    //x 軸坐標(biāo) 右側(cè)越界
    else  if(y<1)
        return 0;
    //y 軸坐標(biāo) 上側(cè)越界
    else if(y>m)
        return 0;
    //y 軸坐標(biāo) 下側(cè)越界
    else if(Map[x][y]=='g')
        return 0;
    //已經(jīng)長草了
    else return 1;
    // 在范圍內(nèi)，且沒長草
}

void BFS()
{
    //BFS 
    //記得 層次
    while(!q.empty()&&k>0)
    {
        tempPair = q.front();
        q.pop();
        //這兩步是取出隊(duì)首的節(jié)點(diǎn)

        int x = tempPair.first;//橫坐標(biāo)
        int y = tempPair.second;//縱坐標(biāo)
        //四種擴(kuò)展情況
        for(int i=0; i<4; i++)
        {
            int nowx = x+dx[i]; //擴(kuò)展后的橫坐標(biāo)
            int nowy = y+dy[i]; //擴(kuò)展后的縱坐標(biāo)

            if(pd(nowx,nowy))
            {
                q.push({nowx,nowy});
                Map[nowx][nowy]='g';
            }
            //符合要求執(zhí)行擴(kuò)展，不符合要求，忽略即可。
        }

        len--; //每擴(kuò)展一個(gè)節(jié)點(diǎn)len  -1

        if(len==0)
        {
            //當(dāng)len =0 時(shí)，代表當(dāng)前層擴(kuò)展完了，那么就代表第一個(gè)月擴(kuò)展完了
            k--; // 所以k--
            //更新草的數(shù)目
            len = q.size(); // 當(dāng)前層擴(kuò)展完了，那就該擴(kuò)展下一層了，所以len又被賦值為下一層的節(jié)點(diǎn)數(shù)目的值
        }
    }
}

int main()
{
    //輸入
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>Map[i][j];
            if(Map[i][j]=='g')
            {
                tempPair.first=i;
                tempPair.second=j;
               // cout<<i<<""<<j<<endl;
                q.push(tempPair);//將初始有樹的結(jié)點(diǎn)加入隊(duì)列
            }
        }
    }

    len = q.size();//記錄第一層的節(jié)點(diǎn)數(shù)量方便后續(xù)k的計(jì)算
    cin>>k;
    BFS();

    //輸出
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cout<<Map[i][j];
        }

        cout<<endl;
    }
    return 0;
}

例題二：走迷宮問題

【數(shù)據(jù)結(jié)構(gòu)與算法】搜索算法（深度優(yōu)先搜索 DFS和廣度優(yōu)先搜索 BFS）以及典型算法例題,深度優(yōu)先,算法,寬度優(yōu)先,數(shù)據(jù)結(jié)構(gòu),矩陣
輸入示例：

輸出示例：

解題分析：

【數(shù)據(jù)結(jié)構(gòu)與算法】搜索算法（深度優(yōu)先搜索 DFS和廣度優(yōu)先搜索 BFS）以及典型算法例題,深度優(yōu)先,算法,寬度優(yōu)先,數(shù)據(jù)結(jié)構(gòu),矩陣

題解代碼示例：


#include <bits/stdc++.h>
using namespace std;

int vis[150][150]; //用于存儲是否訪問過，并且存儲長度

char G[150][150]; //用于存儲題目給出的地圖

int n,m,ans=0;

int dx[4] = {0,0,-1,1};

int dy[4] = {1,-1,0,0};

//上下左右移動(dòng)

struct node
{
    int x;
    int y;
};

node Start,End;
bool pd(int x,int y)
{


    if(x<1)
        return 0;
    //從左側(cè)走出方格

    else if(x>n)
        return 0;
    //從右側(cè)走出方格

    else if(y<1)
        return 0;
    //從上側(cè)走出方格

    else if(y>m)
        return 0;
    //從下側(cè)走出方格

    else if( vis[x][y]!=0)
        //已經(jīng)訪問了
        return 0;
    else if(G[x][y]!='1') return 0;
    //不是路不能走
    else return 1;
}

bool  check(int x, int y)
{

    if(x == End.x&& y == End.y)   //找到終點(diǎn)，把距離給他
    {
        ans  =  vis[x][ y];
        return 1;
    }

    else    return 0;

}
void bfs()
{
    queue<node>q;

    node now,next;

    q.push(Start);     //將起點(diǎn)壓人隊(duì)列中

    vis[Start.x][Start.y] = 1;

    while(!q.empty())
    {
        now = q.front();

        if(check(now.x,now.y))
            return ;

        q.pop();     //將隊(duì)列最前面的彈出。

        for(int i=0; i<4; i++)  //四個(gè)方向
        {

            int nextx = now.x + dx[i];
            int nexty = now.y + dy[i];

            if(pd(nextx,nexty))  //判斷是否符合條件
            {

                next.x=nextx;
                next.y=nexty;

                q.push(next);

                vis[nextx][nexty] = vis[now.x][now.y]+1; //步數(shù)+1
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    //memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>G[i][j];
        }
    }

    cin>>Start.x>>Start.y>>End.x>>End.y;

    ans = 0;

    bfs();
    cout<<ans-1<<endl;

    return 0;
}

感謝您的閱讀?。?！
【數(shù)據(jù)結(jié)構(gòu)與算法】系列文章鏈接: 【數(shù)據(jù)結(jié)構(gòu)與算法】遞推法和遞歸法解題（遞歸遞推算法典型例題）
【數(shù)據(jù)結(jié)構(gòu)與算法】系列文章鏈接: 【數(shù)據(jù)結(jié)構(gòu)與算法】C++的STL模板（迭代器iterator、容器vector、隊(duì)列queue、集合set、映射map）以及算法例題文章來源地址http://www.zghlxwxcb.cn/news/detail-849841.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】搜索算法（深度優(yōu)先搜索 DFS和廣度優(yōu)先搜索 BFS）以及典型算法例題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

【數(shù)據(jù)結(jié)構(gòu)】圖的遍歷：廣度優(yōu)先（BFS），深度優(yōu)先（DFS）
目錄 1、廣度優(yōu)先（BFS）算法思想? 廣度優(yōu)先生成樹? 知識樹? 代碼實(shí)現(xiàn)? 2、深度優(yōu)先（DFS）算法思想? 深度優(yōu)先生成樹知識樹? 代碼實(shí)現(xiàn)? ?????????圖的廣度優(yōu)先遍歷（BFS）是一種遍歷圖的算法，其思想是從起始頂點(diǎn)開始遍歷圖，先訪問起始頂點(diǎn)的所有直接鄰居，然
2024年02月04日
瀏覽(33)
【數(shù)據(jù)結(jié)構(gòu)】圖的創(chuàng)建和深度（DFS）廣度（BFS）優(yōu)先遍歷
圖是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通過表示為G(V,E)，其中，G標(biāo)示一個(gè)圖， V是圖G中頂點(diǎn)的集合， E是圖G中邊的集合。圖分為無向圖和有向圖無向圖：若頂點(diǎn)Vi到Vj之間的邊沒有方向，則稱這條邊為無向邊（Edge），用序偶對(Vi,Vj)表示。有向圖：若從
2024年02月05日
瀏覽(24)
數(shù)據(jù)結(jié)構(gòu)——圖篇（鄰接矩陣、鄰接表、深度優(yōu)先搜索、廣度優(yōu)先搜索）
描述圖比樹更為復(fù)雜，展現(xiàn)的是一種多對多的關(guān)系，圖的結(jié)構(gòu)是任意兩個(gè)數(shù)據(jù)對象之間都可能存在某種特定的關(guān)系的數(shù)據(jù)結(jié)構(gòu) 概念頂點(diǎn) ：基本介紹頂點(diǎn)集合表示為V集合，要求圖中頂點(diǎn)至少要有一個(gè)，即V集合不能為空集。通常使用|V|來表示頂點(diǎn)的個(gè)數(shù)，通常使用E(V)來表示
2024年02月04日
瀏覽(24)
Python 算法基礎(chǔ)篇：深度優(yōu)先搜索（ DFS ）和廣度優(yōu)先搜索（ BFS ）
深度優(yōu)先搜索（ DFS ）和廣度優(yōu)先搜索（ BFS ）是兩種常用的圖遍歷算法，用于在圖中搜索目標(biāo)節(jié)點(diǎn)或遍歷圖的所有節(jié)點(diǎn)。本篇博客將介紹 DFS 和 BFS 算法的基本概念，并通過實(shí)例代碼演示它們的應(yīng)用。 ???? ?? ?? ?? 深度優(yōu)先搜索（ DFS ）是一種用于遍歷或搜索圖或樹
2024年02月07日
瀏覽(53)
深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）兩種算法c++
深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)是一種用于遍歷或搜索樹圖的一種算法，在這個(gè)過程中保證圖或數(shù)的每個(gè)結(jié)點(diǎn)被訪問且僅被訪問一次，再按照每個(gè)結(jié)點(diǎn)訪問的順序不同分為深搜和廣搜。本文只討論這兩種算法在搜索方面的應(yīng)用！深度優(yōu)先搜索 ( Depth-First-Search，DFS )它沿
2024年02月13日
瀏覽(20)
圖的遍歷（搜索）算法（深度優(yōu)先算法DFS和廣度優(yōu)先算法BFS）
從圖的某個(gè)頂點(diǎn)出發(fā)訪問遍圖中所有頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問一次。（連通圖與非連通圖） 1、訪問指定的起始頂點(diǎn)； 2、若當(dāng)前訪問的頂點(diǎn)的鄰接頂點(diǎn)有未被訪問的，則任選一個(gè)訪問之；反之，退回到最近訪問過的頂點(diǎn)；直到與起始頂點(diǎn)相通的全部頂點(diǎn)都訪問完畢； 3、若
2024年01月17日
瀏覽(26)
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)6 ：圖的存儲與遍歷（鄰接矩陣的深度優(yōu)先遍歷DFS和鄰接表的廣度優(yōu)先遍歷BFS）
利用鄰接矩陣存儲無向圖，并從0號頂點(diǎn)開始進(jìn)行深度優(yōu)先遍歷。輸入第一行是兩個(gè)整數(shù)n1 n2，其中n1表示頂點(diǎn)數(shù)（則頂點(diǎn)編號為0至n1-1），n2表示圖中的邊數(shù)。之后有n2行輸入，每行輸入表示一條邊，格式是“頂點(diǎn)1 頂點(diǎn)2”，把邊插入圖中。例如： 4 4 0 1 1 3 0 3 0 2 先輸出存儲
2024年02月09日
瀏覽(27)
【數(shù)據(jù)結(jié)構(gòu)與算法】圖的深度優(yōu)先和廣度優(yōu)先遍歷
????作者簡介???? ：大家好，我是南瓜籽，一個(gè)在校大二學(xué)生，我將會(huì)持續(xù)分享Java相關(guān)知識。 ????個(gè)人主頁???? ：南瓜籽的主頁 ??座右銘?? ：堅(jiān)持到底，決不放棄，是成功的保證，只要你不放棄，你就有機(jī)會(huì)，只要放棄的人，他肯定是不會(huì)成功的人。圖是一
2024年02月02日
瀏覽(23)
【數(shù)據(jù)結(jié)構(gòu)與算法】圖的搜索——廣度優(yōu)先遍歷、最小生成樹
鄰接鏈表: 用字典實(shí)現(xiàn).有向圖的鄰接鏈表的總長度等于圖的邊個(gè)數(shù);無向圖的鄰接鏈表的總長度等于圖的邊個(gè)數(shù)的2倍. 鄰接矩陣:用于最短路徑算法. 該數(shù)據(jù)結(jié)構(gòu)維護(hù)一個(gè)不相交動(dòng)態(tài)集的集合，每個(gè)集合有一個(gè)代表，不關(guān)心誰做代表。支持三種操作： MAKE_SET(x) FIND_SET(x) UNION(x,y
2024年02月19日
瀏覽(24)
【算法導(dǎo)論】圖論（圖的基本概念，圖上的深度優(yōu)先搜索(DFS)，廣度優(yōu)先搜索(BFS)，最小生成樹(MST)及Prim,Kruskal算法）
圖(Graph)是一種包含節(jié)點(diǎn)與節(jié)點(diǎn)的邊的集合，記作G=(V,E),V是節(jié)點(diǎn)的集合，E是邊的集合。有向圖一個(gè)有向圖G=(V,E)，E中每個(gè)元素是V上的一個(gè)二值關(guān)系：一條從a出發(fā)的連向b的邊e可以記作一個(gè) 有序對e = (a,b) 。無向圖一個(gè)無向圖G=(V,E),E的每個(gè)元素e可以表示V上的一個(gè) 無序對，記
2024年02月03日
瀏覽(28)