【C++刷题】优选算法——递归第三辑
floodfill篇
- 图像渲染
unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{-1, 0}
};
void dfs(vector<vector<int>>& image, int sr, int sc, int color, int val)
{image[sr][sc] = color;for(auto& e : direction){int x = sr + e.first, y = sc + e.second;if((x >= 0 && x < image.size())&& (y >= 0 && y < image[0].size())&& (image[x][y] == val)){dfs(image, x, y, color, val);}}
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
{if(color == image[sr][sc]) return image;dfs(image, sr, sc, color, image[sr][sc]);return image;
}
- 岛屿数量
unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{-1, 0}
};
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visit, int i, int j)
{visit[i][j] = true;for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < grid.size())&& (y >= 0 && y < grid[0].size())&& (grid[x][y] == '1')&& (visit[x][y] == false)){dfs(grid, visit, x, y);}}
}
int numIslands(vector<vector<char>>& grid)
{vector<vector<bool>> visit(grid.size(), vector<bool>(grid[0].size()));int ret = 0;for(int i = 0; i < grid.size(); ++i){for(int j = 0; j < grid[0].size(); ++j){if(grid[i][j] == '1' && visit[i][j] == false){ret += 1;dfs(grid, visit, i, j);}}}return ret;
}
- 岛屿的最大面积
int area = 0;
unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{-1, 0}
};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, int i, int j)
{++area;visit[i][j] = true;for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < grid.size())&& (y >= 0 && y < grid[0].size())&& (grid[x][y] == 1)&& (visit[x][y] == false)){dfs(grid, visit, x, y);}}
}
int maxAreaOfIsland(vector<vector<int>>& grid)
{vector<vector<bool>> visit(grid.size(), vector<bool>(grid[0].size()));int ret = 0;for(int i = 0; i < grid.size(); ++i){for(int j = 0; j < grid[0].size(); ++j){if(grid[i][j] == 1 && visit[i][j] == false){dfs(grid, visit, i, j);if(area > ret) ret = area;area = 0;}}}return ret;
}
- 被围绕的区域
unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{-1, 0}
};
void dfs(vector<vector<char>>& board, vector<vector<bool>>& visit, int i, int j)
{visit[i][j] = true;for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < board.size())&& (y >= 0 && y < board[0].size())&& (board[x][y] == 'O')&& (visit[x][y] == false)){dfs(board, visit, x, y);}}
}
void solve(vector<vector<char>>& board)
{vector<vector<bool>> visit(board.size(), vector<bool>(board[0].size(), false));// 第一行 i=0for(int j = 0; j < board[0].size(); ++j){if(board[0][j] == 'O' && visit[0][j] == false){dfs(board, visit, 0, j);}}// 最后一行 i=board.size()-1for(int j = 0; j < board[0].size(); ++j){if(board[board.size()-1][j] == 'O' && visit[board.size()-1][j] == false){dfs(board, visit, board.size() - 1, j);}}// 第一列 j=0for(int i = 1; i < board.size() - 1; ++i){if(board[i][0] == 'O' && visit[i][0] == false){dfs(board, visit, i, 0);}}// 最后一列 j=board[0].size() - 1for(int i = 1; i < board.size() - 1; ++i){if(board[i][board[0].size() - 1] == 'O' && visit[i][board[0].size() - 1] == false){dfs(board, visit, i, board[0].size() - 1);}}for(int i = 0; i < board.size(); ++i){for(int j = 0; j < board[0].size(); ++j){if(board[i][j] == 'O' && visit[i][j] == false){board[i][j] = 'X';}}}
}
- 太平洋大西洋水流问题
unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{-1, 0}
};
int m, n;
void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visit, int i , int j)
{visit[i][j] = true;for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < m)&& (y >= 0 && y < n)&& (heights[i][j] <= heights[x][y])&& (visit[x][y] == false)){dfs(heights, visit, x, y);}}
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights)
{m = heights.size();n = heights[0].size();vector<vector<bool>> visit1(m, vector<bool>(n, false));vector<vector<bool>> visit2(m, vector<bool>(n, false));// 第一行 i=0for(int j = 0; j < n; ++j){if(visit1[0][j] == false){dfs(heights, visit1, 0, j);}}// 第一列 j=0for(int i = 0; i < m; ++i){if(visit1[i][0] == false){dfs(heights, visit1, i, 0);}}// 最后一行 i=m-1for(int j = 0; j < n; ++j){if(visit2[m-1][j] == false){dfs(heights, visit2, m-1, j);}}// 最后一列 j=n-1for(int i = 0; i < m; ++i){if(visit2[i][n-1] == false){dfs(heights, visit2, i, n-1);}}vector<vector<int>> ret;for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(visit1[i][j] && visit2[i][j]){ret.push_back({i, j});}}}return ret;
}
- 扫雷游戏
unordered_multimap<int, int> direction = {{-1, -1},{-1, 0},{-1, 1},{0, -1},{0, 1},{1, -1},{1, 0},{1, 1}
};
void dfs(vector<vector<char>>& board, int i, int j)
{char ch = '0';for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < board.size())&& (y >= 0 && y < board[0].size())&& (board[x][y] == 'M'))++ch;}if(ch > '0') {board[i][j] = ch;return;}board[i][j] = 'B';for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < board.size())&& (y >= 0 && y < board[0].size())&& (board[x][y] == 'E'))dfs(board, x, y);}
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click)
{int r = click[0], c = click[1];if(board[r][c] != 'M' && board[r][c] != 'E') return board;if(board[r][c] == 'M'){board[r][c] = 'X';return board;}// board[r][c]是未挖出的的空方块 - 'E'dfs(board, r, c);return board;
}
- 衣橱整理
int ret = 0;
unordered_multimap<int, int> direction = {{0, 1},{0, -1},{1, 0},{1, -1}
};
int digit(int x)
{int sum = 0;while(x){sum += (x % 10);x /= 10;}return sum;
}
void dfs(vector<vector<bool>>& visit, int i, int j, int cnt)
{++ret;visit[i][j] = true;for(auto& e : direction){int x = i + e.first, y = j + e.second;if((x >= 0 && x < visit.size())&& (y >= 0 && y < visit[0].size())&& (visit[x][y] == false)&& ((digit(x) + digit(y) <= cnt))){dfs(visit, x, y, cnt);}}
}
int wardrobeFinishing(int m, int n, int cnt)
{vector<vector<bool>> visit(m, vector<bool>(n, false));dfs(visit, 0, 0, cnt);return ret;
}