如上图所示的棋盘,需要选择第2行第2列、第4行第2列两颗棋子,按照规则进行翻转便可使得棋盘变为纯黑。现编写程序找出实现棋盘纯色所需翻转棋子次数最少的方案并输出所挑选棋子的个数,若无答案则输出“无法翻转为纯色”。
解决该问题的算法原理:棋盘翻转方案为0000000000000000~1111111111111111之间的某几种,即十进制数 0~65535,利用枚举算法在0~65535之间枚举,即可找到最优方案。假设被选翻转棋子状态用1表示被选中,0表示不选中。例如某方案的十进制为1028即 2^10+2^2,转化为一个16位的二进制串0000010000000100就表示该棋盘中的第2行第2列、第4行第2列这两个棋子及其上下左右被选中翻转,我们认为该方案选中两个棋子进行翻转。
程序运行界面如下图所示,请回答下列问题。
'数组a储存棋盘原状态,数组b储存翻转后的棋盘状态
Dim a(1 To 16) As Integer, b(1 To 16) As Integer, minc As Long
Private Sub Form_Load()
'生成原始由0、1组成的棋盘状态,用数组 a(1)-a(16)保存,代码略
End Sub
Private Sub Command1_Click()
Dim k As Integer, c As Integer, i As Long, j As Long
minc = 100
For i = 0 To 65535
For j = 1 To 16 '初始化棋盘
b(j) = a(j)
Next j
k = 16: c = 0: j = i
Do While j > 0
If j Mod 2=1 Then
b(k) = 1 - b(k)
If k > 4 Then b(k - 4) = 1 - b(k - 4)
If Then b(k + 4) = 1 - b(k + 4)
If k Mod 4 <> 0 Then b(k + 1) = 1 - b(k + 1)
If k Mod 4 <> 1 Then b(k - 1) = 1 - b(k - 1)
c = c + 1
End If
k = k - 1
Loop
If Then minc = c
Next i
If minc = 100 Then Label1.Caption = "无法翻转为纯色!" Else Label1.Caption = "最少翻" + Str(minc) + "次"
End Sub
Function check() As Boolean '判断棋盘是否纯色
Dim flag As Boolean, i As Integer
flag = True
For i = 1 To 15
If Then flag = False: Exit For
Next i
check = flag
End Function