老鼠走迷宫

香川群子

是应该用递归做。

代码其实一点也不难的。

规定：
1. 迷宫二维表在A1单元格所在区域。
2. 边框和墙体写入-1、通道留空
3. 任意起点填写=1、终点填写=9 (或改为99？)

按下按钮，递归返回单元格地址表示的路径，以及路径顺序结果表

代码如下：

1. Dim a, m&, n&, i2&, j2&, k&
   
2. Sub test() 'by kagawa 2017/5/17
   
3. 
   
4.     a = [a1].CurrentRegion '读取迷宫数据表
   
5.     m = UBound(a): n = UBound(a, 2) '最大行m 最大列n
   
6.    
   
7.     '遍历查询起点、终点坐标位置
   
8.     For i = 2 To m - 1
   
9.         For j = 2 To n - 1
   
10.             If a(i, j) = 1 Then i1 = i: j1 = j '起点位置
    
11.             If a(i, j) = 99 Then i2 = i: j2 = j: a(i, j) = 0 '终点位置
    
12.         Next
    
13.     Next
    
14.    
    
15.     k = 0 '路径记录行位置初始化
    
16.     Call dg(Cells(i1, j1).Address(0, 0), i1, j1, 2) '递归查找迷宫路线
    
17.     MsgBox k '有效路径数
    
18. End Sub
    
19. Sub dg(s, i, j, t) '路径记录s、当前坐标i,j、路径节点序号
    
20.     If i = i2 And j = j2 Then '到终点时停止
    
21.         k = k + 1: Cells(k, n + 2) = s '输出路径结果文本字符
    
22.         a(i, j) = 99: Cells(1, n + 3).Resize(m, n) = a '输出二维迷宫表结果
    
23.         Exit Sub '结束向下递归查询
    
24.     End If
    
25.    
    
26.     '以下依次为向上、向左、向下、向右进行递归路径探索
    
27.     If i > 2 Then If a(i - 1, j) = 0 Then a(i - 1, j) = t: Call dg(s & "-" & Cells(i - 1, j).Address(0, 0), i - 1, j, t + 1): a(i - 1, j) = ""
    
28.     If j > 2 Then If a(i, j - 1) = 0 Then a(i, j - 1) = t: Call dg(s & "-" & Cells(i, j - 1).Address(0, 0), i, j - 1, t + 1): a(i, j - 1) = ""
    
29.     If i < m - 1 Then If a(i + 1, j) = 0 Then a(i + 1, j) = t: Call dg(s & "-" & Cells(i + 1, j).Address(0, 0), i + 1, j, t + 1): a(i + 1, j) = ""
    
30.     If j < n - 1 Then If a(i, j + 1) = 0 Then a(i, j + 1) = t: Call dg(s & "-" & Cells(i, j + 1).Address(0, 0), i, j + 1, t + 1): a(i, j + 1) = ""
    
31. End Sub
    

复制代码

香川群子

这样的递归深度查询算法，能够保证找到出路解，但不能保证是最短路径。

……
如需计算最短路径，只有进行广度搜寻，然后根据搜寻结果逆推得到最佳路径。

Moneky

香川群子 发表于 2017-5-17 22:17
是应该用递归做。

代码其实一点也不难的。

为啥你的代码不需要审核？？
谁能告诉我我前面楼层中的代码中哪个关键词触发了审核机制？

香川群子

我觉得广度搜索可以直接用数组来做。

hcm19522

迷宮版本自行設計
B2:H8=OFFSET($S$1,($R$2-1)*8+ROW(A1),COLUMN(A1))
B10:H16=IF(B2="*",IF((B3="#")+(C2="#")+(B1="#")+(A2="#")+(B3="-")+(C2="-")+(B1="-")+(A2="-")>2,"-","*"),B2)
B10:H16與B2:H8格式化與J2:P8三次格式化相同
B10:H16格式化後 ,一起往下複製到 B18 .B26 .B34 .B42 … B58 或更多
J2:P8取最後=B58
J2:P8格式化 字色 底色均黃色=J2="*"
J2:P8格式化 字色白色=J2="-"
J2:P8格式化 字色 底色均藍色=J2="#"

香川群子

可以用数组来做。

香川群子

数组的也改了一下。