代码随想录算法训练营第五十二天|图论专题： 101. 孤岛的总面积、102. 沉没孤岛、103. 水流问题、104. 建造最大岛屿

101. 孤岛的总面积

本题要求找到不靠边的陆地面积，那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋，然后再去重新遍历地图 统计此时还剩下的陆地就可以了。

1、从左边和后边向中间遍历

2、从上边和下边向中间遍历

package mainimport ("fmt"
)func dfs(grid [][]int, x, y, n, m int) {if x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != 1 {return}grid[x][y] = 2 // 标记为接触边缘的陆地dfs(grid, x+1, y, n, m)dfs(grid, x-1, y, n, m)dfs(grid, x, y+1, n, m)dfs(grid, x, y-1, n, m)
}func main() {var n, m intfmt.Scan(&n, &m)grid := make([][]int, n)for i := 0; i < n; i++ {grid[i] = make([]int, m)for j := 0; j < m; j++ {fmt.Scan(&grid[i][j])}}// 从左、右边界向中间遍历for i := 0; i < n; i++ {if grid[i][0] == 1 {dfs(grid, i, 0, n, m)}if grid[i][m - 1] == 1 {dfs(grid, i, m - 1, n, m)}}// 从上、下边界向中间遍历for j := 0; j < m; j++ {if grid[0][j] == 1 {dfs(grid, 0, j, n, m)}if grid[n - 1][j] == 1 {dfs(grid, n - 1, j, n, m)}} count := 0for i := 0; i < n; i++ {for j := 0; j < m; j++ {if grid[i][j] == 1 {count++}}}fmt.Println(count)
}

102. 沉没孤岛

思路依然是从地图周边出发，将周边空格相邻的陆地都做上标记，然后在遍历一遍地图，遇到 陆地 且没做过标记的，那么都是地图中间的 陆地 ，全部改成水域就行。

有的录友可能想，我再定义一个 visited 二维数组，单独标记周边的陆地，然后遍历地图的时候同时对 地图数组 和 数组visited 进行判断，决定 陆地是否变成水域。

这样做其实就有点麻烦了，不用额外定义空间了，标记周边的陆地，可以直接改陆地为其他特殊值作为标记。

步骤一：深搜或者广搜将地图周边的 1 （陆地）全部改成 2 （特殊标记）

步骤二：将水域中间 1 （陆地）全部改成 水域（0）

步骤三：将之前标记的 2 改为 1 （陆地）

package mainimport ("fmt"
)func dfs(grid [][]int, x, y, n, m int) {if x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != 1 {return}grid[x][y] = 2 // 标记为接触边缘的陆地dfs(grid, x+1, y, n, m)dfs(grid, x-1, y, n, m)dfs(grid, x, y+1, n, m)dfs(grid, x, y-1, n, m)
}func main() {var n, m intfmt.Scan(&n, &m)grid := make([][]int, n)for i := 0; i < n; i++ {grid[i] = make([]int, m)for j := 0; j < m; j++ {fmt.Scan(&grid[i][j])}}// 第一步：从左、右边界上所有是 1 的位置开始 DFS 标记for i := 0; i < n; i++ {if grid[i][0] == 1 {dfs(grid, i, 0, n, m)}if grid[i][m-1] == 1 {dfs(grid, i, m-1, n, m)}}// 从上、下边界上所有是 1 的位置开始 DFS 标记for j := 0; j < m; j++ {if grid[0][j] == 1 {dfs(grid, 0, j, n, m)}if grid[n-1][j] == 1 {dfs(grid, n-1, j, n, m)}}// 第二步：沉没孤岛（grid[i][j] == 1），还原边界陆地（grid[i][j] == 2）for i := 0; i < n; i++ {for j := 0; j < m; j++ {if grid[i][j] == 1 {grid[i][j] = 0 // 沉没孤岛} else if grid[i][j] == 2 {grid[i][j] = 1 // 还原接触边界的陆地}}}// 输出矩阵，注意每个元素后都要有空格for i := 0; i < n; i++ {for j := 0; j < m; j++ {fmt.Printf("%d ", grid[i][j])}fmt.Println()}
}

103. 水流问题

首先读懂题目，水从高处流向低处，看看有没有一个坐标位置能同时到达第一和第二边界

从第一组边界上的节点 逆流而上，将遍历过的节点都标记上。

同样从第二组边界的边上节点 逆流而上，将遍历过的节点也标记上。

然后两方都标记过的节点就是既可以流向第一组边界也可以流向第二组边界的节点。

从第一组边界边上节点出发，如图： （图中并没有把所有遍历的方向都画出来，只画关键部分）

package mainimport ("fmt"
)// var dirs = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}// func dfs(matrix [][]int, visited [][]bool, x, y, n, m int) {
// 	visited[x][y] = true
// 	for _, dir := range dirs {
// 		nx := x + dir[0]
// 		ny := y + dir[1]
// 		if nx >= 0 && nx < n && ny >= 0 && ny < m &&
// 			!visited[nx][ny] &&
// 			matrix[nx][ny] >= matrix[x][y] {
// 			dfs(matrix, visited, nx, ny, n, m)
// 		}
// 	}
// }func dfs(matrix [][]int, visited [][]bool, x, y, n, m int) {visited[x][y] = truedirections := [][]int{{0,1},{1,0},{0,-1},{-1,0}}for _, d := range directions {nx, ny := x + d[0], y + d[1]if nx >= 0 && nx < n && ny >= 0 && ny < m {// 只有当相邻格子的高度 >= 当前格子的高度，水才能从边界流进去if !visited[nx][ny] && matrix[nx][ny] >= matrix[x][y] {dfs(matrix, visited, nx, ny, n, m)}}}
}func main() {var n, m intfmt.Scan(&n, &m)matrix := make([][]int, n)for i := 0; i < n; i++ {matrix[i] = make([]int, m)for j := 0; j < m; j++ {fmt.Scan(&matrix[i][j])}}// 初始化访问标记数组canReachFirst := make([][]bool, n)canReachSecond := make([][]bool, n)for i := 0; i < n; i++ {canReachFirst[i] = make([]bool, m)canReachSecond[i] = make([]bool, m)}// 从第一组边界出发（左边 + 上边）for i := 0; i < n; i++ {dfs(matrix, canReachFirst, i, 0, n, m) // 左边}for j := 0; j < m; j++ {dfs(matrix, canReachFirst, 0, j, n, m) // 上边}// 从第二组边界出发（右边 + 下边）for i := 0; i < n; i++ {dfs(matrix, canReachSecond, i, m-1, n, m) // 右边}for j := 0; j < m; j++ {dfs(matrix, canReachSecond, n-1, j, n, m) // 下边}// 输出能同时到达两个边界的坐标for i := 0; i < n; i++ {for j := 0; j < m; j++ {if canReachFirst[i][j] && canReachSecond[i][j] {fmt.Println(i, j)}}}
}

104. 建造最大岛屿

做好标记

其实每次深搜遍历计算最大岛屿面积，我们都做了很多重复的工作。

只要用一次深搜把每个岛屿的面积记录下来就好。

第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积

第二步：再遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积。

拿如下地图的岛屿情况来举例： （1为陆地）

第一步，则遍历地图，并将岛屿的编号和面积都统计好，过程如图所示：

// 先遍历整张地图，找出所有的岛屿，并标记每个岛屿的编号及其面积。// 用一个 islandId 数组记录每个格子属于哪个岛屿。// 然后遍历所有水格（值为0的格子），尝试将它变为1，然后查看它四周是否有不同编号的岛屿，合并这些岛屿面积 +1。// 取最大值返回。package mainimport ("fmt")var dirs = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}var grid [][]intvar islandId [][]intfunc dfs (x, y, id, n, m int) int {if x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != 1 {return 0}grid[x][y] = 2islandId[x][y] = idarea := 1for _, dir := range dirs {area += dfs(x + dir[0], y + dir[1], id, n, m)}return area}func main() {var n, m intfmt.Scan(&n, &m)// 初始化矩阵和标记数组grid = make([][]int, n)islandId = make([][]int, n)for i := 0; i < n; i++ {grid[i] = make([]int, m)islandId[i] = make([]int, m)for j := 0; j < m; j++ {fmt.Scan(&grid[i][j])}}// 岛屿编号和面积映射id := 2areaMap := make(map[int]int)// 找出所有岛屿及面积for i := 0; i < n; i++ {for j := 0; j < m; j++ {if grid[i][j] == 1 {area := dfs(i, j, id, n, m)areaMap[id] = areaid++}}}maxArea := 0for i := 0; i < n; i++ {for j := 0; j < m; j++ {if islandId[i][j] != 0 {if areaMap[islandId[i][j]] > maxArea {maxArea = areaMap[islandId[i][j]]}continue}// 水格，尝试变为陆地seen := map[int]bool{}area := 1for _, d := range dirs {x, y := i+d[0], j+d[1]if x >= 0 && x < n && y >= 0 && y < m {id := islandId[x][y]if id != 0 && !seen[id] {area += areaMap[id]seen[id] = true}}}if area > maxArea {maxArea = area}}}fmt.Println(maxArea)}