正方形网格里的最长路

KeyTo9_Fans

假设地图是n行n列的正方形格子，

起点在第1行第1列，

终点在第n行第n列，

每步的走法有上下左右4种。

问题1：

如何在某些格子里设置障碍，

才能使得起点到终点只有1条路，

且该路径的长度达到最大呢？

问题2：

如果不限制起点和终点的位置，

那么起点到终点之间的最短路径长度的最大值是多少？

#####

对于较小的n，我希望找到准确解。

对于较大的n，我希望找到与n有关的渐进公式。

例如，当n=7时，

问题1我最多可以构造出长度为31格的路径：



上图中的“×”表示障碍。

gxqcn

允许斜对角运动么？

KeyTo9_Fans

问题1：

如何在某些格子里设置障碍，

才能使得起点到终点只有1条路，

且该路径的长度达到最大呢？

解法1：

一共有$n^2$个格子，每个格子要么放障碍，要么不放障碍，

因此一共有$2^{n^2}$种放障碍的方案。

对这$2^{n^2}$种放障碍的方案逐一判断是否存在路径，

如果存在，就求出最短路径长度，

然后输出最短路径长度最长的那条路径，结果如下：

1. n=1: 1
   
2. 1
   
3. 
   
4. n=2: 3
   
5. 11
   
6. 01
   
7. 
   
8. n=3: 5
   
9. 111
   
10. 001
    
11. 001
    
12. 
    
13. n=4: 7
    
14. 1111
    
15. 0001
    
16. 0001
    
17. 0001
    
18. 
    
19. n=5: 17
    
20. 11111
    
21. 00001
    
22. 11111
    
23. 10000
    
24. 11111
    
25. 
    
26. n=6: 23
    
27. 110111
    
28. 010101
    
29. 110101
    
30. 101101
    
31. 101001
    
32. 111001

复制代码

输出的“n=6: 23”表示当n=6时，路径长度的最大值是23，

后面是具体的方案，其中“1”表示通路，“0”表示障碍

问题2：

如果不限制起点和终点的位置，

那么起点到终点之间的最短路径长度的最大值是多少？

解：

枚举起点、终点和$2^{n^2}$种放障碍的方案，

然后输出最短路径长度最长的那条路径，结果如下：

1. n=1: 1
   
2. 1
   
3. 
   
4. n=2: 3
   
5. 11
   
6. 10
   
7. 
   
8. n=3: 7
   
9. 111
   
10. 101
    
11. 110
    
12. 
    
13. n=4: 11
    
14. 1111
    
15. 1001
    
16. 1011
    
17. 1100
    
18. 
    
19. n=5: 17
    
20. 11101
    
21. 10101
    
22. 10101
    
23. 11011
    
24. 01110
    
25. 
    
26. n=6: 24
    
27. 110111
    
28. 010101
    
29. 110101
    
30. 101101
    
31. 101011
    
32. 111010

复制代码

这种解法的优点是不会遗漏任何解，缺点是慢。

n=6用时12小时，

n=7预计用时10年。

你们有更好的解法吗？

aimisiyou

KeyTo9_Fans 发表于 2022-8-22 06:40
问题1：

如何在某些格子里设置障碍，

能否找到递推关系？

aimisiyou

KeyTo9_Fans 发表于 2022-8-22 06:40
问题1：

如何在某些格子里设置障碍，

你是用暴力搜索吧？n=7用不了那么久吧？你划分得太细了。

ejsoon

本人創作的弈棋《巫師與殺手》，殺手的行動方式，跟本主題類似。巫師放置的地符，相當於他的障礙物。

aimisiyou

ejsoon 发表于 2022-8-22 10:14
本人創作的弈棋《巫師與殺手》，殺手的行動方式，跟本主題類似。巫師放置的地符，相當於他的障礙物。

规则恐怕只有你懂……

ejsoon

aimisiyou 发表于 2022-8-22 11:47
规则恐怕只有你懂……

我可以做動畫或錄視頻。當然文字版規則其實也寫的很詳盡了。

ejsoon

aimisiyou 发表于 2022-8-22 11:47
规则恐怕只有你懂……

行棋至此，輪到殺手行動，其實巫師已經輸了，因為殺手只要「左下下下右右」六步，就能正好射殺巫師。

這局巫師只是失誤，一般棋局不會這麼快就結束。

• 那麼為甚麼殺手要走「六步」？
  
  $rarr$因為此時場上一共有六個地符（白色棋子），包括巫師腳下也有一個。
  
  （當棋局進展到中局時，殺手可能要走十幾步。這時殺手可能會因無路可走而輸掉。）
  
• 殺手如何射殺巫師？
  
  $rarr$在殺手的回合中，如果行走結束時，停在與巫師同一條線但不同區的地方，就能擊斃對方。
  
  本棋棋盤是6x6，一個區就是3x3。如果殺手跟巫師處在同一個區，巫師不會遭到射殺。
  
  

aimisiyou

F（N）=F（N-4）+4*N-4，    N>=5。
F（1）=1
F（2）=3
F（3）=5
F（4）=7
F（5）=11
F（6）=23
F（7）=29
看来往后面结果就不对了。