#include<iostream>#include<cstring>#include<vector>usingnamespace std;
constint N = 55;
int arr[N][N];
bool used[N][N];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
voiddfs(int x, int y, int n, int m){
for (int i = 0; i < 4; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !used[nx][ny] && arr[nx][ny] == 1) {
used[nx][ny] = true;
dfs(nx, ny, n, m);
}
}
}
intmain(){
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> arr[i][j];
memset(used, false, sizeof used);
int cnt = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (arr[i][j] == 1 && !used[i][j]) {
used[i][j] = true;
cnt++;
dfs(i, j, n, m);
}
}
}
cout << cnt << endl;
return0;
}
2. 岛屿的最大面积
在统计数量的基础上,计算单个岛屿包含的格子数最大值。
思路:DFS 过程中累加当前岛屿的面积,并维护全局最大值。
#include<iostream>#include<cstring>#include<algorithm>usingnamespace std;
constint N = 55;
int arr[N][N];
bool used[N][N];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int cur_area, max_area;
voiddfs(int x, int y, int n, int m){
for (int i = 0; i < 4; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !used[nx][ny] && arr[nx][ny] == 1) {
used[nx][ny] = true;
cur_area++;
dfs(nx, ny, n, m);
}
}
}
intmain(){
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> arr[i][j];
memset(used, false, sizeof used);
max_area = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (arr[i][j] == 1 && !used[i][j]) {
cur_area = 1;
used[i][j] = true;
dfs(i, j, n, m);
max_area = max(max_area, cur_area);
}
}
}
cout << max_area << endl;
return0;
}
3. 孤岛总面积
计算完全被水域包围(不接触矩阵边缘)的岛屿总面积。
思路:先对接触边缘的岛屿进行 DFS 标记(视为非孤岛),剩余未访问的陆地即为孤岛。
#include<iostream>#include<cstring>usingnamespace std;
constint N = 55;
int arr[N][N];
bool used[N][N];
int n, m;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
voiddfs(int x, int y){
for (int i = 0; i < 4; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && !used[nx][ny] && arr[nx][ny] == 1) {
used[nx][ny] = true;
dfs(nx, ny);
}
}
}
intmain(){
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> arr[i][j];
memset(used, false, sizeof used);
// 标记边缘岛屿for (int i = 0; i < n; ++i) {
if (arr[i][0] == 1 && !used[i][0]) { used[i][0] = true; dfs(i, 0); }
if (arr[i][m - 1] == 1 && !used[i][m - 1]) { used[i][m - 1] = true; dfs(i, m - 1); }
}
for (int j = 0; j < m; ++j) {
if (arr[0][j] == 1 && !used[0][j]) { used[0][j] = true; dfs(0, j); }
if (arr[n - 1][j] == 1 && !used[n - 1][j]) { used[n - 1][j] = true; dfs(n - 1, j); }
}
int cnt = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (arr[i][j] == 1 && !used[i][j]) cnt++;
cout << cnt << endl;
return0;
}
4. 沉没孤岛
将孤岛中的陆地变为水域。
思路:同孤岛总面积,标记边缘岛屿后,将未标记的陆地置为 0。
5. 水流问题
确定哪些单元格的水能同时流向第一组边界和第二组边界。
思路:反向思考。分别从两组边界出发进行 DFS/BFS,标记可达区域。取两个标记集合的交集。
#include<iostream>#include<cstring>usingnamespace std;
constint N = 105;
int n, m;
int arr[N][N];
int arr_one[N][N], arr_two[N][N];
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
voiddfs(int flag, int x, int y, int target_arr[][N]){
for (int i = 0; i < 4; ++i) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && target_arr[nx][ny] == 0) {
if (arr[x][y] <= arr[nx][ny]) {
target_arr[nx][ny] = flag;
dfs(flag, nx, ny, target_arr);
}
}
}
}
intmain(){
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> arr[i][j];
memset(arr_one, 0, sizeof arr_one);
memset(arr_two, 0, sizeof arr_two);
// 从第一组边界(左、上)开始for (int i = 0; i < n; ++i) {
arr_one[i][0] = 1;
dfs(1, i, 0, arr_one);
}
for (int j = 0; j < m; ++j) {
arr_one[0][j] = 1;
dfs(1, 0, j, arr_one);
}
// 从第二组边界(右、下)开始for (int i = 0; i < n; ++i) {
arr_two[i][m - 1] = 2;
dfs(2, i, m - 1, arr_two);
}
for (int j = 0; j < m; ++j) {
arr_two[n - 1][j] = 2;
dfs(2, n - 1, j, arr_two);
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (arr_one[i][j] == 1 && arr_two[i][j] == 2)
cout << i << " " << j << endl;
return0;
}