每日一题之拉低通过率 BFSDFS leetcode 200 岛屿数量

思路1： 套用BFS模型

从一个点开始，利用BFS遍历每一个小岛生成的群岛就是一个岛屿

class Solution { private: int addrow[4] = {1, -1, 0, 0}; int addcol[4] = {0, 0, 1, -1}; public: void BFS(int row, int col, vector<vector<bool>>& visited, vector<vector<char>>& grid) { queue<pair<int, int>> qu; //保存遍历的点 qu.emplace(row, col); //放入第一个点 visited[row][col] = true; //避免重复拜访 while (!qu.empty()) { int r = qu.front().first, c = qu.front().second; qu.pop(); for (int i = 0; i < 4; i ++) { int tr = r + addrow[i]; int tc = c + addcol[i]; if (tr >= 0 && tr < grid.size() && tc >= 0 && tc < grid[0].size() && grid[tr][tc] == '1' && visited[tr][tc] == false) { qu.emplace(tr, tc); visited[tr][tc] = true; } } } } int numIslands(vector<vector<char>>& grid) { int rows = grid.size(), cols = grid[0].size(); vector<vector<bool>> visited(rows, vector<bool>(cols, false)); int sum = 0; for (int i = 0; i < rows; i ++) { for (int j = 0; j < cols; j ++) { if (grid[i][j] == '1' && visited[i][j] == false) { BFS(i, j, visited, grid); sum ++; } } } return sum; } };

思路2：套用DFS模型

现附上错误代码： 有两个错误：

没给row、col的visited赋值visited[row + addrow[i]][col + addcol[i]] 可能越界

回溯算法的每一个节点有选择列表和路径的属性，节点的含义和普通的图、树有差别。因此对于回溯算法，在遍历完一个节点A进行回溯时，为了对节点B进行遍历，就需要清除节点A的path和选择列表的属性，更正为节点B的属性。

class Solution { private: int addrow[4] = {1, -1, 0, 0}; int addcol[4] = {0, 0, 1, -1}; public: void backTrack(int row, int col, vector<vector<bool>>& visited, vector<vector<char>>& grid) { if (!(row >= 0 && row < grid.size() && col >= 0 && col < grid[0].size() && grid[row][col] == '1' && visited[row][col] == false)) { return ; } //有错误 for (int i = 0; i < 4; i ++) { visited[row + addrow[i]][col + addcol[i]] = true; backTrack(row + addrow[i], col + addcol[i], visited, grid); } } int numIslands(vector<vector<char>>& grid) { int rows = grid.size(), cols = grid[0].size(); vector<vector<bool>> visited(rows, vector<bool>(cols, false)); int sum = 0; for (int i = 0; i < rows; i ++) { for (int j = 0; j < cols; j ++) { if (grid[i][j] == '1' && visited[i][j] == false) { backTrack(i, j, visited, grid); sum ++; } } } return sum; } };

更正后

class Solution { private: int addrow[4] = {1, -1, 0, 0}; int addcol[4] = {0, 0, 1, -1}; public: void backTrack(int row, int col, vector<vector<bool>>& visited, vector<vector<char>>& grid) { if (!(row >= 0 && row < grid.size() && col >= 0 && col < grid[0].size() && grid[row][col] == '1' && visited[row][col] == false)) { return ; } visited[row][col] = true; for (int i = 0; i < 4; i ++) { backTrack(row + addrow[i], col + addcol[i], visited, grid); } } int numIslands(vector<vector<char>>& grid) { int rows = grid.size(), cols = grid[0].size(); vector<vector<bool>> visited(rows, vector<bool>(cols, false)); int sum = 0; for (int i = 0; i < rows; i ++) { for (int j = 0; j < cols; j ++) { if (grid[i][j] == '1' && visited[i][j] == false) { backTrack(i, j, visited, grid); sum ++; } } } return sum; } }; class Solution { private: int addrow[4] = {1, -1, 0, 0}; int addcol[4] = {0, 0, 1, -1}; public: void backTrack(int row, int col, vector<vector<bool>>& visited, vector<vector<char>>& grid) { for (int i = 0; i < 4; i ++) { int r = row + addrow[i], c = col + addcol[i]; if (r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size() && grid[r][c] == '1' && visited[r][c] == false) { visited[r][c] = true; backTrack(r, c, visited, grid); } } } int numIslands(vector<vector<char>>& grid) { int rows = grid.size(), cols = grid[0].size(); vector<vector<bool>> visited(rows, vector<bool>(cols, false)); int sum = 0; for (int i = 0; i < rows; i ++) { for (int j = 0; j < cols; j ++) { if (grid[i][j] == '1' && visited[i][j] == false) { visited[i][j] = true; backTrack(i, j, visited, grid); sum ++; } } } return sum; } };