在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 "X", 白棋记作字母 "O"，空余位置记作 "."。
当落下的棋子与其他相同颜色的棋子在行、列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。
「力扣挑战赛」黑白翻转棋项目中，将提供给选手一个未形成可翻转棋子的棋盘残局，其状态记作 chessboard。
若下一步可放置一枚黑棋，请问选手最多能翻转多少枚白棋。
注意：若翻转白棋成黑棋后，棋盘上仍存在可以翻转的白棋，将可以 继续 翻转白棋
输入数据保证初始棋盘状态无可以翻转的棋子且存在空余位置
示例 1：输入：chessboard = ["....X.","....X.","XOOO..","......","......"] 输出：3
解释：可以选择下在 [2,4] 处，能够翻转白方三枚棋子。
示例 2：输入：chessboard = [".X.",".O.","XO."] 输出：2
解释：可以选择下在 [2,2] 处，能够翻转白方两枚棋子。
示例 3：输入：chessboard = [".......",".......",".......","X......",".O.....","..O....","....OOX"] 输出：4
解释： 可以选择下在 [6,3] 处，能够翻转白方四枚棋子。
提示：1 <= chessboard.length, chessboard[i].length <= 8
chessboard[i] 仅包含 "."、"O" 和 "X"
解题思路分析1、枚举 深度优先搜索；时间复杂度O(n^4)，空间复杂度O(n^2)
var res int
var n, m int
var dx = []int{-1, 1, 0, 0, 1, 1, -1, -1}
var dy = []int{0, 0, -1, 1, 1, -1, -1, 1}
func flipChess(chessboard []string) int {
res = 0
n, m = len(chessboard), len(chessboard[0])
temp := make([][]byte, n)
for i := 0; i < n; i {
for j := 0; j < m; j {
if chessboard[i][j] == '.' {
for a := 0; a < n; a {
temp[a] = []byte(chessboard[a])
}
temp[i][j] = 'X'
dfs(temp, i, j) // 尝试在i,j位置下黑棋
count := 0
for a := 0; a < n; a { // 统计结果
for b := 0; b < m; b {
if temp[a][b] == 'X' && chessboard[a][b] == 'O' {
count
}
}
}
res = max(res, count) // 更新结果
}
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func dfs(arr [][]byte, i, j int) {
arr[i][j] = 'X'
for k := 0; k < 8; k {
if ok, path := judge(arr, i, j, 'X', dx[k], dy[k]); ok == true {
for c := 0; c < len(path); c {
a, b := path[c][0], path[c][1]
arr[a][b] = 'X'
dfs(arr, a, b)
}
}
}
}
// leetcode1958.检查操作是否合法
func judge(board [][]byte, rMove int, cMove int, color byte, dirX, dirY int) (res bool, path [][]int) {
x, y := rMove dirX, cMove dirY
count := 1
for 0 <= x && x < n && 0 <= y && y < m {
if board[x][y] == '.' {
return false, nil
}
path = append(path, []int{x, y})
if count == 1 {
if board[x][y] == color {
return false, nil
}
} else {
if board[x][y] == color {
return true, path
}
}
count
x = x dirX
y = y dirY
}
return false, nil
}总结
Medium题目，暴力法枚举即可，下子后检测翻转，可以参考leetcode1958.检查操作是否合法
