题解 | 挡住洪水

package main

/* 
    先把边界为'0'的地方都BFS标记一次（会被淹没的'0'）
    然后再次BFS_未被标记的'0'，计算安全的'0'的个数
 */

import (
    "fmt"
)

type Node struct{
    i,j int
}

func main() {
    var n,m int
    fmt.Scanf("%d %d",&n, &m)
    var k = make([][]byte, n)
    var v = make([][]bool, n)
    var s string
    for i:=0;i<n;i++{
        k[i] = make([]byte, m)
        v[i] = make([]bool, m)
        fmt.Scanf("%s", &s)
        k[i] = []byte(s) 
    }

    dist:= [][]int{{0,1}, {0,-1}, {1,0}, {-1,0}}
    
    var cur Node
    var queue []Node
    var result, ni, nj int
    var BFS func(i, j int)

    BFS = func(i, j int){ // 标记会被淹没的'0'
        queue = []Node{{i,j}}
        for len(queue) > 0{
            cur = queue[0]
            queue = queue[1:]

            for _, d := range dist{
                ni = cur.i + d[0]
                nj = cur.j + d[1]
                if ni<0 || ni>=n || nj<0 || nj>=m || v[ni][nj] || k[ni][nj] == '*'{
                    continue
                }
                v[ni][nj] = true
                queue = append(queue, Node{ni,nj})
            }
        }
    }

    var BFS_ func(i, j int) // 累计安全的'0'的个数
    BFS_ = func(i, j int){
        queue = []Node{{i,j}}
        for len(queue) > 0{
            cur = queue[0]
            queue = queue[1:]

            for _, d := range dist{
                ni = cur.i + d[0]
                nj = cur.j + d[1]
                if ni<0 || ni>=n || nj<0 || nj>=m || v[ni][nj] || k[ni][nj] == '*'{
                    continue
                }
                v[ni][nj] = true
                result++
                queue = append(queue, Node{ni,nj})
            }
        }
    }

    // 标记会被淹没的区域
    for i:=0;i<n;i++{
        if k[i][0] == '0' && !v[i][0] {
            v[i][0] = true
            BFS(i,0)
        }
        if k[i][m-1] == '0' && !v[i][m-1]{
            v[i][m-1] = true
            BFS(i,m-1)
        }
    }
    for i:=0;i<m;i++{
        if k[0][i] == '0' && !v[0][i] {
            v[0][i] = true
            BFS(0,i)
        }
        if k[n-1][i] == '0' && !v[n-1][i]{
            v[n-1][i] = true
            BFS(n-1,i)
        }
    }

    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            if k[i][j] == '0' && !v[i][j]{
                v[i][j] = true
                result++
                BFS_(i,j)
            }
        }
    }
    fmt.Print(result)
}