题目

样例输入：

. 1 2 1

. . . .

. . . .

. . . .

样例输出：

O 1 2 1

O X O X

. . . .

. . . .

go题解

（我省略了输入输出，免得测试的时候重新输入）
思路:

• 由于是4 x 4的地图，因此范围很小，首先想到的就是dfs遍历所有可能情形；
• 每种可能情形（possibleBackup）的格子都是确定的，即要么是'X'要么是'O'要么是数字
• dfs得到possibleBackup后check一下是否是合理的，即所有数字格子周边地雷数是正确的
• 如果是合理的情形，则此时得到的地图backup就是合法的，加入backups
• 所有情形dfs结束后，最后遍历backups，对16个格子进行检查：
  • 数字跳过
  • 所有backup的该格子都是'X'，说明此格子是确定的，此处必有地雷
  • 所有backup的该格子都是'O'，说明此格子是确定的，此处必无地雷
  • backup既有'X'又有'O，此格子无法确定

package main

import "fmt"

var arrs [][]rune
var backups [][][]rune //存所有可能的合法的结果

func main() {
    arrs = [][]rune{
        {'.', '1', '2', '1'},
        {'.', '.', '.', '.'},
        {'.', '.', '.', '.'},
        {'.', '.', '.', '.'},
    }
    backups = [][][]rune{}
    dfs(0)

    // 拿到所有可能backup后，对16个位置进行检测，如果某个位置所有backup都为'X'或'O'，则该位置能确定，否则为'.'

    // 先copy一份原始地图
    res := make([][]rune, 0)
    for i := 0; i < 4; i++ {
        arr := make([]rune, 4)
        copy(arr, arrs[i])
        res = append(res, arr)
    }
    // 再遍历每个位置
    for i := 0; i < 4; i++ {
        for j := 0; j < 4; j++ {
            c := arrs[i][j]
            if c != '.' {
                //数字跳过
                continue
            }
            c = backups[0][i][j]
            flag := true // 该位置是否是确定的
            for idx, backup := range backups {
                if idx == 0 {
                    continue
                }
                if backup[i][j] != c {
                    flag = false
                    break
                }
            }
            if flag { // 该位置是能确定的
                res[i][j] = c
            }
        }
    }
    for i := 0; i < 4; i++ {
        fmt.Printf("%c\n", res[i])
    }
}

func dfs(u int) {
    if u == 16 {
        if !check(arrs) {
            return
        }
        backup := make([][]rune, 0)
        for i := 0; i < 4; i++ {
            arr := make([]rune, 4)
            copy(arr, arrs[i])
            backup = append(backup, arr)
        }
        backups = append(backups, backup)
        return
    }
    x, y := u/4, u%4 // 当前dfs的横纵坐标
    if arrs[x][y] != '.' {
        dfs(u + 1)
    } else {
        c := arrs[x][y]
        arrs[x][y] = 'X'
        dfs(u + 1)
        arrs[x][y] = 'O'
        dfs(u + 1)
        arrs[x][y] = c
    }
}

func check(possibleBackup [][]rune) bool {
    for i := 0; i < 4; i++ {
        for j := 0; j < 4; j++ {
            if possibleBackup[i][j] == 'O' || possibleBackup[i][j] == 'X' {
                continue
            }
            dx, dy := []int{-1, -1, -1, 0, 0, 1, 1, 1}, []int{-1, 0, 1, -1, 1, -1, 0, 1}
            count := 0
            for k := 0; k < 8; k++ {
                a := i + dx[k]
                b := j + dy[k]
                if a >= 0 && a < 4 && b >= 0 && b < 4 && possibleBackup[a][b] == 'X' {
                    count++
                }
            }
            if count != int(possibleBackup[i][j]-'0') {
                return false
            }
        }
    }
    return true
}