题1:
指路:101. 孤岛的总面积 (kamacoder.com)
思路与代码:
本题要求找到不靠边的陆地面积,那么我们从地图的最外层开始遍历,找到靠近四个边的陆地,通过搜索将周边靠陆地且相邻的陆地1变成海洋0,重新遍历地图统计剩下的陆地1即可。代码如下:
#include<iostream>
#include<vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
int count; // 统计符合要求的陆地空格数量
void dfs(vector<vector<int>>& grid, int x, int y) {
grid[x][y] = 0;
count++;
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 ||
nexty >= grid[0].size()) continue;
if (grid[nextx][nexty] == 0) continue;
dfs (grid, nextx, nexty);
}
return ;
}
int main() {
int n, m;
cin >> n >> m; // 行列
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
// 从左右两次向中间遍历
for (int i = 0; i < n; i++) {
if (grid[i][0] == 1) dfs(grid, i, 0);
if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);
}
// 从上下两次向中间遍历
for (int j = 0; j < m; j++) {
if (grid[0][j] == 1) dfs(grid, 0, j);
if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);
}
count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) dfs(grid, i, j);
}
}
cout << count << endl;
}
题2:
指路:102. 沉没孤岛 (kamacoder.com)
思路与代码:
本题与上题的区别在于,要将孤岛1变成水域0,从地图周边开始,在空格相邻的陆地标记,遍历地图遇到陆地且无标记的变成水域1即可。其中,无需另外定义一个二维数组将陆地与原数组对比比较,可以直接将陆地实行特殊标记2。首先,dfs将地图周边的陆地1变成特殊标记2,然后将水域0中间的陆地1变成水域0,最后将特殊标记2改成陆地1即可。代码如下:
#include<iostream>
#include<vector>
using namespace std;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs (vector<vector<int>>& grid, int x, int y) {
grid[x][y] = 2;
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
// 越界退出
if (nextx < 0 || nextx >= grid.size() || nexty < 0
|| nexty >= grid[0].size()) continue;
// 不符合条件退出
if (grid[nextx][nexty] == 0 || grid[nextx][nexty] == 2)
continue;
dfs (grid, nextx, nexty);
}
return ;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid (n, vector<int> (m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
// 从左右向中间遍历
for (int i = 0; i < n; i++) {
if (grid[i][0] == 1) dfs (grid, i, 0);
if (grid[i][m - 1] == 1) dfs (grid, i, m - 1);
}
// 从上下向中间遍历
for (int j = 0; j < m; j++) {
if (grid[0][j] == 1) dfs (grid, 0, j);
if (grid[n - 1][j] == 1) dfs (grid, n - 1, j);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) grid[i][j] = 0;
if (grid[i][j] == 2) grid[i][j] = 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << grid[i][j] << " ";
}
cout << endl;
}
// return 0;
}
题3:
指路:103. 水流问题 (kamacoder.com)
思路与代码:
要求节点能到达第以一边界和第二边界。遍历即可,如果这个节点能同时到达第一和第二边界,那么该节点符合结果集条件,写出来发现超时(见下面代码中的灰色注释部分)。那么对其进行优化:从第一组边界和第二组边界开始遍历,标记遍历过的节点,如果同时标记则表示节点可到达。代码如下:
#include<iostream>
#include<vector>
using namespace std;
//到达第一边界或达到第二边界
//
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
// 辅助数组visited
void dfs (vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
if (visited[x][y]) return ;
visited[x][y] = true; // 初始化
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
// 越界
if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
// 高度差水不可流过去
//if (grid[x][y] < grid[nextx][nexty]) continue;
if (grid[x][y] > grid[nextx][nexty]) continue;
dfs (grid, visited, nextx, nexty);
}
return ;
}
/* bool isResult (vector<vector<int>>& grid, int x, int y) {
vector<vector<bool>> visited(n, vector<bool> (m, false)) ;
dfs (grid, visited, x, y);
bool isFirst = false;
bool isSecond = false;
// 第一边界中的上边界
for (int j = 0; j < m; j++) {
if (visited[0][j]) {
isFirst = true;
break;
}
}
// 第一边界中的左边界
for (int i = 0; i < n; i++) {
if (visited[i][0]) {
isFirst = true;
break;
}
}
// 第二边界中的右边界
for (int j = 0;j < m; j++) {
if (visited[n - 1][j]) {
isSecond = true;
break;
}
}
// 第二边界中的下边界
for (int i = 0; i < n; i++) {
if (visited[i][m - 1]) {
isSecond = true;
break;
}
}
if (isFirst && isSecond) return true;
return false;
}*/
int main() {
cin >> n >> m;
vector<vector<int>> grid (n, vector<int> (m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
/* for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (isResult (grid, i, j)) {
cout << i << " " << j << endl;
}
}
}*/
// 第一组的边界上的节点
vector<vector<bool>> firstBorder (n, vector<bool> (m, false));
// 第二组的边界上的节点
vector<vector<bool>> secondBorder (n, vector<bool> (m, false));
// 最顶和最低的节点出发
for (int i = 0; i < n; i++) {
dfs (grid, firstBorder, i, 0); // 最左列
dfs (grid, secondBorder, i, m - 1); // 最右列
}
// 最左和最右的节点出发
for (int j = 0; j < m; j++) {
dfs (grid, firstBorder, 0, j);
dfs (grid, secondBorder, n - 1, j);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (firstBorder[i][j] && secondBorder[i][j])
cout << i << " " << j << endl;
}
}
}