# 图论第2天----第1020题、第130题
又继续开始修行,把图论这块补上,估计要个5-6天时间。
一、第1020题–飞地的数量
跟前面做的思路差不多,其实有另外一种思路。我这里是在遍历每块岛屿时,判断是否四周都是水,进而再统计数量。另一种思路,与130思路差不多,从边上开始遍历,要遍历2遍。文章来源:https://www.toymoban.com/news/detail-726571.html
class Solution {
public:
int count;
int result = 0;
bool flag;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y){
for (int i=0; i<4; i++){
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if(nextx <0 || nextx >=grid.size() || nexty <0 || nexty >= grid[0].size()){
flag = true;
continue;
}
if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){
visited[nextx][nexty] = true;
count++;
dfs(grid, visited, nextx, nexty);
}
}
}
int numEnclaves(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<bool>> visited(n, vector<bool>(m, false));
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(!visited[i][j] && grid[i][j] == 1){
visited[i][j] = true;
flag = false;
count = 1;
dfs(grid, visited, i, j);
cout << flag << ' ' << count << endl;
if (!flag) result += count;
}
}
}
return result;
}
};
二、第130题–被围绕的区域
遍历2遍。第一遍从边上开始遍历,把边上的岛屿做标记,记为’A’。这样边上的岛屿(‘A’)与中间的岛屿(‘O’)区分开了。第二遍遍历时,每个元素都遍历到,把’O’变为’X’,把’A’变为’O’,就把边上边上的岛屿留下了。文章来源地址https://www.toymoban.com/news/detail-726571.html
class Solution {
public:
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
void dfs(vector<vector<char>>& board, int x, int y){
board[x][y] = 'A';
for(int i=0; i<4; i++){
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if(nextx <0 || nexty <0 || nextx >=board.size() || nexty >=board[0].size()) continue;
if(board[nextx][nexty] == 'X' || board[nextx][nexty] == 'A') continue;
dfs(board, nextx, nexty);
}
}
void solve(vector<vector<char>>& board) {
int n = board.size();
int m = board[0].size();
for(int i=0; i<n; i++){
if(board[i][0] == 'O') dfs(board, i, 0);
if(board[i][m-1] == 'O') dfs(board, i, m-1);
}
for(int j=0; j<m; j++){
if(board[0][j] == 'O') dfs(board, 0, j);
if(board[n-1][j] == 'O') dfs(board, n-1, j);
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(board[i][j] == 'O') board[i][j] = 'X';
if(board[i][j] == 'A') board[i][j] = 'O';
}
}
}
};
到了这里,关于图论第2天----第1020题、第130题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!