C++算法练习：孤岛面积计算与水域扩展问题解析
101. 孤岛面积统计
本题要求计算地图中所有与边界不相连的陆地总面积。初始思路误将孤岛定义为完全被海水包围的区域，实际应理解为未与地图边界接触的陆地区域。
在DFS实现中发现关键问题：当遍历四邻域时，若某次递归返回false需立即标记该区域非孤岛。改进后的逻辑如下：
bool dfs(int x, int y, vector& grid, vector& visited, int& area) {
bool isIsolated = true;
int m = grid.size(), n = grid[0].size();
area++;
if(x == 0 || x == m-1 || y == 0 || y == n-1) {
isIsolated = false;
}
int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
for(auto& dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if(grid[nx][ny] && !visited[nx][ny]) {
visited[nx][ny] = true;
if(!dfs(nx, ny, grid, visited, area)) {
isIsolated = false;
}
}
}
return isIsolated;
}
优化后的主函数实现：
int main() {
int rows, cols;
cin >> rows >> cols;
vector grid(cols, vector<int>(rows));
for(int i=0; i> grid[j][i];
}
}
vector visited(cols, vector<bool>(rows));
int totalArea = 0;
for(int i=0; i 102. 沉没孤岛问题
采用BFS策略实现水域扩展，核心思想是将非孤岛区域置零后重新统计。改进后的实现如下：
void bfs(queue>& q, vector& grid, vector& visited) {
int m = grid.size(), n = grid[0].size();
while(!q.empty()) {
auto [x, y] = q.front(); q.pop();
grid[x][y] = 0;
int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
for(auto& dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if(grid[nx][ny] && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
主函数实现细节：
int main() {
int rows, cols;
cin >> rows >> cols;
vector grid(rows, vector<int>(cols));
for(int i=0; i> grid[i][j];
}
}
vector visited(rows, vector<bool>(cols));
queue> q;
// 初始化边界队列
for(int i=0; i 103. 水流路径问题
通过DFS实现水流路径检测，关键点在于维护两个布尔矩阵记录可达性。改进后的实现：
void dfs(vector& target, int x, int y, const vector& grid) {
int m = grid.size(), n = grid[0].size();
int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
for(auto& dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if(grid[nx][ny] >= grid[x][y] && !target[nx][ny]) {
target[nx][ny] = true;
dfs(target, nx, ny, grid);
}
}
}
主函数实现细节：
int main() {
int rows, cols;
cin >> rows >> cols;
vector grid(rows, vector<int>(cols));
for(int i=0; i> grid[i][j];
}
}
vector topleft(rows, vector<bool>(cols));
vector botright(rows, vector<bool>(cols));
// 初始化起点
for(int i=0; i 104. 最大岛屿建造
通过DFS标记不同岛屿，并使用哈希集合记录已访问岛屿。关键实现细节：
void dfs(int mark, int x, int y, vector& grid, vector& visited, int& area) {
grid[x][y] = mark;
area++;
int m = grid.size(), n = grid[0].size();
int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
for(auto& dir : directions) {
int nx = x + dir[0], ny = y + dir[1];
if(nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if(grid[nx][ny] && !visited[nx][ny]) {
visited[nx][ny] = true;
dfs(mark, nx, ny, grid, visited, area);
}
}
}
主函数完整实现：
int main() {
int rows, cols;
cin >> rows >> cols;
vector grid(rows, vector<int>(cols));
bool allLand = true;
for(int i=0; i> grid[i][j];
if(grid[i][j] == 0) allLand = false;
}
}
if(allLand) {
cout << rows * cols;
return 0;
}
vector visited(rows, vector<bool>(cols));
vector<int> areas;
int mark = 2;
// 标记所有岛屿
for(int i=0; i= 0 && nx < rows && ny >= 0 && ny < cols &&
grid[nx][ny] && used.find(grid[nx][ny]) == used.end()) {
current += areas[grid[nx][ny]-2];
used.insert(grid[nx][ny]);
}
}
maxArea = max(maxArea, current);
}
}
}
cout << maxArea + 1;
}
