前情提要
解题的思路参照了LeetCode用户【爪哇缪斯】的《【爪哇缪斯】图解LeetCode》对于大佬解法的图解，图片和说明很详细了，这里就不再重复造轮子了。
代码
class Solution:
def movesToChessboard(self, board: List[List[int]]) -> int:
"""
做之前先回顾本题思路：
一、判断一个棋盘是否合法：
1. 首先对于一个合法棋盘来说，整个棋盘的行和列只有两种状态，
即与第一行/列相同或全部取反，这是接下来所有优化的基础；
2. 因为一(1)，易得出对于棋盘内所有的子棋盘，四个角上的数字只可能出现
“全是0”，“全是1”和“两个0和两个1”三种情况，可依此筛选掉一些非法棋盘；
这一步可作为第一筛选器，此处可以用异或代替三个判断语句以节省代码量；
这一步可以在只遍历[[0,0],[i,i]]的矩阵的情况下完成一(1)的判断；
3. 对于一个合法棋盘，每一行/列的0和1的数量应该相同（偶数棋盘）
或者只相差1（奇数棋盘）；以这一步作为第二筛选器，可以基本确定棋盘合法性。
二、计算所需步数：
1. 因为一(1)，所以第一行/列的0/1序列即可代表所对应行/列的所属排序，
故在计算步数时可以只根据第一行/列的排序情况确定全棋盘的情况，
将二维判断转换为两个一维判断，以减少代码逻辑编写难度；
此处的计算可以与一(3)合并进行；
2. 在计算步数的时候，偶数行列情况下需要把0和1作为左上角的情况都判断一次，
奇数行列由于只有一种可行解，只需计算一次即可；
3. 计算步数使用当前行列与目标行列求差值的方法，偶数行列为 差异行列数量/2，
奇数行列为 (差异行列数量 + 1)/2。
"""
# 判断棋盘合法第一步：根据一(2)筛掉无法合法化的棋盘
n = len(board)
for i in range(n):
if board[0][0] ^ board[0][i] ^ board[i][0] ^ board[i][i] != 0:
return -1
# 二(1)所需变量预定义
rowcnt = 0
colcnt = 0
rowstep = 0
colstep = 0
# 将一(2)和二(1)合并进行以节省一次枚举
for i in range(n):
# 一(2) 判断合法性
colcnt += board[0][i]
rowcnt += board[i][0]
# 二(1) 计算所需步数
if board[0][i] == i%2:
colstep += 1
if board[i][0] == i%2:
rowstep += 1
# 排除不合法
if colcnt != n // 2 and colcnt != (n+1) // 2:
return -1
if rowcnt != n // 2 and rowcnt != (n+1) // 2:
return -1
# 一开始计算时视左上角为0，如果左上角为1要调整步数防止奇数行列出bug
# !!错误(1)!!：应该看1和0哪个更多来决定棋盘的左上角
# !!错误(2)!!：第一行/列的情况无法直接决定整个棋盘的状况，
# 不过由于一(1)的存在，可以直接服从多数，而不用在意到底是哪个数字
#print(rowstep,colstep)
if rowcnt < n - rowcnt: # 如果多数出现问题
rowstep = n - rowstep
if colcnt < n - colcnt: # 如果多数出现问题
colstep = n - colstep
#print(rowstep,colstep)
if n % 2 == 0:
return min(rowstep,n - rowstep) // 2 + min(colstep,n - colstep) // 2
else:
return (rowstep) // 2 + (colstep) // 2
