正方形网格里的最长路
假设地图是n行n列的正方形格子，起点在第1行第1列，
终点在第n行第n列，
每步的走法有上下左右4种。
问题1：
如何在某些格子里设置障碍，
才能使得起点到终点只有1条路，
且该路径的长度达到最大呢？
问题2：
如果不限制起点和终点的位置，
那么起点到终点之间的最短路径长度的最大值是多少？
#####
对于较小的n，我希望找到准确解。
对于较大的n，我希望找到与n有关的渐进公式。
例如，当n=7时，
问题1我最多可以构造出长度为31格的路径：
上图中的“×”表示障碍。 允许斜对角运动么？ 问题1：
如何在某些格子里设置障碍，
才能使得起点到终点只有1条路，
且该路径的长度达到最大呢？
解法1：
一共有$n^2$个格子，每个格子要么放障碍，要么不放障碍，
因此一共有$2^{n^2}$种放障碍的方案。
对这$2^{n^2}$种放障碍的方案逐一判断是否存在路径，
如果存在，就求出最短路径长度，
然后输出最短路径长度最长的那条路径，结果如下：
n=1: 1
1
n=2: 3
11
01
n=3: 5
111
001
001
n=4: 7
1111
0001
0001
0001
n=5: 17
11111
00001
11111
10000
11111
n=6: 23
110111
010101
110101
101101
101001
111001
输出的“n=6: 23”表示当n=6时，路径长度的最大值是23，
后面是具体的方案，其中“1”表示通路，“0”表示障碍
问题2：
如果不限制起点和终点的位置，
那么起点到终点之间的最短路径长度的最大值是多少？
解：
枚举起点、终点和$2^{n^2}$种放障碍的方案，
然后输出最短路径长度最长的那条路径，结果如下：
n=1: 1
1
n=2: 3
11
10
n=3: 7
111
101
110
n=4: 11
1111
1001
1011
1100
n=5: 17
11101
10101
10101
11011
01110
n=6: 24
110111
010101
110101
101101
101011
111010
这种解法的优点是不会遗漏任何解，缺点是慢。
n=6用时12小时，
n=7预计用时10年。
你们有更好的解法吗？ KeyTo9_Fans 发表于 2022-8-22 06:40
问题1：
如何在某些格子里设置障碍，
能否找到递推关系？ KeyTo9_Fans 发表于 2022-8-22 06:40
问题1：
如何在某些格子里设置障碍，
你是用暴力搜索吧？n=7用不了那么久吧？你划分得太细了。 本人創作的弈棋《巫師與殺手》，殺手的行動方式，跟本主題類似。巫師放置的地符，相當於他的障礙物。 ejsoon 发表于 2022-8-22 10:14
本人創作的弈棋《巫師與殺手》，殺手的行動方式，跟本主題類似。巫師放置的地符，相當於他的障礙物。
规则恐怕只有你懂…… aimisiyou 发表于 2022-8-22 11:47
规则恐怕只有你懂……
我可以做動畫或錄視頻。當然文字版規則其實也寫的很詳盡了。 本帖最后由 ejsoon 于 2022-8-23 07:45 编辑
aimisiyou 发表于 2022-8-22 11:47
规则恐怕只有你懂……
行棋至此，輪到殺手行動，其實巫師已經輸了，因為殺手只要「左下下下右右」六步，就能正好射殺巫師。
這局巫師只是失誤，一般棋局不會這麼快就結束。
[*]那麼為甚麼殺手要走「六步」？
$rarr$因為此時場上一共有六個地符（白色棋子），包括巫師腳下也有一個。
（當棋局進展到中局時，殺手可能要走十幾步。這時殺手可能會因無路可走而輸掉。）
[*]殺手如何射殺巫師？
$rarr$在殺手的回合中，如果行走結束時，停在與巫師同一條線但不同區的地方，就能擊斃對方。
本棋棋盤是6x6，一個區就是3x3。如果殺手跟巫師處在同一個區，巫師不會遭到射殺。
本帖最后由 aimisiyou 于 2022-8-23 13:10 编辑
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
看来往后面结果就不对了。