馬上藍橋杯了，最近刷了廣搜，感覺挺有意思的，廣搜題類型都差不多，模板也一樣，大家寫的時候可以直接套模板

這里給大家講一個比較經典的廣搜題-迷宮

題目問問能否走到?(n,m)?位置，假設最后一個點是我們的（n,m) 點

那我們如何判斷是否可以走到我們的（n,m）點呢？

題目給我們的起點是（1，1），然后對應的數組下標就是（0，0），（下面我們說的坐標都是我們的數組下標）首先我們定義我們的一個二維數組maze來存儲我們的迷宮，然后現在從（0，0）坐標開始，我們需要定義一個隊列來存儲我們的可用的坐標，遍歷我們的坐標，然后這里我們有四個方向可以走，上下左右，就是說當我們達到該坐標的時候，需要遍歷上下左右四個方向，然后將可以用的坐標進行存儲到我們的隊列當中

但是通過上圖可以看到，當向上和向左的時候，我們的坐標越界了，沒有意義，所以我們不需要處理這兩個坐標，然后向右，我們發現是面墻，因為題目說" # "是一個墻，這個坐標是不能使用的，所以這里我們遍歷到該坐標的時候需要一個判斷看該坐標是不是" . " ，然后遍歷下面，發現既沒有越界，也不是墻，所以我們就將該坐標（1，0）添加到我們的隊列里面，然后（0，0）坐標使用過了，我們就使用pop()方法將它刪除，因為我們遍歷所有可添加的坐標，使用需要將不用的坐標進行刪除

通過第一次（0，0）坐標的四個方向遍歷，我們已經（1，0）坐標添加上去，然后繼續進行遍歷~

遍歷完成之后添加我們的（2，0），但是當我們遍歷上面的點時，我們發現有問題，因為我們已經走過（0，0）點了，使用我們還需要一個數組dist，來儲存我們走過的坐標....，如果走過，就讓該坐標當下的值變成1，0表示沒有走過，1表示走過，如果沒有走過我們才將坐標添加上去，依次類推，直到找到我們的（n,m）點，然后進行輸出，如果遍歷完還沒有找到，就輸出No

定義：

 char maze[N][N];//迷宮int dist[N][N];//路徑queue<pair<int,int> > q;//定義隊列

初始化：

  memset(dist,0,sizeof(dist));dist[0][0]=1;//1表示走過，0表示沒有走過q.push({0,0});//初始化隊列

定義上下左右移動數組：
?

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

遍歷隊列坐標：（廣搜模板）

    while(!q.empty()){auto[x,y]=q.front();q.pop();// 遍歷上下左右四個方向for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];//判斷是否到達了該坐標if(nx==n-1&&ny==m-1){cout<<"Yes";return 0;}//判斷是否可以添加該坐標if(nx>=0&&nx<=n&&ny>=0&&ny<=m&&maze[nx][ny]=='.'&&dist[nx][ny]==0){dist[nx][ny]=1;q.push({nx,ny});}}}

?

下面是代碼實現：

#include<bits/stdc++.h>
using namespace std;
const int N=100;
char maze[N][N];//迷宮
int dist[N][N];//路徑
queue<pair<int,int> > q;
int main(){int n,m;cin>>n>>m;dist[0][0]=1;//1表示走過，0表示沒有走過q.push({0,0});//初始化隊列memset(dist,0,sizeof(dist));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>maze[i][j];}}//定義上下左右移動數組int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};while(!q.empty()){auto[x,y]=q.front();q.pop();// 遍歷上下左右四個方向for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx==n-1&&ny==m-1){cout<<"Yes";return 0;}if(nx>=0&&nx<=n&&ny>=0&&ny<=m&&maze[nx][ny]=='.'&&dist[nx][ny]==0){dist[nx][ny]=1;q.push({nx,ny});}}}cout<<"No";return 0;
}

如果大家聽懂了，可以寫一下P1443 馬的遍歷 - 洛谷? 題來檢測一下，一樣的類型