一、图论问题 Ⅲ
1、沉没孤岛
这题只能从边界开始扩散，将靠近边界的陆地标记，表示不是孤岛，最后将孤岛沉没，将不是孤岛标记回陆地。
# include<iostream>
# include<vector>using namespace std;void 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;graph[i][j] = 2;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];// 步骤一：// 从左侧边，和右侧边 向中间遍历for (int i = 0; i < n; i++) {if (graph[i][0] == 1) dfs(graph, i, 0);if (graph[i][m - 1] == 1) dfs(graph, i, m - 1);}// 从上边和下边 向中间遍历for (int j = 0; j < m; j++) {if (graph[0][j] == 1) dfs(graph, 0, j);if (graph[n - 1][j] == 1) dfs(graph, n - 1, j);}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (graph[i][j] == 1) graph[i][j] = 0;if (graph[i][j] == 2) graph[i][j] = 1;}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cout << graph[i][j] << " ";}cout << endl;}return 0;
}
2、水流问题
如果想着从当前点向两个边界移动的话，时间复杂度过高，因为需要遍历每个点，每个点又需要扩散到两个边界。如果我们逆向思维，想着从边界出发去找可达的点，这一下就豁然开朗了。
# include<iostream>
# include<vector>using namespace std;vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(vector<vector<int>> &graph, vector<vector<bool>> &vis,int ii, int jj){if(vis[ii][jj])return;vis[ii][jj] = true;for(auto xy : dirs){int i = ii + xy[0], j = jj + xy[1];if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[ii][jj] > graph[i][j] || vis[i][j])continue;dfs(graph, vis, i, j);}
}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];vector<vector<bool>> vis1(n, vector<bool>(m, false));vector<vector<bool>> vis2(n, vector<bool>(m, false)); for(int i=0; i<n; ++i){dfs(graph, vis1, i, 0);dfs(graph, vis2, i, m-1);}for(int i=0; i<m; ++i){dfs(graph, vis1, 0, i);dfs(graph, vis2, n-1, i);}for(int i=0; i<n; ++i){for(int j=0; j<m; ++j){if(vis1[i][j] && vis2[i][j])cout << i << " " << j << endl;}}return 0;
}
3、建造最大岛屿
写了个很不优雅的代码，思路是 DFS遍历陆地，给每个岛屿一一对应的编号，并用哈希表记录编号与岛屿面积的对应关系。然后，第二次遍历图，遇到水域，遍历水域的四个方向上的编号，进行面积累加，一个细节是需要用set进行去重，可能四个反向上存在编号相同的区域。
# include<iostream>
# include<vector>
# include<unordered_map>
# include<unordered_set>
using namespace std;int dfs(vector<vector<int>> &graph, int i, int j, int num){if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[i][j]!=1)return 0;graph[i][j] = num;return 1 + dfs(graph, i+1, j, num)+ dfs(graph, i-1, j, num)+ dfs(graph, i, j+1, num)+ dfs(graph, i, j-1, num);
} 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];unordered_map<int, int> mp; // 映射几号陆地 与 其面积关系mp[0] = 0;int idx = 2; // 几号陆地 int ans = 0;for(int i=0; i<n; ++i){for(int j=0; j<m; ++j){if(graph[i][j]==1){mp[idx] = dfs(graph, i, j, idx);ans = max(ans, mp[idx]);++idx;}}}vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};for(int i=0; i<n; ++i){for(int j=0; j<m; ++j){if(graph[i][j]==0){int tmp = 1;unordered_set<int> set;for(auto xy : dirs){int x = i + xy[0], y = j + xy[1];if(x>=0 && x<n && y>=0 && y<m && set.find(graph[x][y])==set.end()){set.insert(graph[x][y]);tmp += mp[graph[x][y]];}}ans = max(ans, tmp);}}}cout << ans << endl;return 0;
}
