正方形网格里的最长路 - 第3页 - 趣题妙解 - 数学研发论坛

aimisiyou 发表于 2022-9-1 18:06:03

n=7时，所有最长路径有44条。
((1 8 15 16 17 10 3 4 5 12 13 14 21 28 27 26 25 32 31 30 29 36 43 44 45 46 47 40 41 42 49)
(1 8 15 16 17 10 3 4 5 6 13 14 21 28 27 26 25 32 31 30 29 36 43 44 45 46 47 40 41 42 49)
(1 8 15 16 17 10 3 4 5 6 7 14 21 20 19 26 25 32 31 30 29 36 43 44 45 46 47 40 41 42 49)
(1 8 15 16 17 10 3 4 5 6 7 14 21 20 27 26 25 32 31 30 29 36 43 44 45 46 47 40 41 42 49)
(1 8 15 16 17 10 3 4 5 6 7 14 21 28 27 26 25 32 31 30 29 36 43 44 45 46 47 40 41 42 49)
(1 8 15 16 17 10 11 4 5 6 13 14 21 28 27 26 25 32 31 30 29 36 43 44 45 46 47 40 41 42 49)
(1 8 15 16 17 10 11 4 5 6 7 14 21 20 19 26 25 32 31 30 29 36 43 44 45 46 47 40 41 42 49)
(1 8 15 16 17 10 11 4 5 6 7 14 21 20 27 26 25 32 31 30 29 36 43 44 45 46 47 40 41 42 49)
(1 8 15 16 17 10 11 4 5 6 7 14 21 28 27 26 25 32 31 30 29 36 43 44 45 46 47 40 41 42 49)
(1 8 15 16 17 10 11 12 5 6 7 14 21 20 27 26 25 32 31 30 29 36 43 44 45 46 47 40 41 42 49)
(1 8 15 16 17 10 11 12 5 6 7 14 21 28 27 26 25 32 31 30 29 36 43 44 45 46 47 40 41 42 49)
(1 8 9 10 3 4 5 6 7 14 21 20 19 18 25 24 23 22 29 36 43 44 45 38 39 40 33 34 35 42 49)
(1 8 9 10 3 4 5 6 7 14 21 20 19 18 25 24 23 22 29 36 43 44 45 46 39 40 33 34 35 42 49)
(1 8 9 10 3 4 5 6 7 14 21 20 19 18 25 24 23 22 29 36 43 44 45 46 47 40 33 34 35 42 49)
(1 8 9 10 3 4 5 6 7 14 21 20 19 18 25 24 23 22 29 36 37 44 45 46 39 40 33 34 35 42 49)
(1 8 9 10 3 4 5 6 7 14 21 20 19 18 25 24 23 22 29 36 37 44 45 46 47 40 33 34 35 42 49)
(1 8 9 10 3 4 5 6 7 14 21 20 19 18 25 24 23 22 29 36 37 38 45 46 47 40 33 34 35 42 49)
(1 8 9 10 3 4 5 6 7 14 21 20 19 18 25 24 23 30 29 36 43 44 45 38 39 40 33 34 35 42 49)
(1 8 9 10 3 4 5 6 7 14 21 20 19 18 25 24 23 30 29 36 43 44 45 46 39 40 33 34 35 42 49)
(1 8 9 10 3 4 5 6 7 14 21 20 19 18 25 24 23 30 29 36 43 44 45 46 47 40 33 34 35 42 49)
(1 8 9 10 3 4 5 6 7 14 21 20 19 18 25 24 31 30 29 36 43 44 45 46 39 40 33 34 35 42 49)
(1 8 9 10 3 4 5 6 7 14 21 20 19 18 25 24 31 30 29 36 43 44 45 46 47 40 33 34 35 42 49)
(1 2 9 16 15 22 29 36 43 44 45 38 31 24 25 18 11 4 5 6 13 20 21 28 35 34 33 40 47 48 49)
(1 2 9 16 15 22 29 36 43 44 45 38 31 24 25 18 11 4 5 6 13 14 21 28 27 34 33 40 47 48 49)
(1 2 9 16 15 22 29 36 43 44 45 38 31 24 25 18 11 4 5 6 13 14 21 28 35 34 33 40 47 48 49)
(1 2 9 16 15 22 29 36 43 44 45 38 31 24 25 18 11 4 5 6 7 14 21 20 27 34 33 40 47 48 49)
(1 2 9 16 15 22 29 36 43 44 45 38 31 24 25 18 11 4 5 6 7 14 21 28 27 34 33 40 47 48 49)
(1 2 9 16 15 22 29 36 43 44 45 38 31 24 25 18 11 4 5 6 7 14 21 28 35 34 33 40 47 48 49)
(1 2 9 16 15 22 29 36 43 44 45 38 31 24 25 18 11 12 5 6 7 14 21 20 27 34 33 40 47 48 49)
(1 2 9 16 15 22 29 36 43 44 45 38 31 24 25 18 11 12 5 6 7 14 21 28 27 34 33 40 47 48 49)
(1 2 9 16 15 22 29 36 43 44 45 38 31 24 25 18 11 12 5 6 7 14 21 28 35 34 33 40 47 48 49)
(1 2 9 16 15 22 29 36 43 44 45 38 31 24 25 18 19 12 5 6 7 14 21 28 27 34 33 40 47 48 49)
(1 2 9 16 15 22 29 36 43 44 45 38 31 24 25 18 19 12 5 6 7 14 21 28 35 34 33 40 47 48 49)
(1 2 3 10 17 16 15 22 29 36 43 44 45 38 31 32 25 26 19 12 5 6 7 14 21 28 35 34 41 48 49)
(1 2 3 10 17 16 15 22 29 36 43 44 45 38 39 32 25 26 19 12 5 6 7 14 21 28 35 34 41 48 49)
(1 2 3 10 17 16 15 22 29 36 43 44 45 46 39 32 25 26 19 12 5 6 7 14 21 28 35 34 41 48 49)
(1 2 3 10 17 16 15 22 29 36 37 44 45 46 39 32 25 26 19 12 5 6 7 14 21 28 35 34 41 48 49)
(1 2 3 10 17 16 15 22 29 30 37 44 45 46 39 32 25 26 19 12 5 6 7 14 21 28 35 34 41 48 49)
(1 2 3 10 17 16 23 22 29 36 43 44 45 38 31 32 25 26 19 12 5 6 7 14 21 28 35 34 41 48 49)
(1 2 3 10 17 16 23 22 29 36 43 44 45 38 39 32 25 26 19 12 5 6 7 14 21 28 35 34 41 48 49)
(1 2 3 10 17 16 23 22 29 36 43 44 45 46 39 32 25 26 19 12 5 6 7 14 21 28 35 34 41 48 49)
(1 2 3 10 17 16 23 22 29 36 37 44 45 46 39 32 25 26 19 12 5 6 7 14 21 28 35 34 41 48 49)
(1 2 3 10 17 16 23 30 29 36 43 44 45 38 39 32 25 26 19 12 5 6 7 14 21 28 35 34 41 48 49)
(1 2 3 10 17 16 23 30 29 36 43 44 45 46 39 32 25 26 19 12 5 6 7 14 21 28 35 34 41 48 49))
_$

aimisiyou 发表于 2022-9-2 12:48:06

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

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

插头DP能找出最长路径吗？不是用宽搜么？我是用表数据形式来进行宽搜，万物皆可“表”。

KeyTo9_Fans 发表于 2022-9-16 23:05:55

首项$1/2 n^2$是不对的，应该是$2/3 n^2$

n=2: 3
〇 ※
〇〇
10
n=3: 7
〇〇〇
〇 ※ 〇
〇〇 ※
32
n=4: 11
〇〇〇〇
〇 ※ ※ 〇
〇 ※ 〇〇
〇〇 ※ ※
93
n=5: 17
〇〇〇 ※ 〇
〇 ※ 〇 ※ 〇
〇 ※ 〇 ※ 〇
〇〇 ※ 〇〇
※ 〇〇〇 ※
257
n=6: 24
〇〇〇 ※ 〇〇
〇 ※ 〇〇 ※ 〇
〇 ※ ※ 〇 ※ 〇
〇 ※ 〇〇 ※ 〇
〇 ※ 〇 ※ 〇〇
〇 ※ 〇〇〇 ※
685
n=7: 33
〇〇〇 ※ 〇〇〇
〇 ※ 〇 ※ 〇 ※ 〇
〇 ※ 〇 ※ 〇 ※ 〇
※ 〇〇 ※ 〇 ※ 〇
〇〇 ※ 〇〇 ※ 〇
〇 ※ 〇〇 ※ 〇〇
〇〇〇 ※ 〇〇 ※
1826
n=8: 42
〇〇 ※ 〇〇〇〇〇
〇 ※ 〇〇 ※ ※ ※ 〇
〇〇〇 ※ 〇〇〇〇
※ ※ ※ 〇〇 ※ ※ ※
〇〇〇〇 ※ 〇〇〇
〇 ※ ※ ※ 〇〇 ※ 〇
〇 ※ 〇〇〇 ※ 〇〇
〇〇〇 ※ ※ 〇〇 ※
5029
n=9: 53
〇〇〇 ※ 〇〇〇〇〇
〇 ※ ※ 〇〇 ※ ※ ※ 〇
〇 ※ 〇〇 ※ 〇〇〇〇
〇 ※ 〇 ※ 〇〇 ※ ※ ※
〇〇〇 ※ 〇 ※ 〇〇〇
※ ※ ※ 〇〇 ※ 〇 ※ 〇
〇〇〇〇 ※ 〇〇 ※ 〇
〇 ※ ※ ※ 〇〇 ※ 〇〇
〇〇〇〇〇 ※ 〇〇 ※
14140
n=10: 64
〇〇〇〇〇〇 ※ 〇〇〇
〇 ※ ※ ※ ※ 〇〇〇 ※ 〇
〇 ※ 〇〇〇 ※ ※ ※ 〇〇
〇 ※ 〇 ※ 〇〇〇 ※ 〇 ※
〇 ※ 〇〇 ※ ※ 〇 ※ 〇〇
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
※ 〇 ※ ※ 〇 ※ ※ 〇 ※ 〇
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇
〇〇〇 ※ 〇〇 ※ 〇〇 ※
39978
n=11: 77
〇〇〇 ※ 〇〇〇 ※ 〇〇〇
〇 ※ 〇 ※ 〇 ※ 〇 ※ 〇 ※ 〇
〇 ※ 〇 ※ 〇 ※ 〇 ※ 〇〇 ※
〇 ※ 〇 ※ 〇 ※ 〇〇 ※ 〇〇
〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇
〇〇 ※ 〇〇 ※ 〇〇 ※ ※ ※
※ 〇 ※ ※ 〇〇 ※ 〇〇〇〇
〇〇 ※ ※ ※ 〇〇 ※ ※ ※ 〇
〇 ※ 〇〇〇 ※ 〇〇 ※ 〇〇
〇〇〇 ※ 〇〇 ※ 〇〇〇 ※
112395
n=12: 92
〇〇〇〇〇 ※ 〇〇 ※ 〇〇〇
〇 ※ ※ ※ 〇〇 ※ 〇〇〇 ※ 〇
〇〇〇〇 ※ 〇〇 ※ ※ ※ 〇〇
※ ※ ※ 〇〇 ※ 〇〇〇 ※ 〇 ※
〇〇〇 ※ 〇〇 ※ ※ 〇 ※ 〇〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇
※ 〇 ※ ※ 〇〇 ※ 〇〇 ※ ※ ※
〇〇 ※ ※ ※ 〇〇 ※ 〇〇〇〇
〇 ※ 〇〇〇 ※ 〇〇 ※ ※ ※ 〇
〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ 〇〇
〇〇〇 ※ ※ 〇〇 ※ 〇〇〇 ※
313977
n=13: 107
〇〇〇 ※ 〇〇 ※ 〇〇〇〇〇 ※
〇 ※ 〇〇〇 ※ 〇〇 ※ ※ ※ 〇〇
〇〇 ※ ※ ※ 〇〇 ※ 〇〇〇 ※ 〇
※ 〇 ※ 〇〇〇 ※ 〇〇 ※ 〇 ※ 〇
〇〇 ※ 〇 ※ ※ 〇〇 ※ 〇〇 ※ 〇
〇 ※ 〇〇 ※ 〇〇 ※ ※ 〇 ※ 〇〇
〇〇〇 ※ 〇〇 ※ 〇〇〇 ※ 〇 ※
※ ※ ※ 〇〇 ※ 〇〇 ※ ※ ※ 〇〇
〇〇 ※ 〇 ※ 〇〇 ※ 〇〇〇 ※ 〇
〇 ※ 〇〇 ※ 〇 ※ 〇〇 ※ 〇 ※ 〇
〇 ※ 〇 ※ 〇〇 ※ 〇 ※ 〇〇 ※ 〇
〇 ※ 〇 ※ 〇 ※ 〇〇 ※ 〇 ※ 〇〇
〇〇〇 ※ 〇〇〇 ※ ※ 〇〇〇 ※
875546
n=14: 123
〇〇〇〇〇 ※ 〇〇 ※ 〇〇〇〇〇
〇 ※ ※ ※ 〇〇 ※ 〇〇〇 ※ ※ ※ 〇
〇〇〇〇 ※ 〇〇 ※ ※ ※ 〇〇〇〇
※ ※ ※ 〇〇 ※ 〇〇〇 ※ 〇 ※ ※ ※
〇〇〇 ※ 〇〇 ※ ※ 〇 ※ 〇〇〇〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ ※ 〇
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ 〇
※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ ※
※ 〇 ※ ※ 〇〇 ※ 〇〇 ※ 〇〇〇〇
〇〇 ※ ※ ※ 〇〇 ※ 〇 ※ ※ ※ ※ 〇
〇 ※ 〇〇〇 ※ 〇 ※ 〇 ※ 〇〇〇〇
〇〇〇 ※ 〇〇〇 ※ 〇〇〇 ※ ※ ※
2446050
n=15: 142
〇〇〇 ※ 〇〇〇 ※ 〇〇〇 ※ 〇〇〇
〇 ※ 〇 ※ 〇 ※ 〇 ※ 〇 ※ 〇〇〇 ※ 〇
〇 ※ 〇 ※ 〇 ※ 〇 ※ 〇〇 ※ ※ ※ 〇〇
〇 ※ 〇 ※ 〇 ※ 〇〇 ※ 〇〇〇 ※ 〇 ※
〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ ※ 〇 ※ 〇〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※
※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇
※ 〇 ※ ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ ※
〇〇 ※ ※ ※ 〇〇 ※ 〇〇 ※ 〇〇〇〇
〇 ※ 〇〇〇 ※ 〇〇 ※ 〇 ※ ※ ※ ※ 〇
〇 ※ 〇 ※ 〇〇 ※ 〇 ※ 〇 ※ 〇〇〇〇
〇〇〇 ※ ※ 〇〇〇 ※ 〇〇〇 ※ ※ ※
6848345
n=16: 162
〇〇〇〇〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇
〇 ※ ※ ※ ※ 〇〇 ※ 〇〇 ※ 〇〇〇 ※ 〇
〇 ※ 〇〇〇 ※ 〇〇 ※ 〇〇 ※ ※ ※ 〇〇
〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ 〇 ※
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
※ 〇 ※ ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇 ※ 〇
〇〇 ※ ※ ※ 〇〇 ※ 〇〇 ※ 〇〇〇 ※ 〇
〇 ※ 〇〇〇 ※ 〇〇 ※ 〇〇 ※ ※ ※ 〇〇
〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ 〇 ※
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
※ 〇 ※ ※ 〇〇 ※ 〇〇 ※ 〇 ※ ※ 〇 ※ 〇
〇〇 ※ ※ ※ 〇〇 ※ 〇 ※ 〇 ※ 〇〇 ※ 〇
〇 ※ 〇〇〇 ※ 〇 ※ 〇 ※ 〇 ※ 〇 ※ 〇〇
〇〇〇 ※ 〇〇〇 ※ 〇〇〇 ※ 〇〇〇 ※
19183535

n=2: length=3, status=10
n=3: length=7, status=32
n=4: length=11, status=93
n=5: length=17, status=257
n=6: length=24, status=685
n=7: length=33, status=1826
n=8: length=42, status=5029
n=9: length=53, status=14140
n=10: length=64, status=39978
n=11: length=77, status=112395
n=12: length=92, status=313977
n=13: length=107, status=875546
n=14: length=123, status=2446050
n=15: length=142, status=6848345
n=16: length=162, status=19183535
n=17: length=182, status=53689393

n=17目前只知道长度，具体方案未知

mathe 发表于 2022-9-17 09:04:34

n=15这种模式看来是典型代表

KeyTo9_Fans 发表于 2022-9-17 09:20:22

达到$2/3 n^2$的窍门是尽量斜着走，尽量多拐弯，少走直路

起点终点必须在左上角、右下角的最优解如下：

n=2: 3
〇 ※
〇〇
5
n=3: 5
〇〇 ※
※ 〇 ※
※ 〇〇
15
n=4: 7
〇〇〇 ※
※ ※ 〇 ※
※ ※ 〇 ※
※ ※ 〇〇
47
n=5: 17
〇〇〇〇〇
※ ※ ※ ※ 〇
〇〇〇〇〇
〇 ※ ※ ※ ※
〇〇〇〇〇
115
n=6: 23
〇 ※ 〇〇〇〇
〇 ※ 〇 ※ ※ 〇
〇 ※ 〇 ※ 〇〇
〇 ※ 〇 ※ 〇 ※
〇 ※ 〇 ※ 〇 ※
〇〇〇 ※ 〇〇
285
n=7: 31
〇〇〇 ※ 〇〇〇
※ ※ 〇 ※ 〇 ※ 〇
〇〇〇 ※ 〇 ※ 〇
〇 ※ ※ 〇〇 ※ 〇
〇 ※ 〇〇 ※ 〇〇
〇 ※ 〇 ※ ※ 〇 ※
〇〇〇 ※ ※ 〇〇
720
n=8: 39
〇 ※ 〇〇〇〇〇〇
〇 ※ 〇 ※ ※ ※ ※ 〇
〇 ※ 〇〇〇〇 ※ 〇
〇〇 ※ ※ ※ 〇 ※ 〇
※ 〇 ※ 〇〇〇 ※ 〇
〇〇 ※ 〇 ※ ※ 〇〇
〇 ※ 〇〇 ※ ※ 〇 ※
〇〇〇 ※ ※ ※ 〇〇
1821
n=9: 51
〇 ※ 〇〇〇 ※ 〇〇〇
〇 ※ 〇 ※ 〇〇〇 ※ 〇
〇 ※ 〇〇 ※ ※ ※ 〇〇
〇〇 ※ 〇〇〇 ※ 〇 ※
※ 〇〇 ※ ※ 〇 ※ 〇〇
※ ※ 〇 ※ 〇〇 ※ ※ 〇
〇〇〇 ※ 〇 ※ 〇〇〇
〇 ※ ※ 〇〇 ※ 〇 ※ ※
〇〇〇〇 ※ ※ 〇〇〇
4572
n=10: 63
〇〇〇〇 ※ 〇〇〇〇〇
※ ※ ※ 〇〇〇 ※ ※ ※ 〇
〇〇〇 ※ ※ ※ 〇〇〇〇
〇 ※ 〇〇 ※ 〇〇 ※ ※ ※
〇〇 ※ 〇 ※ 〇 ※ 〇〇〇
※ 〇 ※ 〇〇〇 ※ 〇 ※ 〇
〇〇 ※ ※ ※ ※ 〇〇 ※ 〇
〇 ※ 〇〇〇 ※ 〇 ※ 〇〇
〇 ※ 〇 ※ 〇 ※ 〇 ※ 〇 ※
〇〇〇 ※ 〇〇〇 ※ 〇〇
11458
n=11: 75
〇 ※ 〇〇〇 ※ 〇〇〇〇〇
〇 ※ 〇 ※ 〇〇〇 ※ ※ ※ 〇
〇 ※ 〇〇 ※ ※ ※ 〇〇〇〇
〇〇 ※ 〇〇 ※ 〇〇 ※ ※ ※
※ 〇 ※ ※ 〇 ※ 〇 ※ 〇〇〇
〇〇 ※ 〇〇 ※ 〇 ※ 〇 ※ 〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇 ※ 〇
〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇 ※ 〇 ※ 〇 ※ 〇〇 ※ 〇〇
〇 ※ 〇 ※ 〇 ※ 〇 ※ ※ 〇 ※
〇〇〇 ※ 〇〇〇 ※ ※ 〇〇
28883
n=12: 89
〇 ※ 〇〇〇〇〇〇 ※ 〇〇〇
〇 ※ 〇 ※ ※ ※ ※ 〇〇〇 ※ 〇
〇 ※ 〇〇〇〇〇 ※ ※ ※ 〇〇
〇〇 ※ ※ ※ ※ 〇〇〇 ※ 〇 ※
※ 〇 ※ 〇〇〇 ※ ※ 〇 ※ 〇〇
〇〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇 ※ ※ 〇〇 ※ 〇〇 ※ 〇 ※ 〇
〇〇〇 ※ 〇〇 ※ 〇〇〇 ※ 〇
※ ※ 〇 ※ ※ 〇〇 ※ ※ ※ ※ 〇
〇〇〇 ※ ※ ※ 〇〇〇 ※ 〇〇
〇 ※ ※ 〇〇〇 ※ ※ 〇 ※ 〇 ※
〇〇〇〇 ※ 〇〇〇〇 ※ 〇〇
73410
n=13: 105
〇 ※ 〇〇〇〇 ※ 〇〇〇〇〇 ※
〇 ※ 〇 ※ ※ 〇〇〇 ※ ※ ※ 〇〇
〇 ※ 〇〇〇 ※ ※ ※ 〇〇〇 ※ 〇
〇〇 ※ ※ 〇〇〇 ※ 〇 ※ 〇〇〇
※ 〇〇〇 ※ ※ 〇 ※ 〇〇 ※ ※ ※
※ ※ ※ 〇〇 ※ 〇〇 ※ 〇〇〇 ※
〇〇〇 ※ 〇〇 ※ 〇〇 ※ ※ 〇〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇 ※ 〇
〇〇 ※ 〇〇 ※ 〇〇 ※ ※ 〇 ※ 〇
※ 〇 ※ ※ 〇〇 ※ 〇 ※ 〇〇 ※ 〇
〇〇 ※ ※ ※ 〇〇〇 ※ 〇 ※ 〇〇
〇 ※ 〇〇〇 ※ ※ ※ 〇〇 ※ 〇 ※
〇〇〇 ※ 〇〇〇〇〇 ※ ※ 〇〇
187665
n=14: 121
〇 ※ 〇〇〇〇〇〇 ※ 〇〇〇〇〇
〇〇〇 ※ ※ ※ ※ 〇 ※ 〇 ※ ※ ※ 〇
※ ※ ※ 〇〇〇 ※ 〇 ※ 〇〇〇 ※ 〇
〇〇〇〇 ※ 〇 ※ 〇〇 ※ ※ 〇 ※ 〇
〇 ※ ※ ※ ※ 〇〇 ※ 〇〇 ※ 〇 ※ 〇
〇 ※ 〇〇〇 ※ 〇〇 ※ 〇〇〇 ※ 〇
〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ ※ ※ 〇〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇 ※ 〇 ※
〇〇 ※ 〇〇 ※ 〇〇 ※ ※ 〇 ※ 〇〇
※ 〇 ※ ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇〇 ※ ※ ※ 〇〇 ※ 〇〇 ※ 〇 ※ 〇
〇 ※ 〇〇〇 ※ 〇〇 ※ 〇 ※ 〇〇〇
〇 ※ 〇 ※ 〇〇 ※ 〇 ※ 〇〇 ※ ※ ※
〇〇〇 ※ ※ 〇〇〇 ※ ※ 〇〇〇〇
480863
n=15: 139
〇〇〇〇 ※ 〇〇〇〇〇 ※ 〇〇〇〇
※ ※ ※ 〇〇〇 ※ ※ ※ 〇〇〇 ※ ※ 〇
〇〇〇 ※ ※ ※ 〇〇〇 ※ ※ ※ 〇〇〇
〇 ※ 〇〇〇 ※ 〇 ※ 〇〇〇 ※ 〇 ※ ※
〇〇 ※ ※ 〇 ※ 〇〇 ※ ※ 〇 ※ 〇〇〇
※ 〇 ※ ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ 〇
〇〇 ※ ※ ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇 ※ 〇〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇
〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ ※
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇〇
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ ※ 〇
※ 〇 ※ ※ 〇〇 ※ 〇〇 ※ 〇〇〇 ※ 〇
〇〇 ※ ※ ※ 〇〇 ※ 〇〇 ※ ※ 〇〇〇
〇 ※ 〇〇〇 ※ 〇 ※ ※ 〇〇〇 ※ ※ ※
〇〇〇 ※ 〇〇〇 ※ ※ ※ ※ 〇〇〇〇
1232943
n=16: 159
〇 ※ 〇〇〇〇 ※ 〇〇〇〇〇 ※ 〇〇〇
〇 ※ 〇 ※ ※ 〇〇〇 ※ ※ ※ 〇〇〇 ※ 〇
〇 ※ 〇〇〇 ※ ※ ※ 〇〇〇 ※ ※ ※ 〇〇
〇〇 ※ ※ 〇〇〇 ※ 〇 ※ 〇〇〇 ※ 〇 ※
※ 〇〇〇 ※ ※ 〇 ※ 〇〇 ※ ※ 〇 ※ 〇〇
※ ※ ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ ※
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇〇
※ 〇 ※ ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ ※ 〇
〇〇 ※ ※ ※ 〇〇 ※ 〇〇 ※ 〇〇〇 ※ 〇
〇 ※ 〇〇〇 ※ 〇〇 ※ 〇〇 ※ ※ 〇 ※ 〇
〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ 〇 ※ 〇〇 ※ 〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇 ※ 〇 ※ 〇〇
〇〇 ※ 〇 ※ ※ 〇〇 ※ ※ ※ 〇〇 ※ 〇 ※
※ 〇〇〇 ※ ※ ※ 〇〇〇〇〇 ※ ※ 〇〇
3164525
n=17: 179
〇 ※ 〇〇〇〇〇〇 ※ 〇〇〇 ※ ※ 〇〇〇
〇〇〇 ※ ※ ※ ※ 〇 ※ 〇 ※ 〇〇 ※ 〇 ※ 〇
※ ※ ※ 〇〇〇 ※ 〇 ※ 〇〇 ※ 〇〇〇 ※ 〇
〇〇〇〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ ※ ※ 〇〇
〇 ※ ※ ※ ※ 〇〇 ※ 〇〇 ※ 〇〇〇 ※ 〇 ※
〇 ※ 〇〇〇 ※ 〇〇 ※ 〇〇 ※ ※ 〇 ※ 〇〇
〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇 ※ 〇
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇〇 ※ 〇
※ 〇 ※ ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ ※ 〇〇
〇〇 ※ ※ ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ ※ 〇 ※
〇 ※ 〇〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇
〇 ※ 〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇
〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇 ※ 〇
〇〇 ※ 〇〇 ※ 〇〇 ※ 〇〇 ※ 〇 ※ 〇〇〇
※ 〇〇 ※ 〇 ※ ※ 〇〇 ※ 〇 ※ 〇〇 ※ ※ ※
※ ※ 〇〇〇 ※ ※ ※ 〇〇〇 ※ ※ 〇〇〇〇
8139616

mathe 发表于 2022-9-17 09:24:33

尽量斜走，网格充分大时，理论上是否能够逼近$\frac34$而不是$\frac23$

KeyTo9_Fans 发表于 2022-9-17 21:59:21

如果要输出具体的路线，那插头DP就只能算到n=17了

如果只需要输出路线长度，不需要输出具体的路线，我还能往后多算2个（起终点在左上右下角）：

n=2: length=3, status=5
n=3: length=5, status=15
n=4: length=7, status=47
n=5: length=17, status=115
n=6: length=23, status=285
n=7: length=31, status=720
n=8: length=39, status=1821
n=9: length=51, status=4572
n=10: length=63, status=11458
n=11: length=75, status=28883
n=12: length=89, status=73410
n=13: length=105, status=187665
n=14: length=121, status=480863
n=15: length=139, status=1232943
n=16: length=159, status=3164525
n=17: length=179, status=8139616
n=18: length=201, status=20994447
n=19: length=225, status=54291504

如果把硬盘当内存用，我估计还能再往后多算2个

所以之前预估n=21有点过于乐观了，需要我付出更多的精力去达成这个目标

KeyTo9_Fans 发表于 2022-9-19 08:26:01

好家伙，这个数列已经在2020年被收录了：

http://oeis.org/A331968

我晚了2年才发现这个数列

KeyTo9_Fans 发表于 2022-9-19 10:33:29

从左上角走到右下角的最大长度，没有人发布过，我赶紧新建了一个数列：

https://oeis.org/A357234

读者看到这个数列之后，要求我展示程序。

我得借此地展示一下：

#include<cstdio>
#include<cstring>

const int p=62200001,q=9999;
struct e
{
unsigned __int64 k;
int l;
};
e a,b;
int n,h,i,j,k,t,br,bl,u,v;
unsigned __int64 x,w;

void ad(int d)
{
if(j>n-2)
{
if(br>1)return;
br=0;
}
if(d>1)
{
for(k=1;k<n+2;k++)
if(br>1)return;
k=a.l+1;
if(k>bl)
{
bl=k;
k=n*i+j;
}
return;
}
w=1,x=0;
for(k=1;k<n+2;k++,w*=5)
x+=w*br;
for(k=int(x%p);b.l;k++)
if(x==b.k)
{
if(a.l+d<=b.l)return;
break;
}
b.k=x;
u+=!b.l;
b.l=a.l+d;
}

int gp(int p)
{
if(br==3)
for(k=0;;p++)
{
if(br==3)k++;
if(br==4)
{
k--;
if(!k)return p;
}
}
if(br==4)
for(k=0;;p--)
{
if(br==4)k++;
if(br==3)
{
k--;
if(!k)return p;
}
}
return p;
}

void go(int s)
{
if(s==0)
{
ad(0);
if(!i&&!j||i>n-2&&j>n-2)
{
br=1;
br=2;
ad(1);
br=2;
br=1;
ad(1);
}
br=3;
br=4;
ad(1);
return;
}
if(s==25||s==6||s==31||s==7||s==32||s==8||s==33||s==9||s==34)
{
br=0;
br=0;
ad(0);
return;
}
if(s==50)
{
br=1;
ad(1);
br=2;
br=1;
ad(1);
return;
}
if(s==75||s==100)
{
br=1;
ad(1);
br=s/25;
br=1;
ad(1);
if(!i&&!j||i>n-2&&j>n-2)
{
br=2;
br=1;
br=1;
ad(1);
}
return;
}
if(s==11)
{
if(!i&&!j||i>n-2&&j>n-2)
{
br=1;
br=1;
ad(2);
}
br=1;
br=2;
ad(1);
br=2;
br=1;
ad(1);
return;
}
if(s==61)
{
br=1;
br=1;
ad(2);
return;
}
if(s==86||s==111)
{
br=2;
br=1;
br=1;
ad(1);
return;
}
if(s==16||s==21)
{
br=1;
ad(1);
br=1;
br=s/5;
ad(1);
if(!i&&!j||i>n-2&&j>n-2)
{
br=s/5;
br=1;
br=2;
br=1;
ad(1);
}
return;
}
if(s==66||s==71)
{
br=2;
br=1;
br=1;
ad(1);
return;
}
if(s==91||s==96||s==121)
{
if(s==91)br=3;
if(s==121)br=4;
br=1;
br=1;
ad(1);
return;
}
if(s==23)
{
br=1;
br=4;
ad(1);
if(!i&&!j||i>n-2&&j>n-2)
{
br=2;
br=1;
br=1;
ad(1);
}
return;
}
if(s==73||s==98||s==123)
{
br=s/25;
br=1;
br=1;
ad(1);
return;
}
}

int main()
{
for(n=2;n<20;n++)
{
memset(a,0,sizeof(a));
a.l=1;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
for(u=h=0;h<p;h++)
if(a.l)
{
x=a.k;
for(t=0,k=1;k<n+2;x/=5)
{
br=int(x%5);
if(br==2)t++;
}
go(br+br*5+br*25);
}
if(u>v)v=u;
printf("%d %d %c",i,j,13);
memcpy(a,b,sizeof(a));
memset(b,0,sizeof(b));
}
for(h=0;h<p;h++)
a.k*=5;
}
printf("n=%d: length=%d, status=%d\n",n,bl-1,v);
}
return 0;
}

KeyTo9_Fans 发表于 2022-9-21 14:21:47

再大就很难再穷举了。我们能否用局部调整法、启发式搜索、神经网络、模拟退火、蚁群、粒子群等智能优化算法，求出更大的n的可行解呢？

页: 1 2 [3] 4

数学研发论坛's Archiver