接下來幾天我要討論 Grid traversal 與 Graph Traversal，在這兩者主題都有談及 DFS（深度優先搜索）和BFS（廣度優先搜索），因此我今天就討論DFS 與 BFS。這兩搜尋策略並且都要注意「不要重複走訪相同的節點」，為此，我們該像糖果屋兄妹撒麵包屑一樣，記錄走過的路徑。

在文章 Python-LeetCode 581 第三招 Grid Traversal ，吳邦一教授教授的招式是，當我們在網格(Grid)中使 BFS/DFS走訪時，可以使用 sentinel(哨兵) 的小技巧，也就是在grid 的右邊與下方加上不能通行的 0，藉由 python 索引 -1 是 list 最後一元素的寫法，當超過上界或右界都會走到哨兵處，因此這就不需要做邊界檢查，這讓程式碼跑得又快又優雅啊!

(以下的 C++ 練習沒有用到 sentinel的技巧，但 Rust 這語言可以做到，之後題目我補寫這技巧!)

DFS, BFS 的非遞迴模板

DFS 用 stack, BFS用 queue 做圖的遍歷。
使用不同資料結構的重點，在於順序。

stack 先進後出的特性，當所有相鄰節點塞進 stack 後，會是最後塞進 stack 的相連節點被pop ，第一個被訪問到。

而 bfs 的 queue 則是先進先出的特性，會先處理所有相鄰結點後，逐步擴展 (就像是同心圓般)

以下是DFS模板 (BFS模板 只需將 stack 改成 queue)

bool DFS(Node *root) {
	stack<int> st;
	set<Node *> isVisited;  // 可用陣列代替
	st.push(root);
	while (!st.empty()) {
		Node *tp = st.top();
		st.pop();
		for (...) // 遍歷四個方向或遍歷相鄰節點 {
			獲取相鄰節點 Node *
			if (該相鄰節點可以走訪且未被走訪) {
				isVisited.insert(相鄰節點);
				st.push(相鄰節點);
			}
		}
	}
}

如果題目要求:

1. 搜索到某目標節點，那麼在每次要將節點塞入 stack 之前，檢查節點是否是為目標節點，否則就繼續走訪圖，直到最後把整張圖都走完。
2. 計算走到目標節點的步數，就在在 while 內的第一行設一個計步器並遞增。

200. Number of Islands (medium)

題目敘述: 由0(水), 1 (島)組成二維矩陣當作地圖，這地圖裡相連的1被視為一個島，要返回地圖上島的數量。

解題思路:
把全部二維矩陣的每一個位置都當作 DFS 或是 BFS 的起點，然後起點向外能走到的都是島。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        // int dirs[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};
        int IslandNum = 0, offsets[] = {0, 1, 0, -1, 0};
        //每一位置都當起點做 BFS
        for(int i =0 ; i < grid.size() ; i++){
            for (int j =0; j < grid[0].size() ; j++){  
                if(grid[i][j] == '1'){  
                    IslandNum += 1;
                    queue<pair<int, int>> qu; // 存 x, y座標 
                    qu.push({i,j});
                    // 套BFS 模板
                    while(!qu.empty()) {
                        pair<int, int> node = qu.front();
                        qu.pop();
                        // 四個方向都嘗試
                        for (int k = 0; k < 4; k++) {
                            int r = node.first + offsets[k], c = node.second + offsets[k+1];
                           if (r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size() && grid[r][c] == '1') {
                                grid[r][c] = '0'; // 走過就設0
                                qu.push({r, c});
                            }
                        }
                    }
                }
            }
        }
        return IslandNum;
    }
};

看別人的學到兩招:

1. 這題沒有規定不能改變 map，因此這題可以走過就直接設 0 ，讓下次走訪不能走，而不用額外使用陣列或是 set 去紀錄此位置是否走過。
2. offsets[] = {0, 1, 0, -1, 0}; 表示四方向，這寫法很簡潔! 我以前都是寫 int dirs[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};或是用 4個 pair<int, int> 去相對冗長的表示四方向。

時間複雜度為 O(n * m)，其中 n 和 m 分別是二維矩陣的行數和列數，因為，每個節點最多只會被訪問一次。