题解 | 剪纸游戏

/*
    for n // 从左往右
        for m // 从上往下
            BFS(i,j) 

    BFS(i,j)时，k[i][j]应该是长方形的左上角，记录最右的下标max_i、最下的下标max_j和'.'的数量num，判断(max_i+1-i)*(max_j+1-j) == num，但是有部分样例没通过。
    后面加上记录 min_i，min_j，然后判断(max_i+1 -min_i)*(max_j+1 -min_j) == num就都通过了。
*/
package main

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)
    }

    var result, num, max_i, max_j, ni, nj, min_i, min_j int
    var queue []Node
    var cur Node
    dist := [][]int{{1,0}, {-1,0}, {0,1}, {0,-1}}

    var BFS func(i, j int)
    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
                num++
                queue = append(queue, Node{ni,nj})
                if ni > max_i {
                    max_i = ni
                }
                if ni < min_i {
                    min_i = ni
                }
                if nj > max_j {
                    max_j = nj
                }
                if nj < min_j{
                    min_j = nj
                }
            }
        }
    }
    for i:=0;i<n;i++{
        for j:=0;j<m;j++{
            if k[i][j] == '.' && !v[i][j]{
                v[i][j] = true
                max_i = i
                max_j = j
                min_i = i
                min_j = j
                num = 1
                BFS(i,j)
                if (max_i+1 -min_i)*(max_j+1 -min_j) == num {
                    result++
                }
            }
        }
    }
    fmt.Print(result)
}