*算法练习（leetcode）第四十五天 | 101. 孤岛的总面积、102. 沉没孤岛、10 ...

101. 孤岛的总面积

题目地址
本题要求不与矩阵边缘相连的孤岛的总面积。先将与四个边缘相连的岛屿变为海洋，再统计剩余的孤岛的总面积。无需再标识访问过的结点，因为访问过后都变为海洋了。
时间复杂度：                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2)
空间复杂度：                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2)
DFS

1. // c++
2. #include<bits/stdc++.h>
3. using namespace std;
4. int direction[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};
5. int result = 0;
7. void pre_dfs(vector<vector<int>> &matrix, int x, int  y){
8.    
9.     matrix[x][y] = 0;
10.     result++;
11.     for(int i=0; i<4; i++){
12.         int nextx = x + direction[i][0];
13.         int nexty = y + direction[i][1];
14.         if(nextx>=matrix.size() || nexty>=matrix[0].size() || nextx<0 || nexty<0) continue;
15.         if(matrix[nextx][nexty]){
16.             matrix[nextx][nexty] = 0;
17.             
18.             pre_dfs(matrix, nextx, nexty);
19.         }
20.         
21.     }
22. }
24. int main(){
25.     int n,m;
26.     cin>>n>>m;
27.     vector<vector<int>> matrix(n, vector<int>(m, 0));
28.     for(int i=0; i<n; i++){
29.         for(int j=0; j<m; j++){
30.             cin>>matrix[i][j];
31.         }
32.     }
33.    
34.     for(int i=0; i<n; i++) {
35.         if(matrix[i][0]){
36.             pre_dfs(matrix, i, 0);
37.         }
38.         if(matrix[i][m-1]){
39.             pre_dfs(matrix, i, m-1);
40.         }
41.     }
42.     for(int j=0; j<m; j++){
43.         if(matrix[0][j]){
44.             pre_dfs(matrix, 0, j);
45.         }
46.         if(matrix[n-1][j]){
47.             pre_dfs(matrix, n-1, j);   
48.         }
49.       
50.     }
51.     result = 0;
52.     for(int i=0; i<n; i++){
53.         for(int j=0; j<m; j++){
54.             if(matrix[i][j]){
55.                 pre_dfs(matrix, i, j);   
56.             }
57.         }
58.     }
59.     cout<<result;
60.     return 0;
61. }

复制代码

BFS

1. // c++
2. #include<bits/stdc++.h>
3. using namespace std;
4. int direction[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};
5. int result = 0;
7. void pre_dfs(vector<vector<int>> &matrix, int x, int  y){
8.    
9.     matrix[x][y] = 0;
10.     result++;
11.     for(int i=0; i<4; i++){
12.         int nextx = x + direction[i][0];
13.         int nexty = y + direction[i][1];
14.         if(nextx>=matrix.size() || nexty>=matrix[0].size() || nextx<0 || nexty<0) continue;
15.         if(matrix[nextx][nexty]){
16.             matrix[nextx][nexty] = 0;
17.             
18.             pre_dfs(matrix, nextx, nexty);
19.         }
20.         
21.     }
22. }
24. void pre_bfs(vector<vector<int>> &matrix, int x, int  y){
25.     queue<pair<int, int>> que;
26.     que.push({x, y});
27.     matrix[x][y] = 0;
28.     result++;
29.     while(!que.empty()){
30.         pair<int, int> cur = que.front();
31.         que.pop();
32.         int curx = cur.first;
33.         int cury = cur.second;
34.         for(int i=0; i<4; i++){
35.             int nextx = curx + direction[i][0];
36.             int nexty = cury + direction[i][1];
37.             if(nextx>=matrix.size() || nexty>=matrix[0].size() || nextx<0 || nexty<0) continue;
38.             if(matrix[nextx][nexty]){
39.                 matrix[nextx][nexty] = 0;
40.                 result++;
41.                 que.push({nextx, nexty});
42.             }
43.         }
44.         
45.     }
46. }
48. int main(){
49.     int n,m;
50.     cin>>n>>m;
51.     vector<vector<int>> matrix(n, vector<int>(m, 0));
52.     for(int i=0; i<n; i++){
53.         for(int j=0; j<m; j++){
54.             cin>>matrix[i][j];
55.         }
56.     }
57.     /*
58.     // dfs
59.     for(int i=0; i<n; i++) {
60.         if(matrix[i][0]){
61.             pre_dfs(matrix, i, 0);
62.         }
63.         if(matrix[i][m-1]){
64.             pre_dfs(matrix, i, m-1);
65.         }
66.     }
67.     for(int j=0; j<m; j++){
68.         if(matrix[0][j]){
69.             pre_dfs(matrix, 0, j);
70.         }
71.         if(matrix[n-1][j]){
72.             pre_dfs(matrix, n-1, j);   
73.         }
74.       
75.     }
76.     */
77.     // bfs
78.     for(int i=0; i<n; i++) {
79.         if(matrix[i][0]){
80.             pre_bfs(matrix, i, 0);
81.         }
82.         if(matrix[i][m-1]){
83.             pre_bfs(matrix, i, m-1);
84.         }
85.     }
86.     for(int j=0; j<m; j++){
87.         if(matrix[0][j]){
88.             pre_bfs(matrix, 0, j);
89.         }
90.         if(matrix[n-1][j]){
91.             pre_bfs(matrix, n-1, j);   
92.         }
93.       
94.     }
95.     result = 0;
96.     for(int i=0; i<n; i++){
97.         for(int j=0; j<m; j++){
98.             if(matrix[i][j]){
99.                 // pre_dfs(matrix, i, j);   
100.                 pre_bfs(matrix, i, j);
101.             }
102.         }
103.     }
104.     cout<<result;
105.     return 0;
106. }

复制代码

102. 沉没孤岛

题目地址
本题是上一题的反向操纵
先把非孤岛做访问标记，再对剩余陆地举行操纵。
时间复杂度：                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2)
空间复杂度：                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2)
DFS

1. // c++
2. #include<bits/stdc++.h>
3. using namespace std;
4. int direction[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
5. void pre_dfs(const vector<vector<int>>& matrix,
6.             vector<vector<bool>>& visited,
7.             int x, int y){
8.     visited[x][y] = true;
9.     for(int i=0; i<4; i++){
10.         int nextx = x + direction[i][0];
11.         int nexty = y + direction[i][1];
12.         if(nextx>=matrix.size() || nexty>=matrix.size() ||nextx<0 || nexty<0) continue;
13.         if(matrix[nextx][nexty] && !visited[nextx][nexty]){
14.             // visited[nextx][nexty] = true;
15.             pre_dfs(matrix, visited, nextx, nexty);
16.         }
17.     }
18. }
20. void dfs(vector<vector<int>>& matrix,
21.             vector<vector<bool>>& visited,
22.             int x, int y){
23.     matrix[x][y] = 0;
24.     for(int i=0; i<4; i++){
25.         int nextx = x + direction[i][0];
26.         int nexty = y + direction[i][1];
27.         if(nextx>=matrix.size() || nexty>=matrix.size() ||nextx<0 || nexty<0) continue;
28.         if(matrix[nextx][nexty] && !visited[nextx][nexty]){
29.             visited[nextx][nexty] = true;
30.             dfs(matrix, visited, nextx, nexty);
31.         }
32.     }
33. }
34. int main(){
35.     int n,m;
36.     cin>>n>>m;
37.     vector<vector<int>> matrix(n, vector<int>(m, 0));
38.     vector<vector<bool>> visited(n, vector<bool>(m, false));
39.     for(int i=0; i<n; i++){
40.         for(int j=0; j<m; j++){
41.             cin>>matrix[i][j];
42.         }
43.     }
44.     for(int i=0; i<n; i++){
45.         if(matrix[i][0] && !visited[i][0]) pre_dfs(matrix, visited, i, 0);
46.         if(matrix[i][m-1] && !visited[i][m-1]) pre_dfs(matrix, visited, i, m-1);
47.     }
48.    
49.     for(int j=0; j<m; j++){
50.         if(matrix[0][j] && !visited[0][j]) pre_dfs(matrix, visited, 0, j);
51.         if(matrix[n-1][j] && !visited[n-1][j]) pre_dfs(matrix, visited, n-1, j);
52.     }
53.    
54.     for(int i=0; i<n; i++){
55.         
56.         
57.         for(int j=0; j<m; j++){
58.             if(matrix[i][j] && !visited[i][j]){
59.                 visited[i][j] = true;
60.                 dfs(matrix,visited, i, j);
61.             }
62.         }
63.         for(int j=0; j<m; j++) cout<<matrix[i][j]<<" ";
64.         cout<<endl;
65.         
66.     }
67.    
68.    
69.    
70.    
71.     return 0;
72. }

复制代码

BFS

1. //c++
2. #include<bits/stdc++.h>
3. using namespace std;
4. int direction[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
5. void pre_dfs(const vector<vector<int>>& matrix,
6.             vector<vector<bool>>& visited,
7.             int x, int y){
8.     visited[x][y] = true;
9.     for(int i=0; i<4; i++){
10.         int nextx = x + direction[i][0];
11.         int nexty = y + direction[i][1];
12.         if(nextx>=matrix.size() || nexty>=matrix.size() ||nextx<0 || nexty<0) continue;
13.         if(matrix[nextx][nexty] && !visited[nextx][nexty]){
14.             // visited[nextx][nexty] = true;
15.             pre_dfs(matrix, visited, nextx, nexty);
16.         }
17.     }
18. }
20. void dfs(vector<vector<int>>& matrix,
21.             vector<vector<bool>>& visited,
22.             int x, int y){
23.     matrix[x][y] = 0;
24.    
25.     for(int i=0; i<4; i++){
26.         int nextx = x + direction[i][0];
27.         int nexty = y + direction[i][1];
28.         if(nextx>=matrix.size() || nexty>=matrix.size() ||nextx<0 || nexty<0) continue;
29.         if(matrix[nextx][nexty] && !visited[nextx][nexty]){
30.             visited[nextx][nexty] = true;
31.             dfs(matrix, visited, nextx, nexty);
32.         }
33.     }
34. }
36. void pre_bfs(const vector<vector<int>>& matrix,
37.             vector<vector<bool>>& visited,
38.             int x, int y){
39.     visited[x][y] = true;
40.     queue<pair<int, int>> que;
41.     que.push({x,y});
42.     while(!que.empty()){
43.         pair<int, int> cur = que.front();
44.         que.pop();
45.         int curx = cur.first;
46.         int cury = cur.second;
47.         for(int i=0; i<4; i++){
48.             int nextx = curx + direction[i][0];
49.             int nexty = cury + direction[i][1];
50.             if(nextx>=matrix.size() || nexty>=matrix.size() ||nextx<0 || nexty<0) continue;
51.             if(matrix[nextx][nexty] && !visited[nextx][nexty]){
52.                 visited[nextx][nexty] = true;
53.                 que.push({nextx, nexty});
54.             }
55.         }
56.     }
57. }
59. void bfs(vector<vector<int>>& matrix,
60.             vector<vector<bool>>& visited,
61.             int x, int y){
62.     visited[x][y] = true;
63.     matrix[x][y] = 0;
64.     queue<pair<int, int>> que;
65.     que.push({x,y});
66.     while(!que.empty()){
67.         pair<int, int> cur = que.front();
68.         que.pop();
69.         int curx = cur.first;
70.         int cury = cur.second;
71.         for(int i=0; i<4; i++){
72.             int nextx = curx + direction[i][0];
73.             int nexty = cury + direction[i][1];
74.             if(nextx>=matrix.size() || nexty>=matrix.size() ||nextx<0 || nexty<0) continue;
75.             if(matrix[nextx][nexty] && !visited[nextx][nexty]){
76.                 visited[nextx][nexty] = true;
77.                 matrix[nextx][nexty] = 0;
78.                 que.push({nextx, nexty});
79.             }
80.         }
81.     }
82. }
83. int main(){
84.     int n,m;
85.     cin>>n>>m;
86.     vector<vector<int>> matrix(n, vector<int>(m, 0));
87.     vector<vector<bool>> visited(n, vector<bool>(m, false));
88.     for(int i=0; i<n; i++){
89.         for(int j=0; j<m; j++){
90.             cin>>matrix[i][j];
91.         }
92.     }
93.     /*
94.     // dfs
95.     for(int i=0; i<n; i++){
96.         if(matrix[i][0] && !visited[i][0]) pre_dfs(matrix, visited, i, 0);
97.         if(matrix[i][m-1] && !visited[i][m-1]) pre_dfs(matrix, visited, i, m-1);
98.     }
99.    
100.     for(int j=0; j<m; j++){
101.         if(matrix[0][j] && !visited[0][j]) pre_dfs(matrix, visited, 0, j);
102.         if(matrix[n-1][j] && !visited[n-1][j]) pre_dfs(matrix, visited, n-1, j);
103.     }
104.     */
105.     // bfs
106.     for(int i=0; i<n; i++){
107.         if(matrix[i][0] && !visited[i][0]) pre_bfs(matrix, visited, i, 0);
108.         if(matrix[i][m-1] && !visited[i][m-1]) pre_bfs(matrix, visited, i, m-1);
109.     }
110.    
111.     for(int j=0; j<m; j++){
112.         if(matrix[0][j] && !visited[0][j]) pre_bfs(matrix, visited, 0, j);
113.         if(matrix[n-1][j] && !visited[n-1][j]) pre_bfs(matrix, visited, n-1, j);
114.     }
115.    
116.     for(int i=0; i<n; i++){
117.         
118.         
119.         for(int j=0; j<m; j++){
120.             if(matrix[i][j] && !visited[i][j]){
121.                 // visited[i][j] = true;
122.                 // dfs(matrix,visited, i, j);
123.                 bfs(matrix,visited, i, j);
124.             }
125.         }
126.         for(int j=0; j<m; j++) cout<<matrix[i][j]<<" ";
127.         cout<<endl;
128.         
129.     }
130.    
131.    
132.    
133.    
134.     return 0;
135. }

复制代码

*103. 水流问题

题目地址
利用两个标识访问的数组分别从两组边界出发举行dfs遍历，利用从低向高流(反向流)来分别记录两组边界的结点。末了两组边界的交集就是本题答案。
思路
时间复杂度：                                    O                         (                         m                         ∗                         n                         )                              O(m*n)                  O(m∗n)
空间复杂度：                                    O                         (                         m                         ∗                         n                         )                              O(m*n)                  O(m∗n)

1. // c++
2. #include<bits/stdc++.h>
3. using namespace std;
4. int direction[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
5. void dfs(const vector<vector<int>> &matrix,
6.         vector<vector<bool>> &visited,
7.         int x, int y){
8.     visited[x][y] = true;
9.    
10.     for(int i=0; i<4; i++){
11.         int nextx = x + direction[i][0];
12.         int nexty = y + direction[i][1];
13.         if(nextx>=matrix.size() || nexty>=matrix[0].size() || nextx<0 || nexty<0) continue;
14.         if(matrix[x][y]>matrix[nextx][nexty]) continue;
15.         if(!visited[nextx][nexty]) dfs(matrix, visited, nextx, nexty);
16.     }
17. }
19. int main(){
20.     int n,m;
21.     cin>>n>>m;
22.     vector<vector<int>> matrix(n, vector<int>(m, 0));
23.     vector<vector<bool>> first(n, vector<bool>(m, false));
24.     vector<vector<bool>> second(n, vector<bool>(m, false));
25.     for(int i=0; i<n; i++){
26.         for(int j=0; j<m; j++){
27.             cin>>matrix[i][j];
28.         }
29.     }
30.    
31.     for(int i=0; i<n; i++){
32.         dfs(matrix, first, i, 0);
33.         dfs(matrix, second, i, m-1);
34.     }
35.     for(int j=0; j<m; j++){
36.         dfs(matrix, first, 0, j);
37.         dfs(matrix, second, n-1, j);
38.     }
39.    
40.     for(int i=0; i<n; i++){
41.         for(int j=0; j<m; j++){
42.             if(first[i][j] && second[i][j]) cout<<i<<" "<<j<<endl;
43.         }
44.     }
45.    
46.     return 0;   
47. }

复制代码

*104. 制作最大岛屿

题目地址
分两阶段。

• 先对地图中的陆地举行一次遍历，对每一个岛屿举行标记，同时盘算每个岛屿的面积。
  
• 再对地图中的水域举行一次遍历，盘算每一个水域酿成陆地后的一连陆地面积，就是把水域四个方向的陆地面积求和，再加上1体现当前水域变为陆地。
  

题解
时间复杂度：                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2)
空间复杂度：                                    O                         (                                   n                            2                                  )                              O(n^2)                  O(n2)

1. // c++
2. #include<bits/stdc++.h>
3. using namespace std;
4. int direction[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};
6. void dfs(vector<vector<int>> &matrix,
7.         vector<vector<bool>> &visited,
8.         int x, int  y, int &count, int mark){
9.     visited[x][y] = true;
10.     matrix[x][y] = mark;
11.     count++;
12.    
13.     for(int i=0; i<4; i++){
14.         int nextx = x + direction[i][0];
15.         int nexty = y + direction[i][1];
17.         if(nextx>=matrix.size() || nexty>=matrix[0].size() || nextx<0 || nexty<0) continue;
18.         if(matrix[nextx][nexty] == 1 && !visited[nextx][nexty]){
19.             dfs(matrix, visited, nextx, nexty, count, mark);
20.         }
21.     }
22. }
24. int main(){
25.     int n,m;
26.     cin>>n>>m;
27.     vector<vector<int>> matrix(n, vector<int>(m, 0));
28.     for(int i=0; i<n; i++){
29.         for(int j=0; j<m; j++){
30.             cin>>matrix[i][j];
31.         }
32.     }
33.     vector<vector<bool>> visited(n, vector<bool>(m, false));
34.     // 记录岛屿面积
35.     unordered_map<int, int> markCount;
36.     int mark = 2;
37.     int count;
38.     bool isAllGrid = true;
39.     // 第一阶段：记录岛屿大小
40.     for(int i=0; i<n; i++){
41.         for(int j=0; j<m; j++){
42.             if(matrix[i][j] == 0) isAllGrid = false;
43.             if(matrix[i][j] == 1 && !visited[i][j]){
44.                 count = 0;
45.                 dfs(matrix, visited, i, j, count, mark);
46.                 markCount[mark] = count;
47.                 mark++;
48.             }
49.         }
50.     }
51.     if(isAllGrid) {
52.         cout<<n*m<<endl;
53.         return 0;
54.     }
55.     int result = 0;
56.     // 第二阶段
57.     for(int i=0; i<n; i++){
58.         for(int j=0; j<m; j++){
59.             // 非陆地 计算把当前水域变为陆地的最大面积
60.             if(matrix[i][j] == 0){
61.                 unordered_set<int> lands;
62.                 // 把当前水域变为陆地
63.                 count = 1;
64.                 // 遍历当前水域的四个方向 把四个方向的陆地面积都加起来
65.                 for(int k=0; k<4; k++){
66.                     int nextx = i + direction[k][0];
67.                     int nexty = j + direction[k][1];
68.                     if(nextx>=matrix.size() || nexty>=matrix[0].size() || nextx<0 || nexty<0) continue;
69.                     // 当前陆地已加入
70.                     if(lands.count(matrix[nextx][nexty])>0) continue;
71.                     
72.                     count += markCount[matrix[nextx][nexty]];
73.                     // 标记已加入的节点
74.                     lands.insert(matrix[nextx][nexty]);
75.                 }
76.             }
77.             
78.             result = max(result, count);
79.         }
80.     }
81.     cout<<result;
82.     return 0;
83. }

复制代码

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