问题
N*N矩阵由0和1组成,判断是否能通过行与行或者列与列的交换,达到国际象棋棋盘的样子(任意相邻元素不同),如果能,求出最小交换步数
解决方案
- 问题的分析和转化
- 算法的简化
1.交换整行或整列的位置不会使相同的行和相同的列的数量减少
2.符合要求的矩阵有且仅有两种不同的行(列)
3.通过0,1表示这两种行(列),到达目标状态所需的最小交换步骤,就是这个状态序列与理想状态序列的差异位数(相同的位不需要交换)
4.通过 xor 和 Integer.bitCount 可以高效地求出二进制上的差异位数,除以2就是所需的最小交换步数