代码随想录算法训练营第四十四天 | 99.岛屿数量 深搜 99.岛屿数量 广搜 100. 岛屿的最大面积

版本一的写法是 ：下一个节点是否能合法已经判断完了，传进dfs函数的就是合法节点。

版本二的写法是：不管节点是否合法，上来就dfs，然后在终止条件的地方进行判断，不合法再return。

我在之前回溯算法做过笔记，我更偏好版本一。

xy老让我联想到坐标，我就不用xy了。也可以叫row、col。

package main import ( "bufio" "fmt" "os" ) var dir = [4][2]int{{0, 1}, {1, 0}, {-1, 0}, {0, -1}} func main() { in := bufio.NewReader(os.Stdin) var n, m int fmt.Fscan(in, &n, &m) grid := make([][]int, n) visited := make([][]bool, n) for i := range grid { grid[i] = make([]int, m) } for i := range visited { visited[i] = make([]bool, m) } for i := range grid { for j := range grid[i] { fmt.Fscan(in, &grid[i][j]) } } res := 0 for i := range grid { for j := range grid[i] { if grid[i][j] == 1 && !visited[i][j] { res++ visited[i][j] = true dfs(grid, visited, i, j) } } } fmt.Println(res) } func dfs(grid [][]int, visited [][]bool, i, j int) { for k := 0; k < 4; k++ { nextI := i + dir[k][0] nextJ := j + dir[k][1] if nextI < 0 || nextI >= len(grid) || nextJ < 0 || nextJ >= len(grid[0]) { continue } if grid[nextI][nextJ] == 1 && !visited[nextI][nextJ] { visited[nextI][nextJ] = true dfs(grid, visited, nextI, nextJ) } } }

如果节点出队列再标记为已访问过，会导致相同的节点重复入队列，进而导致队列中会有大量的重复节点。

package main import ( "bufio" "fmt" "os" ) var dir = [4][2]int{{0, 1}, {1, 0}, {-1, 0}, {0, -1}} func main() { in := bufio.NewReader(os.Stdin) var n, m int fmt.Fscan(in, &n, &m) grid := make([][]int, n) visited := make([][]bool, n) for i := range grid { grid[i] = make([]int, m) } for i := range visited { visited[i] = make([]bool, m) } for i := range grid { for j := range grid[i] { fmt.Fscan(in, &grid[i][j]) } } res := 0 for i := range grid { for j := range grid[i] { if grid[i][j] == 1 && !visited[i][j] { res++ visited[i][j] = true bfs(grid, visited, i, j) } } } fmt.Println(res) } type Pair struct { i, j int } func bfs(grid [][]int, visited [][]bool, row, col int) { q := make([]Pair, 0) q = append(q, Pair{row, col}) visited[row][col] = true for len(q) != 0 { cur := q[0] q = q[1:] for k := 0; k < 4; k++ { nextI := cur.i + dir[k][0] nextJ := cur.j + dir[k][1] if nextI < 0 || nextI >= len(grid) || nextJ < 0 || nextJ >= len(grid[0]) { continue } if grid[nextI][nextJ] == 1 && !visited[nextI][nextJ] { q = append(q, Pair{nextI, nextJ}) visited[nextI][nextJ] = true } } } }

easy

package main import ( "bufio" "fmt" "os" ) var dir = [4][2]int{{0, 1}, {1, 0}, {-1, 0}, {0, -1}} var count int func main() { in := bufio.NewReader(os.Stdin) var n, m int fmt.Fscan(in, &n, &m) grid := make([][]int, n) visited := make([][]bool, n) for i := range grid { grid[i] = make([]int, m) } for i := range visited { visited[i] = make([]bool, m) } for i := range grid { for j := range grid[i] { fmt.Fscan(in, &grid[i][j]) } } res := 0 for i := range grid { for j := range grid[i] { if grid[i][j] == 1 && !visited[i][j] { visited[i][j] = true count = 1 dfs(grid, visited, i, j) if count > res { res = count } } } } fmt.Println(res) } func dfs(grid [][]int, visited [][]bool, i, j int) { for k := 0; k < 4; k++ { nextI := i + dir[k][0] nextJ := j + dir[k][1] if nextI < 0 || nextI >= len(grid) || nextJ < 0 || nextJ >= len(grid[0]) { continue } if grid[nextI][nextJ] == 1 && !visited[nextI][nextJ] { visited[nextI][nextJ] = true count++ dfs(grid, visited, nextI, nextJ) } } }