【Day45 LeetCode】图论题目 Ⅲ

一、图论题目 Ⅲ

1、淹没孤岛

这题只能从边界开始扩散，将靠近边界的陆地标志，表示不是孤岛，最后将孤岛淹没，将不是孤岛标志回陆地。

1. # include<iostream>
2. # include<vector>
4. using namespace std;
6. void dfs(vector<vector<int>> &graph, int i, int j){
7.     if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[i][j]!=1)
8.         return;
9.     graph[i][j] = 2;
10.     dfs(graph, i+1, j);
11.     dfs(graph, i-1, j);
12.     dfs(graph, i, j+1);
13.     dfs(graph, i, j-1);
14. }
16. int main(){
17.     int n, m;
18.     cin >> n >> m;
19.     vector<vector<int>> graph(n, vector<int>(m));
20.     for(int i=0; i<n; ++i)
21.         for(int j=0; j<m; ++j)
22.             cin >> graph[i][j];
23.    
24.     // 步骤一：
25.     // 从左侧边，和右侧边 向中间遍历
26.     for (int i = 0; i < n; i++) {
27.         if (graph[i][0] == 1) dfs(graph, i, 0);
28.         if (graph[i][m - 1] == 1) dfs(graph, i, m - 1);
29.     }
31.     // 从上边和下边 向中间遍历
32.     for (int j = 0; j < m; j++) {
33.         if (graph[0][j] == 1) dfs(graph, 0, j);
34.         if (graph[n - 1][j] == 1) dfs(graph, n - 1, j);
35.     }
38.     for (int i = 0; i < n; i++) {
39.         for (int j = 0; j < m; j++) {
40.             if (graph[i][j] == 1) graph[i][j] = 0;
41.             if (graph[i][j] == 2) graph[i][j] = 1;
42.         }
43.     }
44.     for (int i = 0; i < n; i++) {
45.         for (int j = 0; j < m; j++) {
46.             cout << graph[i][j] << " ";
47.         }
48.         cout << endl;
49.     }
50.     return 0;
51. }

复制代码

2、水流题目

如果想着从当前点向两个边界移动的话，时间复杂度过高，因为需要遍历每个点，每个点又需要扩散到两个边界。如果我们逆向思维，想着从边界出发去找可达的点，这一下就豁然开朗了。

1. # include<iostream>
2. # include<vector>
4. using namespace std;
6. vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
7. void dfs(vector<vector<int>> &graph, vector<vector<bool>> &vis,int ii, int jj){
8.     if(vis[ii][jj])
9.         return;
10.     vis[ii][jj] = true;
11.     for(auto xy : dirs){
12.         int i = ii + xy[0], j = jj + xy[1];
13.         if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[ii][jj] > graph[i][j] || vis[i][j])
14.             continue;
15.         dfs(graph, vis, i, j);
16.     }
17. }
20. int main(){
21.     int n, m;
22.     cin >> n >> m;
23.     vector<vector<int>> graph(n, vector<int>(m));
24.     for(int i=0; i<n; ++i)
25.         for(int j=0; j<m; ++j)
26.             cin >> graph[i][j];
27.    
28.     vector<vector<bool>> vis1(n, vector<bool>(m, false));
29.     vector<vector<bool>> vis2(n, vector<bool>(m, false));
30.    
31.     for(int i=0; i<n; ++i){
32.         dfs(graph, vis1, i, 0);
33.         dfs(graph, vis2, i, m-1);
34.     }
35.     for(int i=0; i<m; ++i){
36.         dfs(graph, vis1, 0, i);
37.         dfs(graph, vis2, n-1, i);
38.     }
39.     for(int i=0; i<n; ++i){
40.         for(int j=0; j<m; ++j){
41.             if(vis1[i][j] && vis2[i][j])
42.                 cout << i << " " << j << endl;
43.         }
44.     }
45.     return 0;
46. }

复制代码

3、建造最大岛屿

写了个很不优雅的代码，思路是 DFS遍历陆地，给每个岛屿一一对应的编号，并用哈希表记载编号与岛屿面积的对应关系。然后，第二次遍历图，碰到水域，遍历水域的四个方向上的编号，举行面积聚加，一个细节是需要用set举行去重，可能四个反向上存在编号雷同的区域。

1. # include<iostream>
2. # include<vector>
3. # include<unordered_map>
4. # include<unordered_set>
5. using namespace std;
7. int dfs(vector<vector<int>> &graph, int i, int j, int num){
8.     if(i<0 || i>=graph.size() || j<0 || j>=graph[0].size() || graph[i][j]!=1)
9.         return 0;
10.     graph[i][j] = num;
11.     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);
12. }
14. int main(){
15.     int n, m;
16.     cin >> n >> m;
17.     vector<vector<int>> graph(n, vector<int>(m));
18.     for(int i=0; i<n; ++i)
19.         for(int j=0; j<m; ++j)
20.             cin >> graph[i][j];
21.     unordered_map<int, int> mp; // 映射几号陆地 与 其面积关系
22.     mp[0] = 0;
23.     int idx = 2; // 几号陆地
24.     int ans = 0;
25.     for(int i=0; i<n; ++i){
26.         for(int j=0; j<m; ++j){
27.             if(graph[i][j]==1){
28.                 mp[idx] = dfs(graph, i, j, idx);
29.                 ans = max(ans, mp[idx]);
30.                 ++idx;
31.             }
32.         }
33.     }
34.     vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
35.     for(int i=0; i<n; ++i){
36.         for(int j=0; j<m; ++j){
37.             if(graph[i][j]==0){
38.                 int tmp = 1;
39.                 unordered_set<int> set;
40.                 for(auto xy : dirs){
41.                     int x = i + xy[0], y = j + xy[1];
42.                     if(x>=0 && x<n && y>=0 && y<m && set.find(graph[x][y])==set.end()){
43.                         set.insert(graph[x][y]);
44.                         tmp += mp[graph[x][y]];
45.                     }
46.                 }
47.                 ans = max(ans, tmp);
48.             }
49.         }
50.     }
51.     cout << ans << endl;
52.    
53.     return 0;
54. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。