【Day44 LeetCode】图论问题 Ⅱ

一、图论问题 Ⅱ

1、岛屿的最大面积

这题和上一篇博客求岛屿数量如出一辙，都是要找出所有岛屿，深度优先搜索代码如下：

# include<iostream>
# include<vector>using namespace std;int dfs(vector<vector<int>> &graph, int i, int j){if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[i][j]!=1)return 0;graph[i][j] = 2;return 1 + dfs(graph, i+1, j)+ dfs(graph, i-1, j)+ dfs(graph, i, j+1)+ dfs(graph, i, j-1);
}int main(){int n, m;cin >> n >> m;vector<vector<int>> graph(n, vector<int>(m));for(int i=0; i<n; ++i)for(int j=0; j<m; ++j)cin >> graph[i][j];int ans = 0;for(int i=0; i<n; ++i)for(int j=0; j<m; ++j)if(graph[i][j]==1)ans = max(ans, dfs(graph, i, j));cout << ans << endl;return 0;
}

广度优先搜索代码如下：

# include<iostream>
# include<vector>
#include<queue>using namespace std;vector<vector<int>> dirs({{0, 1}, {0, -1}, {1, 0}, {-1, 0}});
int bfs(vector<vector<int>> &graph, int ii, int jj){queue<pair<int, int>> q;q.push({ii, jj});graph[ii][jj] = 2;int res = 0;while(!q.empty()){auto cur = q.front(); q.pop();++res;for(auto xy : dirs){int i = cur.first + xy[0], j = cur.second + xy[1];if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[i][j]!=1)continue;graph[i][j] = 2;q.push({i, j});}}return res;
}int main(){int n, m;cin >> n >> m;vector<vector<int>> graph(n, vector<int>(m));for(int i=0; i<n; ++i)for(int j=0; j<m; ++j)cin >> graph[i][j];int ans = 0;for(int i=0; i<n; ++i)for(int j=0; j<m; ++j)if(graph[i][j]==1)ans = max(ans, bfs(graph, i, j));cout << ans << endl;return 0;
}

2、孤岛总面积

本质上还是要搜索所有岛屿，同时还得统计岛屿面积，将是孤岛的面积累加。这就涉及到不是孤岛的判断，遇到边界就不是孤岛，这个不要加入结果，我们只需要让函数的统计结果减去一个很大的数，从而保证不是孤岛的返回值是负数就好，最后结果只累加正数。这个能在之前的代码下做出最小的改动。
深度优先搜索代码如下：

# include<iostream>
# include<vector>using namespace std;int dfs(vector<vector<int>> &graph, int i, int j){if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[i][j]!=1)return 0;graph[i][j] = 2;int res = 1;if(i==0 || j==0 || i==graph.size()-1 || j==graph[0].size()-1)res -= 10000;res += dfs(graph, i+1, j)+ dfs(graph, i-1, j)+ dfs(graph, i, j+1)+ dfs(graph, i, j-1);return res;
}int main(){int n, m;cin >> n >> m;vector<vector<int>> graph(n, vector<int>(m));for(int i=0; i<n; ++i)for(int j=0; j<m; ++j)cin >> graph[i][j];int ans = 0;for(int i=0; i<n; ++i)for(int j=0; j<m; ++j)if(graph[i][j]==1)ans += max(0, dfs(graph, i, j));cout << ans << endl;return 0;
}

广度优先搜索代码如下：

# include<iostream>
# include<vector>
#include<queue>using namespace std;vector<vector<int>> dirs({{0, 1}, {0, -1}, {1, 0}, {-1, 0}});
int bfs(vector<vector<int>> &graph, int ii, int jj){queue<pair<int, int>> q;q.push({ii, jj});graph[ii][jj] = 2;int res = 0;while(!q.empty()){auto cur = q.front(); q.pop();++res;if(cur.first==0 || cur.second==0 || cur.first==graph.size()-1 || cur.second==graph[0].size()-1)res -= 10000;for(auto xy : dirs){int i = cur.first + xy[0], j = cur.second + xy[1];if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[i][j]!=1)continue;graph[i][j] = 2;q.push({i, j});}}return res;
}int main(){int n, m;cin >> n >> m;vector<vector<int>> graph(n, vector<int>(m));for(int i=0; i<n; ++i)for(int j=0; j<m; ++j)cin >> graph[i][j];int ans = 0;for(int i=0; i<n; ++i)for(int j=0; j<m; ++j)if(graph[i][j]==1)ans += max(0, bfs(graph, i, j));cout << ans << endl;return 0;
}