DFS深度优先搜索岛屿问题涂色问题扫雷游戏 LeetCode

题目：https://leetcode-cn.com/problems/number-of-islands/
参考：https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/
重要参考：https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/

文章图片

文章图片

基于DFS解决问题 :
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
最终岛屿的数量就是我们进行深度优先搜索的次数。

class Solution { public: bool inArea(vector>& grid, int row, int col) { return row >= 0 && row < grid.size() && col >= 0 && col < grid[0].size(); } void dfs(vector>& grid, int row, int col) { if(!inArea(grid, row, col)) return; if(grid[row][col] != '1') return; grid[row][col] = '0'; dfs(grid, row - 1, col); dfs(grid, row + 1, col); dfs(grid, row, col - 1); dfs(grid, row, col + 1); } int numIslands(vector>& grid) { int count = 0; if(grid.size() == 0 || grid[0].size() == 0) return 0; for(int i = 0; i < grid.size(); i++) { for(int j = 0; j < grid[0].size(); j++) { if(grid[i][j] == '1') { count++; dfs(grid, i, j); } } } return count; } };

第2种写法，本质相同

/*深度优先搜索 DFS*/ class Solution { private: void dfs(vector>& grid, int r, int c) { int m = grid.size(); int n = grid[0].size(); grid[r][c] = '0'; // 1 -> 0 if(r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r-1, c); //up if(r + 1 < m && grid[r+1][c] == '1') dfs(grid, r+1, c); //down if(c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c-1); //left if(c + 1 < n && grid[r][c+1] == '1') dfs(grid, r, c+1); //right }public: int numIslands(vector>& grid) { int m = grid.size(); if(m == 0) return 0; int n = grid[0].size(); int num_of_islands = 0; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(grid[i][j] == '1') { //以此节点为起始节点进行深度优先搜索 num_of_islands++; dfs(grid, i, j); //把与这个1相连的1全部清0 } } } return num_of_islands; } };

leetcode 695. 岛屿的最大面积
题目：https://leetcode-cn.com/problems/max-area-of-island/

class Solution { public: bool inArea(vector>& grid, int row, int col) { return row >= 0 && row < grid.size() && col >= 0 && col < grid[0].size(); } int dfs(vector>& grid, int row, int col) { if(!inArea(grid, row, col)) return 0; if(grid[row][col] != 1) return 0; grid[row][col] = 2; return 1 + dfs(grid, row - 1, col) + dfs(grid, row + 1, col) + dfs(grid, row, col - 1) + dfs(grid, row, col + 1); } int maxAreaOfIsland(vector>& grid) { int count = 0; if(grid.size() == 0 || grid[0].size() == 0) return 0; for(int i = 0; i < grid.size(); i++) { for(int j = 0; j < grid[0].size(); j++) { if(grid[i][j] == 1) { count = max(count, dfs(grid, i, j)); } } } return count; } };

leetcode 463. 岛屿的周长
题目：https://leetcode-cn.com/problems/island-perimeter/

class Solution { public: //判断坐标是否在网格中 bool inArea(vector>& grid, int row, int col) { return row >= 0 && row < grid.size() && col >= 0 && col < grid[0].size(); } int dfs(vector>& grid, int row, int col) { //坐标超出网格边界 if(!inArea(grid, row, col)) return 1; //当前格子是海洋 if(grid[row][col] == 0) return 1; //当前格子已经遍历过了 if(grid[row][col] != 1) return 0; grid[row][col] = 2; //标记已经遍历了 return dfs(grid, row - 1, col) + dfs(grid, row + 1, col) + dfs(grid, row, col - 1) + dfs(grid, row, col + 1); } //周长 = 超出网格边界的情况数 + 当前节点是海洋（0）的情况数 int islandPerimeter(vector>& grid) { if(grid.size() == 0 || grid[0].size() == 0) return 0; for(int i = 0; i < grid.size(); i++) { for(int j = 0; j < grid[0].size(); j++) { if(grid[i][j] == 1) { return dfs(grid, i, j); //只有1个岛屿 } } } return 0; } };

参考：https://labuladong.gitbook.io/algo/suan-fa-si-wei-xi-lie/floodfill-suan-fa-xiang-jie-ji-ying-yong
leetcode 733. 图像渲染

class Solution_flood_fill { public: bool inArea(vector>& image, int r, int c) { return r >= 0 && r < image.size() && c >= 0 && c < image[0].size(); } void dfs(vector>& image, int row, int col, int originColor, int newColor) { //出界超出数组边界 if(!inArea(image, row, col)) return; //遇到其他颜色超出originColor区域 if(image[row][col] != originColor) return; //已经访问过 if(image[row][col] == -1) return; image[row][col] = -1; //标记, 已经访问过 dfs(image, row-1, col, originColor, newColor); //up dfs(image, row+1, col, originColor, newColor); //down dfs(image, row, col-1, originColor, newColor); //left dfs(image, row, col+1, originColor, newColor); //right image[row][col] = newColor; //颜色填充 } vector> floodFill(vector>& image, int sr, int sc, int newColor) { int originColor = image[sr][sc]; dfs(image, sr, sc, originColor, newColor); return image; } };

【DFS深度优先搜索岛屿问题涂色问题扫雷游戏】leetcode 1034. 边框着色

class Solution_1034 { public: vector> visited; bool inArea(vector>& image, int r, int c) { return r >= 0 && r < image.size() && c >= 0 && c < image[0].size(); } int dfs(vector>& grid, int row, int col, int originColor, int color) { // 超出数组边界 if(!inArea(grid, row, col)) return 0; // 已经访问过此区域 if(visited[row][col]) return 1; // 碰壁：遇到其他颜色, 超出originColor区域 if(grid[row][col] != originColor) return 0; // 标记已经访问了 visited[row][col] = true; int surround = dfs(grid, row-1, col, originColor, color) + dfs(grid, row+1, col, originColor, color) + dfs(grid, row, col-1, originColor, color) + dfs(grid, row, col+1, originColor, color); // 区域内部的点 surround == 4, 边界点surround < 4 if(surround < 4) grid[row][col] = color; return 1; } vector> colorBorder(vector>& grid, int r0, int c0, int color) { int m = grid.size(); int n = grid[0].size(); visited.resize(m, vector(n, false)); int originColor = grid[r0][c0]; dfs(grid, r0, c0, originColor, color); return grid; } };

leetcode 529. 扫雷游戏
题目：https://leetcode-cn.com/problems/minesweeper/

class Solution_529 { public: vector dx = {-1, +1, 0, 0, -1, -1, +1, +1}; vector dy = {0, 0, -1, +1, -1, +1, -1, +1}; // 是否在数组内 bool inArea(vector>& board, int r, int c) { return r >= 0 && r < board.size() && c >= 0 && c < board[0].size(); } // 统计此位置周围有多少地雷 int numsOfMine(vector>& board, int row, int col) { int count_mine = 0; for(int i = 0; i < 8; i++) { int new_row = row + dx[i]; int new_col = col + dy[i]; if(!inArea(board, new_row, new_col)) continue; if(board[new_row][new_col] == 'M') count_mine++; } return count_mine; } void dfs(vector>& board, int row, int col) { if(!inArea(board, row, col)) return; if(board[row][col] == 'E') { board[row][col] = 'B'; int nums_mine = numsOfMine(board, row, col); if(nums_mine == 0) { // 当前位置为 ‘E’ 且周围地雷数量为0时, 进行深度优先搜索dfs for(int i = 0; i < 8; i++) { int new_row = row + dx[i]; int new_col = col + dy[i]; dfs(board, new_row, new_col); } } else { // nums_mine > 0 board[row][col] = nums_mine + '0'; } } } vector> updateBoard(vector>& board, vector& click) { int row = click[0]; int col = click[1]; if(board[row][col] == 'M') board[row][col] = 'X'; else if(board[row][col] == 'E') dfs(board, row, col); return board; } };