每日一题 --- 1020. 飞地的数量[力扣][Go]

// dirs
// 定义方向
// 右，下，左，上
var dirs = []struct{x,y int}{{-1,0},{1,0},{0,-1},{0,1}}
func numEnclaves(grid [][]int) int {
    m,n := len(grid), len(grid[0])
    // 确定被访问过的陆地
    vis := make([][]bool,m)
    for i := 0; i < m; i++ {
        vis[i] = make([]bool,n)
    }
    // 深度优先函数
    var dfs func(int,int)
    dfs = func(r,c int) {
        if r < 0 || r >= m || c < 0 || c >= n || grid[r][c]==0 || vis[r][c] {
            return
        }
        vis[r][c] = true
        for _, dir := range dirs {
            dfs(r+dir.x,c+dir.y)
        }
    }
    // 将边界进行访问
    for i := range grid {
        dfs(i,0)
        dfs(i,n-1)
    }
    for j := 1; j < n - 1; j++ {
        dfs(0,j)
        dfs(m-1,j)
    }
    // 记录
    ans := 0
    for i := 1; i < m - 1; i++ {
        for j := 1; j < n - 1; j++ {
            if grid[i][j] == 1 && !vis[i][j] {
                ans++
            }
        }
    }
    return ans
}

type pair struct{ x, y int }
var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func numEnclaves(grid [][]int) int {
    m,n := len(grid), len(grid[0])
    // 确定被访问过的陆地
    vis := make([][]bool,m)
    for i := 0; i < m; i++ {
        vis[i] = make([]bool,n)
    }
    var q []pair
    for i,g:= range grid {
        if g[0] == 1 {
            vis[i][0] = true
            q = append(q,pair{i,0})
        }
        if g[n-1] == 1 {
            vis[i][n-1] = true
            q = append(q,pair{i,n-1})
        }
    }
    for j := 1; j < n - 1; j++ {
        if grid[0][j] == 1 {
            vis[0][j] = true
            q = append(q, pair{0,j})
        }
        if grid[m-1][j] == 1 {
            vis[m-1][j] = true
            q = append(q, pair{m-1,j})
        }
    }
    // 广度优先搜索
    for len(q) > 0 {
        p := q[0]
        q = q[1:]
        for _, dir := range dirs {
            if x,y := p.x + dir.x,p.y + dir.y; 0 <= x && x < m && 0 <= y && y < n && grid[x][y] == 1 && !vis[x][y] {
                vis[x][y] = true
                q = append(q, pair{x,y})
            }
        }
    }
    // 记录
    ans := 0
    for i := 1; i < m - 1; i++ {
        for j := 1; j < n - 1; j++ {
            if grid[i][j] == 1 && !vis[i][j] {
                ans++
            }
        }
    }
    return ans
}