【LeetCode & 劍指offer 刷題筆記】目錄（持續更新中...）

Number of Islands

Given a 2d grid map of?'1's (land) and?'0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: 11110 11010 11000 00000 Output: 1 Example 2: Input: 11000 11000 00100 00011 Output: 3

---

C++ 類似題目： 13 機器人的運動范圍? Word Search（系列） ?? ?這道求島嶼數量的題的本質是求矩陣中連續區域的個數，很容易想到需要用深度優先搜索DFS來解，我們需要建立一個visited數組用來記錄某個位置是否被訪問過， ?? ?對于一個為‘1’且未被訪問過的位置，我們遞歸進入其上下左右位置上為‘1’的數，將其visited對應值賦為true，繼續進入其所有相連的鄰位置，這樣可以將這個連通區域所有的數找出來，并將其對應的visited中的值賦true， ?? ?找完次區域后，我們將結果res自增1，然后我們在繼續找下一個為‘1’且未被訪問過的位置，以此類推直至遍歷完整個原數組即可得到最終結果，代碼如下： class Solution { public: ??? int numIslands(vector<vector<char> > &grid) ??? { ??????? if (grid.empty() || grid[0].empty()) return 0; ??????? ??????? int m = grid.size(), n = grid[0].size(); ??????? int result = 0; ??????? vector<vector<bool> > visited(m, vector<bool>(n, false)); //創建訪問矩陣 ??????? for (int i = 0; i < m; i++)?//遍歷柵格中所有元素（因為每個點都有可能為某個島嶼的某點） ??????? { ??????????? for (int j = 0; j < n; j++) ??????????? { ??????????????? if (grid[i][j] == '1' && !visited[i][j]) { ??????????????????? numIslandsDFS(grid, visited, i, j); //向相鄰方向（上下左右）走當遇到越界，或者遇到0或者遇到訪問過的1后，遞歸函數退出，所有遞歸分支退出后，該遞歸函數結束，找到一個島嶼 ??????????????????? result++; //統計島嶼的個數 ??????????????? } ??????????? } ??????? } ??????? return result; ??? } ??? void numIslandsDFS(vector<vector<char> > &grid, vector<vector<bool> > &visited, int x, int y) { ??????? if (x < 0 || x >= grid.size()) return; ??????? if (y < 0 || y >= grid[0].size()) return; //超出范圍時退出 ??????? if (grid[x][y] != '1' || visited[x][y]) return; //如果不為1或者訪問過就退出 ??????? ??????? visited[x][y] = true; ??????? numIslandsDFS(grid, visited, x - 1, y); ??????? numIslandsDFS(grid, visited, x + 1, y); ??????? numIslandsDFS(grid, visited, x, y - 1); ??????? numIslandsDFS(grid, visited, x, y + 1); ??? } }; 轉自：https://www.cnblogs.com/grandyang/p/4402656.html

?

轉載于:https://www.cnblogs.com/wikiwen/p/10229466.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的【LeetCode 剑指offer刷题】回溯法与暴力枚举法题6：Number of Islands的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。