图遍历
dfs 深度优先搜索
bfs 广度优先搜索
200 岛屿数量(dfs)
var dirPath = [][]int{{0, -1}, {1, 0}, {0, 1}, {-1, 0}} // 上, 右, 下, 左
var visited [][]bool
func numIslands(grid [][]byte) int {
// dfs 深度优先遍历,对于每一个节点,按照上下左右四个固定顺序遍历,然后到下一个节点递归,实现一条路走到黑
// 重新初始化,避免多个测试样例导致出现全局变量污染情况
visited = make([][]bool, len(grid))
for idx, _ := range visited {
visited[idx] = make([]bool, len(grid[0]))
}
var res int
for i:=0; i<len(grid); i++ {
for j:=0; j<len(grid[0]); j++ {
if grid[i][j] != '0' && !visited[i][j] { // 是陆地并且没被遍历过
dfs(grid, i, j)
}else{
continue
}
if visited[i][j] { // 是陆地,并且被标记了,这里的标记会遍历整个四周陆地,并且为周边陆地打上标记,所以不会出现同一陆地多个地块都被计数
res += 1
}
}
}
return res
}
func dfs(grid [][]byte, x, y int) {
// 遇到之前节点或者水,返回
if grid[x][y] == '0' || visited[x][y] == true {
visited[x][y] = true // 优化,不是陆地也标记遍历过,防止出现多次对水进行重复遍历
return
}
visited[x][y] = true // 本节点是陆地并且标记为已经遍历过
// 按照四个方向遍历到下一个节点,然后递归,实现一条路走到黑之后回溯,由于不需要路径,所以回溯过程视为隐藏
for _, v := range dirPath {
next_x, next_y := x+v[0], y+v[1] // 要遍历的下一个节点
if next_x < 0 || next_x >= len(grid) || next_y < 0 || next_y >= len(grid[0]) { // 避免出现节点越界情况
continue
}
// 加入
dfs(grid, next_x, next_y)
// 回溯
}
return
}
岛屿数量(bsf)
var dirPath = [][]int{{0, -1}, {1, 0}, {0, 1}, {-1, 0}} // 上, 右, 下, 左
var visited [][]bool
var queue *list.List
func numIslands(grid [][]byte) int {
// 重新初始化,避免多个测试样例导致出现全局变量污染情况
queue = list.New()
visited = make([][]bool, len(grid))
for idx, _ := range visited {
visited[idx] = make([]bool, len(grid[0]))
}
var res int
for i:=0; i<len(grid); i++ {
for j:=0; j<len(grid[0]); j++ {
if grid[i][j] != '0' && !visited[i][j] { // 是陆地并且没被遍历过
queue.PushBack([2]int{i, j})
visited[i][j] = true
bfs(grid)
}else{
continue
}
if visited[i][j] { // 本质上多余这一步判断,方便理解放进去了
// 是陆地,并且被标记了,这里的标记会遍历整个四周陆地,并且为周边陆地打上标记,所以不会出现同一陆地多个地块都被计数
res += 1
}
}
}
return res
}
func bfs(grid [][]byte) {
for queue.Len() > 0 { // 一个岛屿的完成遍历过程就是整个队列完全为空
node := queue.Remove(queue.Front()).([2]int) // 去除队首,断言为长度为2数组
for _, v := range dirPath { // 遍历四个节点标记入队
next_x, next_y := node[0] + v[0], node[1] + v[1]
if next_x < 0 || next_x >= len(grid) || next_y < 0 || next_y >= len(grid[0]) { // 避免越界
continue
}
if visited[next_x][next_y] { // 节点被使用过,过
continue
}
// 先标记再入队,可以避免很多重复遍历,例如如果节点是0,不标记已经遍历过,那么bfs中也要遍历多次,主函数两层for循环也要遍历多次,容易超时
visited[next_x][next_y] = true
if grid[next_x][next_y] == '1'{
queue.PushBack([2]int{next_x, next_y})
}
}
}
}
岛屿最大面积(dfs)
var dirPath = [4][2]int{{0, -1}, {1, 0}, {0, 1}, {-1, 0}} // 上右下左
var visited [][]bool
var area int
func maxAreaOfIsland(grid [][]int) int {
visited = make([][]bool, len(grid))
for idx, _ := range visited {
visited[idx] = make([]bool, len(grid[0]))
}
var maxArea int
for i:=0; i<len(grid); i++ {
for j:=0; j<len(grid[0]); j++{
if !visited[i][j] && grid[i][j] == 1{
area = 1
dfs(grid, i, j)
maxArea = max(area, maxArea)
}
}
}
return maxArea
}
func dfs(grid [][]int, x, y int) {
if visited[x][y] || grid[x][y] == 0 { // 如果是水,标记返回,或者如果是标记过,也直接返回
visited[x][y] = true
return
}
visited[x][y] = true // 此时是陆地,标记
for _, dir := range dirPath {
next_x, next_y := dir[0] + x, dir[1] + y
if next_x < 0 || next_x >= len(grid) || next_y < 0 || next_y >= len(grid[0]) {
continue
}
if grid[next_x][next_y] == 1 && !visited[next_x][next_y]{
area++
dfs(grid, next_x, next_y)
}
}
}
岛屿最大面积(bfs)
var dirPath = [4][2]int{{0, -1}, {1, 0}, {0, 1}, {-1, 0}} // 上右下左
var visited [][]bool
var queue *list.List
func maxAreaOfIsland(grid [][]int) int {
visited = make([][]bool, len(grid))
for idx, _ := range visited {
visited[idx] = make([]bool, len(grid[0]))
}
queue = list.New()
var maxArea int
for i:=0; i<len(grid); i++ {
for j:=0; j<len(grid[0]); j++{
if !visited[i][j] && grid[i][j] == 1{
visited[i][j] = true
queue.PushBack([2]int{i, j})
area := bfs(grid)
maxArea = max(area, maxArea)
}
}
}
return maxArea
}
func bfs(grid [][]int) int {
var area int = 1
for queue.Len() >0 {
node := queue.Remove(queue.Front()).([2]int)
for _, dir := range dirPath{
next_x, next_y := node[0] + dir[0], node[1] + dir[1]
if next_x < 0 || next_x >= len(grid) || next_y < 0 || next_y >= len(grid[0]) { // 越界
continue
}
if grid[next_x][next_y] == 1 && !visited[next_x][next_y] {
area++
queue.PushBack([2]int{next_x, next_y})
}
visited[next_x][next_y] = true
}
}
return area
}
标签:int,岛屿,随想录,len,next,grid,var,visited,day52
From: https://www.cnblogs.com/zhougongjin55/p/18398280