floodfill+DFS(1)

文章目录

图像渲染
岛屿数量
岛屿的最大面积
被围绕的岛屿

图像渲染

class Solution {
public:int m = 0, n = 0;bool check[51][51] = {false};vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {m = image.size();n = image[0].size();int old = image[sr][sc];image[sr][sc] = color;dfs(image, sr, sc, color, old);return image;}void dfs(vector<vector<int>>& image, int sr, int sc, int color, int old){int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};for(int k = 0; k < 4; ++k){int x = sr + dx[k];int y = sc + dy[k];if(x >= 0 && y >= 0 && x < m && y < n && !check[x][y] && image[x][y] == old){int tmp = image[x][y];image[x][y] = color;check[x][y] = true;dfs(image, x, y,color, tmp);}}}
};

岛屿数量

class Solution {
public:bool check[301][301] = {false};int m = 0, n = 0;int numIslands(vector<vector<char>>& g) {m = g.size();n = g[0].size();int res = 0;for (int i = 0; i < m; ++i)for (int j = 0; j < n; ++j) {if (g[i][j] == '1' && !check[i][j]) {dfs(g, i, j);res++;}}return res;}void dfs(vector<vector<char>>& g, int i, int j) {check[i][j] = true;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};for (int k = 0; k < 4; ++k) {int x = i + dx[k];int y = j + dy[k];if (x >= 0 && y >= 0 && x < m && y < n && !check[x][y] && g[x][y] == '1')dfs(g, x, y);}}
};

岛屿的最大面积

class Solution {
public:bool check[51][51] = {false};int m = 0, n = 0;int path = 0;int maxAreaOfIsland(vector<vector<int>>& g) {m = g.size();n = g[0].size();int res = 0;for (int i = 0; i < m; ++i)for (int j = 0; j < n; ++j) {if (g[i][j] == 1 && !check[i][j]) {dfs(g, i, j);res = res > path ? res : path;path = 0;}}return res;}void dfs(vector<vector<int>>& g, int i, int j) {path += g[i][j];check[i][j] = true;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};for (int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if (x >= 0 && y >= 0 && x < m && y < n && g[x][y] == 1 && !check[x][y])dfs(g, x, y);}}
};

被围绕的岛屿

法1：先从边界往内处理，将不可被围绕的地方标记；剩下的分为可被围绕部分以及围绕点，将可被围绕地方变成围绕点；再恢复标记点成不可围绕标记

class Solution {
public:int m = 0, n = 0;bool check[201][201] = {false};void solve(vector<vector<char>>& board) {m = board.size();n = board[0].size();for (int i = 0; i < m; ++i) {if (board[i][0] == 'O' && !check[i][0])dfs(board, i, 0);if (board[i][n - 1] == 'O' && !check[i][n - 1])dfs(board, i, n - 1);}for (int i = 0; i < n; ++i) {if (board[0][i] == 'O' && !check[0][i])dfs(board, 0, i);if (board[m - 1][i] == 'O' && !check[m - 1][i])dfs(board, m - 1, i);}for (int i = 0; i < m; ++i)for (int j = 0; j < n; ++j) {if (board[i][j] == '.')board[i][j] = 'O';else if (board[i][j] == 'O')board[i][j] = 'X';}}void dfs(vector<vector<char>>& board, int i, int j) {board[i][j] = '.';check[i][j] = true;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};for (int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if (x >= 0 && y >= 0 && x < m && y < n && board[x][y] == 'O' && !check[x][y])dfs(board, x, y);}}
};