【Day44LeetCode】图论问题Ⅱ

一、图论问题 Ⅱ 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; }