小試牛刀——走迷宮 ?

問題描述 ?

給定一個 n×m 的二維整數陣列，用來表示一個迷宮，陣列中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通過的墻壁，

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

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

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

輸入格式
第一行包含兩個整數 n 和 m，

接下來 n 行，每行包含 m 個整數（0 或 1），表示完整的二維陣列迷宮，

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

資料范圍
1≤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

原題鏈接：https://www.acwing.com/problem/content/846/

參考代碼(C++版本)

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

using namespace std;
typedef pair<int,int> PII;
const int N = 110;
int n,m;
int g[N][N],d[N][N]; //存放地圖的陣列和存放距離的陣列
queue<PII> q;

int bfs()
{
    memset(d,-1,sizeof d);//使用<cstring>中的庫函式memset快速初始化陣列
    d[0][0] = 0;//標記點(0,0)已經走過了
    q.push({0,0});
    
    //放置的偏移量陣列
    int dx[] ={-1,0,1,0},dy[] = {0,1,0,-1};
    
    //當佇列不為空，執行下述操作
    while(q.size())
    {
        auto t = q.front(); //取出隊頭元素
        q.pop();//已獲得隊頭資訊，隊頭可以出隊了
        
        //對四個方向進行探索
        for(int i = 0; i < 4;i++)
        {
            //利用向量陣列獲得四個方向的坐標
            int x = t.first+dx[i],y = t.second+dy[i];
            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;//更新現在的點(x,y)到起點的距離
                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() <<endl;
    return 0;
}

知識儲備🌊🌊🌊

寬度優先搜索(Breadth-first search,BFS)

一點閑話🌹

寬度優先搜索也是一種常用的搜索方式之一，和它一起耳熟能詳的是深度優先搜索(DFS),都是從某個狀態出發，探索所有可以到達的狀態

BFS的搜索模式🎯

寬度優先搜索總是先搜索距離初始狀態近的狀態，也就是說，它是按照這樣的順序進行搜索的，開始狀態——>只需轉移1次就可以到達的所有狀態——>只需轉移2次就可以到達的所有狀態——>…，對于同一個位置，寬度優先搜索只會經過它一次，以后再碰到它便不會再檢索它，

BFS依賴的資料結構🎯

寬度優先搜索不同于深度優先搜索，它是一層一層的進行遍歷，因此需要用到的是先入先出的佇列

BFS的用武之地🎯

BFS可以用于處理一下問題:

1. 第一類問題：可達性問題，從結點A出發，有前往結點B的路徑嗎？
2. 第二類問題：最短路問題，從結點A出發，前往結點B的哪條路最短？

由于按照層次逐層進行搜索、遍歷，寬度優先搜索時按照距開始狀態由近及遠的順序進行搜索，也就常常用來處理最短路、最少操作等問題，
注意：寬度優先搜索只能解決每條邊的權值是相同的最短路徑問題，其他情況的最短路問題需要使用專門的最短路演算法，比如：Dijkstra演算法、Bellman-Ford演算法等等，這些演算法后續我也會持續更出對它們的理解和總結的喔~🎉🎉🎉

解題思路🌊🌊🌊

BFS的運作流程🎯

前提鋪墊：使用陣列d[]記錄個當前點v到起點s的距離

1. 將起點s放入佇列Q中(訪問)
2. 只要Q不空，回圈執行下述操作
   1. 從Q中取出頂點u進行訪問(訪問結束)
   2. 將與u相鄰的未訪問的頂點v放入Q，同時將d[v]更新為d[u] +1

邏輯思路講解🎯

1. 輸入：創建地圖 🎶

   cin >> n >>m;
   for(int i = 0; i < n;i++)
       for(int j = 0;j< m;j++) cin >> g[i][j];
   

2. 呼叫bfs()函式🎶

   cout << bfs() <<endl;
   

   實作寬搜的bfs()函式🎶
   1. 🎹前戲——初始化整個距離陣列

      memset(d,-1,sizeof d);//使用的是<cstring>庫中的memset函式，按照位元組對傳入的陣列全部初始化為-1
       d[0][0] = 0;//表示點(0,0)已經走過了
   

   2.🎹 將起點s放入佇列Q中(訪問)

   q.push({0,0});
   

   3. 🎹只要Q不空，回圈執行下述操作===> 取隊頭，拓展隊頭

   int dx[] ={-1,0,1,0},dy[] = {0,1,0,-1};
   while(q.size())
      {
          auto t = q.front();
          q.pop();
          
          for(int i = 0; i < 4;i++)
          {
              int x = t.first+dx[i],y = t.second+dy[i];
              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.push({x,y});
              }
          }
      }
   

3. 快樂Ac 💫

難點剖析🌊🌊🌊

最難處理的應該是回圈體中的邏輯怎么安排

首先，按照bfs運作流程取出隊頭.這里使用了c++的關鍵字auto,它會自動判斷回傳值型別，偷懶省事必備喔💓

獲得隊頭資訊以后，這個隊頭就可以出隊了，使得下一個資訊可以來到隊頭的位置被獲取

        auto t = q.front();
        q.pop()

然后，將與u相鄰的未訪問的頂點v放入Q 也就是拓展隊頭，判斷隊頭可以向走到哪些位置，此處取巧使用了向量陣列來表示4個移動的方向，將獲取后的新坐標放到if判斷里，判斷其是否越界，是否是可以探索的，是否被探索過，假如都沒有，那就占據這個點，也就是將其入隊，同時將d[v]更新為d[u] +1

        for(int i = 0; i < 4;i++)
        {
            int x = t.first+dx[i],y = t.second+dy[i];
            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.push({x,y});
            }
        }

關于方向向量陣列

如圖，可以將一個坐標點進行抽象，那么它在x軸上能活動的區域，按照順時針記錄，是{-1,0,1,0}，對于y一樣可以這種記錄，即{0,1,0,-1}，

使用向量陣列可以簡化我們的代碼，對于四個方向的探索就可以不用麻煩的寫if判斷

舉一反三——資訊學奧賽一本通-T1255

給定一個 n×n 的二維陣列，如下所示：

int maze[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,

};
它表示一個迷宮，其中的1表示墻壁，0表示可以走的路，只能橫著走或豎著走，不能斜著走，要求編程式找出從左上角到右下角的最短路線，

資料保證至少存在一條從左上角走到右下角的路徑，

輸入格式
第一行包含整數 n，

接下來 n 行，每行包含 n 個整數 0 或 1，表示迷宮，

輸出格式
輸出從左上角到右下角的最短路線，如果答案不唯一，輸出任意一條路徑均可，

按順序，每行輸出一個路徑中經過的單元格的坐標，左上角坐標為 (0,0)，右下角坐標為 (n?1,n?1)，

資料范圍
0≤n≤1000
輸入樣例：
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
輸出樣例：
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4

參考代碼(C++版本)

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

using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int n;
int g[N][N];
PII prev_num[N][N];

void bfs(int sx,int sy)
{
    queue<PII> q;
    //入隊
    q.push({sx,sy});
    
    int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
    memset(prev_num,-1 ,sizeof prev_num);
    //當佇列不為空
    while(q.size())
    {
        //取隊頭
        PII t = q.front();
        q.pop();
        
        //拓展隊頭
        for(int i = 0;i < 4;i++)
        {
            int a = t.first+dx[i],b = t.second+dy[i];
            if(a< 0 || a  >= n || b < 0 || b >= n) continue;//越界
            if(g[a][b]) continue;//墻
            if(prev_num[a][b].first != -1) continue;
            
            //加到佇列
            q.push({a,b});
            //記錄上個狀態的位置
            prev_num[a][b] = t;
            
        }
    }
    
}

int main()
{
    scanf("%d",&n);
    for(int i = 0; i <n;i++)
        for(int j = 0;j < n;j++) scanf("%d",&g[i][j]);
    
    bfs(n-1,n-1);
    PII end(0,0);
    
    while(true)
    {
        printf("%d %d\n",end.first,end.second);
        if(end.first == n-1 && end.second == n-1) break;
        end = prev_num[end.first][end.second];
    }
    
    return 0;
}

解題思路🌊🌊🌊

這道迷宮問題和走迷宮幾乎是一樣的，思路是一樣的，用寬度優先搜索一層一層的去查找，第一次搜索到的終點就是最短路徑，要求我們輸出這段路徑，

道理誰都懂，隨口就能生動形象的描述出來，從這個點走到哪個點，再轉一下…問題怎么用代碼實作出來了？

我們來手動模擬一下bfs探索的程序，先取出隊頭，然后咱們站在隊頭的位置，眺望四方，康康哪里可以走了？喔~~~ 那里可以走，好的，走上去,記錄下當前的位置，再探索，按照這種流程，我們可以開一個陣列，記錄當前這個點(x,y)是從哪個點走過來的，

詳細剖析

記錄資料🎯

typedef pair<int,int> PII;
PII prev_num[N][N];
// 記錄資料的偽代碼如下：
prev_num[x][y] = 探索前的坐標

//記錄上個狀態的位置
prev_num[a][b] = t;

1. 涉及的stl容器：pair(數對)是將2個資料組合成一組資料，pair的實作是一個結構體，主要的兩個成員變數first和second，分別存盤兩個資料，因為我們要輸出的是一組坐標，那么用數對pair來記錄會讓我們，如魚得水

2. 關于prev_num[x][y] = 探索前的點,有小伙伴讀起來可能比較蒙，what’s this ?！各位看官，可這種理解喔💓💓💓，
   現在有一個二維矩陣，矩陣的型別是存放一組int型變數的數對，矩陣的名字是prev_num，現在讓矩陣中位置是(x,y)的這塊空間存放探索前的坐標t(這個坐標肯定也是數對型別的啦~)

輸出資料🎯

經過一番倒騰，資料終于記錄進去了，現在怎么輸出這個二維陣列了？注意喔，正是因為它是二維陣列，所以不能很暴力的直接兩個for回圈輸出結果，因為其他沒有用到的位置也會被遍歷輸出，

這里就出現了比較巧妙的一點，bfs搜索的時候，倒著搜索回去，那我存放的點就是從起點(0,0)逐步逐步的到達終點，這樣我們就可以正向遍歷這段路徑了

    bfs(n-1,n-1);//倒著搜回去
    PII end(0,0);//創建一個PII型別的變數end，初始化為(0,0)
    
    while(true)
    {
        printf("%d %d\n",end.first,end.second);
        if(end.first == n-1 && end.second == n-1) break;
        end = prev_num[end.first][end.second];
    }

快樂Ac~

謝謝耐心觀看啦~，若有偏頗，歡迎及時指出喔💓💓💓

基礎演算法持續更新中ing~