101. 孤島的總面積

題目地址

本題要求不與矩陣邊緣相連的孤島的總面積。先將與四個邊緣相連的島嶼變為海洋，再統計剩余的孤島的總面積。無需再標識訪問過的結點，因為訪問過后都變為海洋了。

時間復雜度： $O(n^2)$
空間復雜度： $O(n^2)$

DFS

// c++
#include<bits/stdc++.h>
using namespace std;
int direction[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};
int result = 0;void pre_dfs(vector<vector<int>> &matrix, int x, int  y){matrix[x][y] = 0;result++;for(int i=0; i<4; i++){int nextx = x + direction[i][0];int nexty = y + direction[i][1];if(nextx>=matrix.size() || nexty>=matrix[0].size() || nextx<0 || nexty<0) continue;if(matrix[nextx][nexty]){matrix[nextx][nexty] = 0;pre_dfs(matrix, nextx, nexty);}}
}int main(){int n,m;cin>>n>>m;vector<vector<int>> matrix(n, vector<int>(m, 0));for(int i=0; i<n; i++){for(int j=0; j<m; j++){cin>>matrix[i][j];}}for(int i=0; i<n; i++) {if(matrix[i][0]){pre_dfs(matrix, i, 0);}if(matrix[i][m-1]){pre_dfs(matrix, i, m-1);}}for(int j=0; j<m; j++){if(matrix[0][j]){pre_dfs(matrix, 0, j);}if(matrix[n-1][j]){pre_dfs(matrix, n-1, j);   }}result = 0;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(matrix[i][j]){pre_dfs(matrix, i, j);   }}}cout<<result;return 0;
}

BFS

// c++
#include<bits/stdc++.h>
using namespace std;
int direction[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};
int result = 0;void pre_dfs(vector<vector<int>> &matrix, int x, int  y){matrix[x][y] = 0;result++;for(int i=0; i<4; i++){int nextx = x + direction[i][0];int nexty = y + direction[i][1];if(nextx>=matrix.size() || nexty>=matrix[0].size() || nextx<0 || nexty<0) continue;if(matrix[nextx][nexty]){matrix[nextx][nexty] = 0;pre_dfs(matrix, nextx, nexty);}}
}void pre_bfs(vector<vector<int>> &matrix, int x, int  y){queue<pair<int, int>> que;que.push({x, y});matrix[x][y] = 0;result++;while(!que.empty()){pair<int, int> cur = que.front();que.pop();int curx = cur.first;int cury = cur.second;for(int i=0; i<4; i++){int nextx = curx + direction[i][0];int nexty = cury + direction[i][1];if(nextx>=matrix.size() || nexty>=matrix[0].size() || nextx<0 || nexty<0) continue;if(matrix[nextx][nexty]){matrix[nextx][nexty] = 0;result++;que.push({nextx, nexty});}}}
}int main(){int n,m;cin>>n>>m;vector<vector<int>> matrix(n, vector<int>(m, 0));for(int i=0; i<n; i++){for(int j=0; j<m; j++){cin>>matrix[i][j];}}/*// dfsfor(int i=0; i<n; i++) {if(matrix[i][0]){pre_dfs(matrix, i, 0);}if(matrix[i][m-1]){pre_dfs(matrix, i, m-1);}}for(int j=0; j<m; j++){if(matrix[0][j]){pre_dfs(matrix, 0, j);}if(matrix[n-1][j]){pre_dfs(matrix, n-1, j);   }}*/// bfsfor(int i=0; i<n; i++) {if(matrix[i][0]){pre_bfs(matrix, i, 0);}if(matrix[i][m-1]){pre_bfs(matrix, i, m-1);}}for(int j=0; j<m; j++){if(matrix[0][j]){pre_bfs(matrix, 0, j);}if(matrix[n-1][j]){pre_bfs(matrix, n-1, j);   }}result = 0;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(matrix[i][j]){// pre_dfs(matrix, i, j);   pre_bfs(matrix, i, j);}}}cout<<result;return 0;
}

102. 沉沒孤島

題目地址

本題是上一題的反向操作

先把非孤島做訪問標記，再對剩余陸地進行操作。

時間復雜度： $O(n^2)$
空間復雜度： $O(n^2)$

DFS

// c++
#include<bits/stdc++.h>
using namespace std;
int direction[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
void pre_dfs(const vector<vector<int>>& matrix,vector<vector<bool>>& visited,int x, int y){visited[x][y] = true;for(int i=0; i<4; i++){int nextx = x + direction[i][0];int nexty = y + direction[i][1];if(nextx>=matrix.size() || nexty>=matrix.size() ||nextx<0 || nexty<0) continue;if(matrix[nextx][nexty] && !visited[nextx][nexty]){// visited[nextx][nexty] = true;pre_dfs(matrix, visited, nextx, nexty);}}
}void dfs(vector<vector<int>>& matrix,vector<vector<bool>>& visited,int x, int y){matrix[x][y] = 0;for(int i=0; i<4; i++){int nextx = x + direction[i][0];int nexty = y + direction[i][1];if(nextx>=matrix.size() || nexty>=matrix.size() ||nextx<0 || nexty<0) continue;if(matrix[nextx][nexty] && !visited[nextx][nexty]){visited[nextx][nexty] = true;dfs(matrix, visited, nextx, nexty);}}
}
int main(){int n,m;cin>>n>>m;vector<vector<int>> matrix(n, vector<int>(m, 0));vector<vector<bool>> visited(n, vector<bool>(m, false));for(int i=0; i<n; i++){for(int j=0; j<m; j++){cin>>matrix[i][j];}}for(int i=0; i<n; i++){if(matrix[i][0] && !visited[i][0]) pre_dfs(matrix, visited, i, 0);if(matrix[i][m-1] && !visited[i][m-1]) pre_dfs(matrix, visited, i, m-1);}for(int j=0; j<m; j++){if(matrix[0][j] && !visited[0][j]) pre_dfs(matrix, visited, 0, j);if(matrix[n-1][j] && !visited[n-1][j]) pre_dfs(matrix, visited, n-1, j);}for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(matrix[i][j] && !visited[i][j]){visited[i][j] = true;dfs(matrix,visited, i, j);}}for(int j=0; j<m; j++) cout<<matrix[i][j]<<" ";cout<<endl;}return 0;
}

BFS

//c++
#include<bits/stdc++.h>
using namespace std;
int direction[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
void pre_dfs(const vector<vector<int>>& matrix,vector<vector<bool>>& visited,int x, int y){visited[x][y] = true;for(int i=0; i<4; i++){int nextx = x + direction[i][0];int nexty = y + direction[i][1];if(nextx>=matrix.size() || nexty>=matrix.size() ||nextx<0 || nexty<0) continue;if(matrix[nextx][nexty] && !visited[nextx][nexty]){// visited[nextx][nexty] = true;pre_dfs(matrix, visited, nextx, nexty);}}
}void dfs(vector<vector<int>>& matrix,vector<vector<bool>>& visited,int x, int y){matrix[x][y] = 0;for(int i=0; i<4; i++){int nextx = x + direction[i][0];int nexty = y + direction[i][1];if(nextx>=matrix.size() || nexty>=matrix.size() ||nextx<0 || nexty<0) continue;if(matrix[nextx][nexty] && !visited[nextx][nexty]){visited[nextx][nexty] = true;dfs(matrix, visited, nextx, nexty);}}
}void pre_bfs(const vector<vector<int>>& matrix,vector<vector<bool>>& visited,int x, int y){visited[x][y] = true;queue<pair<int, int>> que;que.push({x,y});while(!que.empty()){pair<int, int> cur = que.front();que.pop();int curx = cur.first;int cury = cur.second;for(int i=0; i<4; i++){int nextx = curx + direction[i][0];int nexty = cury + direction[i][1];if(nextx>=matrix.size() || nexty>=matrix.size() ||nextx<0 || nexty<0) continue;if(matrix[nextx][nexty] && !visited[nextx][nexty]){visited[nextx][nexty] = true;que.push({nextx, nexty});}}}
}void bfs(vector<vector<int>>& matrix,vector<vector<bool>>& visited,int x, int y){visited[x][y] = true;matrix[x][y] = 0;queue<pair<int, int>> que;que.push({x,y});while(!que.empty()){pair<int, int> cur = que.front();que.pop();int curx = cur.first;int cury = cur.second;for(int i=0; i<4; i++){int nextx = curx + direction[i][0];int nexty = cury + direction[i][1];if(nextx>=matrix.size() || nexty>=matrix.size() ||nextx<0 || nexty<0) continue;if(matrix[nextx][nexty] && !visited[nextx][nexty]){visited[nextx][nexty] = true;matrix[nextx][nexty] = 0;que.push({nextx, nexty});}}}
}
int main(){int n,m;cin>>n>>m;vector<vector<int>> matrix(n, vector<int>(m, 0));vector<vector<bool>> visited(n, vector<bool>(m, false));for(int i=0; i<n; i++){for(int j=0; j<m; j++){cin>>matrix[i][j];}}/*// dfsfor(int i=0; i<n; i++){if(matrix[i][0] && !visited[i][0]) pre_dfs(matrix, visited, i, 0);if(matrix[i][m-1] && !visited[i][m-1]) pre_dfs(matrix, visited, i, m-1);}for(int j=0; j<m; j++){if(matrix[0][j] && !visited[0][j]) pre_dfs(matrix, visited, 0, j);if(matrix[n-1][j] && !visited[n-1][j]) pre_dfs(matrix, visited, n-1, j);}*/// bfsfor(int i=0; i<n; i++){if(matrix[i][0] && !visited[i][0]) pre_bfs(matrix, visited, i, 0);if(matrix[i][m-1] && !visited[i][m-1]) pre_bfs(matrix, visited, i, m-1);}for(int j=0; j<m; j++){if(matrix[0][j] && !visited[0][j]) pre_bfs(matrix, visited, 0, j);if(matrix[n-1][j] && !visited[n-1][j]) pre_bfs(matrix, visited, n-1, j);}for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(matrix[i][j] && !visited[i][j]){// visited[i][j] = true;// dfs(matrix,visited, i, j);bfs(matrix,visited, i, j);}}for(int j=0; j<m; j++) cout<<matrix[i][j]<<" ";cout<<endl;}return 0;
}

*103. 水流問題

題目地址

使用兩個標識訪問的數組分別從兩組邊界出發進行dfs遍歷，使用從低向高流(反向流)來分別記錄兩組邊界的結點。最后兩組邊界的交集就是本題答案。
思路

時間復雜度： $O(m?n)$
空間復雜度： $O(m?n)$

// c++
#include<bits/stdc++.h>
using namespace std;
int direction[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
void dfs(const vector<vector<int>> &matrix, vector<vector<bool>> &visited,int x, int y){visited[x][y] = true;for(int i=0; i<4; i++){int nextx = x + direction[i][0];int nexty = y + direction[i][1];if(nextx>=matrix.size() || nexty>=matrix[0].size() || nextx<0 || nexty<0) continue;if(matrix[x][y]>matrix[nextx][nexty]) continue;if(!visited[nextx][nexty]) dfs(matrix, visited, nextx, nexty);}
}int main(){int n,m;cin>>n>>m;vector<vector<int>> matrix(n, vector<int>(m, 0));vector<vector<bool>> first(n, vector<bool>(m, false));vector<vector<bool>> second(n, vector<bool>(m, false));for(int i=0; i<n; i++){for(int j=0; j<m; j++){cin>>matrix[i][j];}}for(int i=0; i<n; i++){dfs(matrix, first, i, 0);dfs(matrix, second, i, m-1);}for(int j=0; j<m; j++){dfs(matrix, first, 0, j);dfs(matrix, second, n-1, j);}for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(first[i][j] && second[i][j]) cout<<i<<" "<<j<<endl;}}return 0;   
}

*104. 建造最大島嶼

題目地址

題解思路

時間復雜度： $O(n)$
空間復雜度： $O(n)$

// c++