[讨论+下载]2174 - Tsuukin Hitofude（通勤一笔）

ssdy

我就是纯粹看的...........

DOT-X

技巧？
的确，我也想知道。目前我程序用到就是：
1.第X步与第X+1步方向不可能是反向。
2.走过的地方，不能再走。
3.走过的地方，如果是白色，那么这行的黑色格子不能再被走过。
4.按上右下左的优先顺序进行穷举计算，步数与电脑提示的步数相同。
5.计算当时位置，与终点位置的距离步数，小于电脑提示的剩余步数，说明走错了。
6.计算经过的格子是否将终点包围成不可入区域。(该算法未加入程序)

大致想到这些。以上仅适用于，无小块和无连接块的题。

希望大家再补充一些。

ssdy

原帖由 DOT-X 于 10/19/05 13:19 发表
技巧？
的确，我也想知道。目前我程序用到就是：
1.第X步与第X+1步方向不可能是反向。
2.走过的地方，不能再走。
3.走过的地方，如果是白色，那么这行的黑色格子不能再被走过。
4.按上右下左的优先顺序进行穷 ...

这些算法除了3,其他都只适合编程.自己做要是用穷举会死人的

DOT-X

原帖由 ssdy 于 2005-10-19 13:22 发表

这些算法除了3,其他都只适合编程.自己做要是用穷举会死人的

那些除了6之外，都是我那个程序在用的算法。。。

用穷举的话，一开始30步以内没有什么，至少我的CPU能算，之后每增加一位，就是增加4倍的时间。。


3.走过的地方，如果是白色，那么这行的黑色格子不能再被走过。

我当时的思路，是考虑
假定一行左边三个白的，右边三个黑的
当经过其中任意一个白色块，表示结束时，它将被翻转为黑色，所以黑色不能再被经过。

不过不适用于有连接块的题

[ 本帖最后由 DOT-X 于 2005-10-19 13:31 编辑 ]

ssdy

看很长时间还没思路的,我一般会先确定每一行应该翻哪种颜色

snowrabbit

可以把那个什么“画笔”加入算法呀~
给定起点和终点后，就可以确定必须要走的。
或者按一定规律先将图型做一定的变化，然后执行算法。

ssdy

我道是有一个想法.
就是按排列组合先把若干行全部翻转,然后在翻转后的图中只走颜色一样的,看能不能全部走下来
不过同样只适合机器

DOT-X

其实我还想到一种算法。
就是把每一行的色彩进行穷举

假定是最大迷题就是16*16
去掉边界就是14*14
每一行色彩的机率为二种，“白行”和“黑行”(如迷题有连接块，再追加第三种可能“空白行”)
也就是 00000000000000 到 11111111111111 种可能进行运算。

不过呢。。。。因为程序写的太乱，再加上不是一天写的，所以哪些代码什么用的都忘记了。所以没有加上这个算法

snowrabbit

原帖由 ssdy 于 2005-10-19 13:34 发表
我道是有一个想法.
就是按排列组合先把若干行全部翻转,然后在翻转后的图中只走颜色一样的,看能不能全部走下来
不过同样只适合机器

想过，但不知道这样有没有逻辑错误。

snowrabbit

顺便问一下，现在是不是所有的题都通了啊？
如果是这样的话偶就无视这个游戏了......

ssdy

你没看到我放出的全图鉴???

ssdy

原帖由 snowrabbit 于 10/19/05 13:36 发表

想过，但不知道这样有没有逻辑错误。

不会的.因为这样只是相当于走完之后再把若干行全部翻转.全白变全黑或全黑变全白..没有问题的
知识把这两步顺序变了一下

snowrabbit

原帖由 ssdy 于 2005-10-19 13:40 发表
你没看到我放出的全图鉴???

看到啊，没隐藏要素了么？

ssdy

隐藏的就是第九组

snowrabbit

原帖由 ssdy 于 2005-10-19 13:34 发表
我道是有一个想法.
就是按排列组合先把若干行全部翻转,然后在翻转后的图中只走颜色一样的,看能不能全部走下来
不过同样只适合机器

值得考虑，然后就该想想将哪些行翻转比较好了。比如说先随便走，没路的时候翻转下一行，继续走。

[ 本帖最后由 snowrabbit 于 2005-10-19 13:53 编辑 ]

ssdy

刚发现时间模式里两个都拿第一后会有新新东西
会出超大的一张图

果然其他１００道是时间模式里的．．．．．

[ 本帖最后由 ssdy 于 2005-10-19 15:23 编辑 ]

xliz

原帖由 ssdy 于 2005-10-19 15:34 发表
我道是有一个想法.
就是按排列组合先把若干行全部翻转,然后在翻转后的图中只走颜色一样的,看能不能全部走下来
不过同样只适合机器

在解你放出来的6灯泡题目的时候，我也有稍微用过这种方法。就例如图里面有的白色比较特别，都被黑色包围起来，我就会立刻假定我画的可能会要经过这里，然后我就会考虑它们所在的行，以及上/下一共三行的颜色会是什么组合：

这样就不外乎是在八种之间选择：
白　白　白　黑　黑　黑　黑　白
白　白　黑　黑　黑　白　白　黑
白、黑、黑、黑、白、白、黑、白

有的组合一应用到那三行的时候，就会马上发现不可以，那就可以排除掉一部分走法了。

原帖由 DOT-X 于 2005-10-19 15:35 发表
不过呢。。。。因为程序写的太乱，再加上不是一天写的，所以哪些代码什么用的都忘记了。所以没有加上这个算法

怎么这程序的可读性这么差~~~呵呵……说笑~~

[ 本帖最后由 xliz 于 2005-10-19 19:24 编辑 ]

DOT-X

原帖由 xliz 于 2005-10-19 17:22 发表
怎么这程序的可读性这么差~~~呵呵……说笑~~

那个。。。。个人问题。。。。
关于自动解题的那段代码。。。。
E文不好，所以变量名字，想到什么写什么，跳转也是，
再加上用中文的输入法要切来切去，麻烦，所以懒得写注释。

关于解题的代码。。。

Private Sub Command3_Click()
Dim ZL(15, 15) As Byte
Dim ZLG(15, 15) As Byte
Dim ZLE(15, 15) As Byte
Dim Z(1 To 255) As Byte
Dim zlx As Integer, zly As Integer
Dim f As Integer, f1 As Integer, f2 As Integer
Dim a As Byte, b As Byte
Dim at As Integer
Dim x As Integer, y As Integer
Dim t As Integer
Dim c As String
Dim m As Integer

If FS > 40 Then m = MsgBox("当前迷题的步数过多," & vbCrLf & "运算会花费很多时间" & vbCrLf & "是否进行运算", vbYesNo, "步数过多")
If m = 7 Then Exit Sub

Timer1.Enabled = True
tme = 0
Label5.Caption = ""
List1.Enabled = False
Command3.Enabled = False

If Check1.Value = 1 Then Form2.SetFocus

Open Fileaddress For Binary As #1
Form2.Label1.Caption = ""
b = 1
x = SX
y = SY
ZLG(x, y) = 1

GetData:
Get #1, AR + at, a
If a <> 255 Then
If a = 7 Then ZLG(zlx, zly) = 3
If a = 2 Or a = 3 Or a = 4 Or a = 8 Then
  MsgBox "发现无法解决的块,无法解题", vbOKOnly, "警告"
  Text1.Text = "无法解题"
  Timer1.Enabled = False
  Label5.Caption = "总计用时" & tme & "秒,共用步数" & b & "步"
  List1.Enabled = True
  Command3.Enabled = True
  Close #1
Exit Sub
  
End If
ZL(zlx, zly) = a
zlx = zlx + 1
End If

If a = 255 Then
Get #1, AR + at + 1, a
If a = 255 Then
  For f = 1 To LX - 2
   If ZLG(f, SY) <> 5 Then
    If ZL(f, SY) <> ZL(SX, SY) Then ZLG(f, SY) = 3
   End If
   If ZLG(f, EY) <> 5 Then
   If ZL(f, EY) <> ZL(EX, EY) Then ZLG(f, EY) = 3
   End If
  Next f
  GoTo NF
End If
zly = zly + 1
zlx = 0
End If

at = at + 1

GoTo GetData

NF:

Z(b) = Z(b) + 1

If Check1.Value = 1 Then
Form2.Label1.Caption = ""
For f = 1 To FS - 1
Form2.Label1.Caption = Form2.Label1.Caption & Z(f)
Next f
End If

DoEvents
If b > 2 Then
If Z(b - 1) = 1 And Z(b) = 3 Then GoTo NF
If Z(b - 1) = 2 And Z(b) = 4 Then GoTo NF
If Z(b - 1) = 3 And Z(b) = 1 Then GoTo NF
If Z(b - 1) = 4 And Z(b) = 2 Then GoTo NF
End If

If Z(b) <= 4 Then

Select Case Z(b)
Case 1
y = y - 1
If y < 0 Then y = y + 1: GoTo NF
If ZLG(x, y) <> 0 Then y = y + 1: GoTo NF
Case 2
x = x + 1
If x > (LX - 1) Then x = x - 1: GoTo NF
If ZLG(x, y) <> 0 Then x = x - 1: GoTo NF
Case 3
y = y + 1
If y > (LY - 1) Then y = y - 1: GoTo NF
If ZLG(x, y) <> 0 Then y = y - 1: GoTo NF
Case 4
x = x - 1
If x < 0 Then x = x + 1: GoTo NF
If ZLG(x, y) <> 0 Then x = x + 1: GoTo NF
End Select

Else
TB:
For f = b To FS - 1
   Z(f) = 0
Next f
b = b - 1
ZLG(x, y) = 0

  For f = 1 To LX - 1
   If ZLG(f, y) = 1 Then GoTo TB2
  Next f
  For f = 1 To LX - 1
   If ZLG(f, y) = 2 Then ZLG(f, y) = 0
  Next f

TB2:
If b = 0 Then
Text1.Text = "无解"
Timer1.Enabled = False
Label5.Caption = "总计用时" & tme \ 2 & "秒,共用步数" & b & "步"
List1.Enabled = True
Command3.Enabled = True
Close #1
Exit Sub
End If

Select Case Z(b)
Case 1
  y = y + 1
Case 2
  x = x - 1
Case 3
  y = y - 1
Case 4
  x = x + 1
End Select

GoTo NF

End If

b = b + 1

If (FS - b) < (Abs(x - EX) + Abs(y - EY)) Then GoTo TB

If b > FS Then
GoTo TB
End If

ZLG(x, y) = 1

If Check1.Value = 1 Then
Form2.Label2.Caption = ""
For f = 0 To LY - 1
For f1 = 0 To LX - 1
Form2.Label2.Caption = Form2.Label2.Caption & ZLG(f1, f) & " "
Next f1
Form2.Label2.Caption = Form2.Label2.Caption & vbCrLf
Next f
End If

If y > 0 And y < LY - 1 And x > 0 And x < LX - 1 Then
For f = 1 To LX - 2
  If ZLG(f, y) = 2 Then Exit For
  If ZLG(f, y) = 0 Then
   If ZL(f, y) <> ZL(x, y) Then ZLG(f, y) = 2
  End If
Next f
End If

If x = EX And y = EY Then GoTo TF

GoTo NF

TF:

For f1 = 1 To LY - 2
t = 0
For f = 1 To LX - 2
   If ZLG(f, f1) = 1 Then
    ZLE(f, f1) = (ZL(f, f1) Xor 1) + 1
   Else
    ZLE(f, f1) = (ZL(f, f1) Xor 0) + 1
   End If
   t = t + ZLE(f, f1)
Next f

If t <> LX - 2 And t <> (LX - 2) * 2 Then
  ZLG(x, y) = 0
  Z(b) = 0
  b = b - 1
   Select Case Z(b)
    Case 1
     y = y + 1
    Case 2
     x = x - 1
    Case 3
     y = y - 1
    Case 4
     x = x + 1
   End Select
  GoTo NF
End If

Next f1

Text1.Text = ""
For f2 = 1 To b - 1
Select Case Z(f2)
Case 1
c = "↑"
Case 2
c = "→"
Case 3
c = "↓"
Case 4
c = "←"
End Select
Text1.Text = Text1.Text & sl(CStr(f2)) & " " & c & vbCrLf
Next f2

Timer1.Enabled = False
Label5.Caption = "总计用时" & tme \ 2 & "秒,共用步数" & b & "步"
List1.Enabled = True
Command3.Enabled = True

Close #1
End Sub

什么时候有空，再从头开始写一个。。。。

[ 本帖最后由 DOT-X 于 2005-10-19 20:04 编辑 ]

xliz

想到一个解题思路，就像ssdy和DOT-X所说的那样使用排列组合（是这样叫吧？！）或者说先确定每一行的颜色是什么。那么如果题目有20行，那么就有1048576种可能性——对电脑来说应该不算多吧（我猜……）？然后算出每种组合要翻转的块数，如果多于规定步数，那么剔除该种组合；进一步地，因为到后面的题目，不一定只在黑白色的块上移动，有时候也会在边上移动，所以实际上翻转的块数会比规定的步数要少，因此可以继续把（翻转块数+N）>规定步数的组合剔除掉（N可以设为5，因为一般如果要用到边上，那在那里要花的步数都会多于5；如果想要剔除更多的组合，把N设为更大的数字，不过数字设得越高，就越有可能把正确的组合删掉） ；接着测试那些组合，看看能不能一次走完 翻转过 的方块。

[ 本帖最后由 xliz 于 2005-10-19 22:23 编辑 ]

DOT-X

题目最大为16*16，去掉边界为14*14，再去掉起点和终点的那一行，就是12-13行，实际可能为4096种或8192种。
如行色被固定的话，那每个必须经过的点和不能被经过的点，也被固定。

计算起点到最近边界的值为SL，终点到最近边界的值EL
计算全边界的值为N
A
如N+SL+EL大于总步数，N减1，回到A重新计算
B
计算必须经过点的数量再加上N，大于总步数，重新排列行色。
如无排列可出答案，N减1，回到B重新计算

这个意思？

注：从游戏内存使用看，游戏为每行色块(含边界)分配了16个位置，行也是。所以最大为16*16

[ 本帖最后由 DOT-X 于 2005-10-19 20:50 编辑 ]