一个4*4的棋盘如下图，在这个棋盘上可以沿上下左右四个方向行动。起初一只蚂蚁在6的位置，而终点在11的位置。请问蚂蚁从起点到终点共有多少个不同的路径？注意，在同一个路径里，不可以访问同一个格点超过1次（也就是不可以出现6->7->8->7->11这种路径）。

+----+----+----+----+

|  1  |  2   |  3  |  4 |

+----+----+----+----+

|  5  |  6   |  7  |  8 |

+----+----+----+----+

|  9  | 10  | 11 | 12 |

+----+----+----+----+

| 13  | 14 | 15 | 16 |

+----+----+----+----+

除了深度优先搜索没想到什么更好的方法。。

mayuqiang (mayuqiang) 在 ta 的帖子中提到：

一个4*4的棋盘如下图，在这个棋盘上可以沿上下左右四个方向行动。起初一只蚂蚁在6的位置，而终点在11的位置。请问蚂蚁从起点到终点共有多少个不同的路径？注意，在同一个路径里，不可以访问同一个格点超过1次（也就是不可以出现6->7->8->7->11这种路径）。

+----+----+----+----+

|  1  |  2   |  3  |  4 |

……

46

mayuqiang (mayuqiang) 在 ta 的帖子中提到：

一个4*4的棋盘如下图，在这个棋盘上可以沿上下左右四个方向行动。起初一只蚂蚁在6的位置，而终点在11的位置。请问蚂蚁从起点到终点共有多少个不同的路径？注意，在同一个路径里，不可以访问同一个格点超过1次（也就是不可以出现6->7->8->7->11这种路径）。

+----+----+----+----+

|  1  |  2   |  3  |  4 |

……

动态规划？

mayuqiang (mayuqiang) 在 ta 的帖子中提到：

一个4*4的棋盘如下图，在这个棋盘上可以沿上下左右四个方向行动。起初一只蚂蚁在6的位置，而终点在11的位置。请问蚂蚁从起点到终点共有多少个不同的路径？注意，在同一个路径里，不可以访问同一个格点超过1次（也就是不可以出现6->7->8->7->11这种路径）。

+----+----+----+----+

|  1  |  2   |  3  |  4 |

……

简单的动态规划，我初中的时候确实会，现在确实不会了

mayuqiang (mayuqiang) 在 ta 的帖子中提到：

一个4*4的棋盘如下图，在这个棋盘上可以沿上下左右四个方向行动。起初一只蚂蚁在6的位置，而终点在11的位置。请问蚂蚁从起点到终点共有多少个不同的路径？注意，在同一个路径里，不可以访问同一个格点超过1次（也就是不可以出现6->7->8->7->11这种路径）。

+----+----+----+----+

|  1  |  2   |  3  |  4 |

……

不简单，而且只能做到3^短边长度这种级别，仍然是指数级，即便如此也已经极其繁琐。简单点就得是2^总格点数这种级别了

loasa (鲁鱼亥豕) 在 ta 的帖子中提到：

简单的动态规划，我初中的时候确实会，现在确实不会了

82

[6, 2, 3, 7, 11]

[6, 2, 3, 7, 8, 12, 16, 15, 11]

[6, 2, 3, 7, 8, 12, 16, 15, 14, 10, 11]

[6, 2, 3, 7, 8, 12, 16, 15, 14, 13, 9, 10, 11]

[6, 2, 3, 7, 8, 12, 11]

[6, 2, 3, 4, 8, 12, 16, 15, 11]

[6, 2, 3, 4, 8, 12, 16, 15, 14, 10, 11]

[6, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 10, 11]

[6, 2, 3, 4, 8, 12, 11]

[6, 2, 3, 4, 8, 7, 11]

[6, 2, 1, 5, 9, 13, 14, 10, 11]

[6, 2, 1, 5, 9, 13, 14, 15, 11]

[6, 2, 1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 7, 11]

[6, 2, 1, 5, 9, 13, 14, 15, 16, 12, 8, 7, 11]

[6, 2, 1, 5, 9, 13, 14, 15, 16, 12, 11]

[6, 2, 1, 5, 9, 10, 14, 15, 11]

[6, 2, 1, 5, 9, 10, 14, 15, 16, 12, 8, 4, 3, 7, 11]

[6, 2, 1, 5, 9, 10, 14, 15, 16, 12, 8, 7, 11]

[6, 2, 1, 5, 9, 10, 14, 15, 16, 12, 11]

[6, 2, 1, 5, 9, 10, 11]

[6, 10, 14, 15, 11]

[6, 10, 14, 15, 16, 12, 8, 4, 3, 7, 11]

[6, 10, 14, 15, 16, 12, 8, 7, 11]

[6, 10, 14, 15, 16, 12, 11]

[6, 10, 14, 13, 9, 5, 1, 2, 3, 7, 11]

[6, 10, 14, 13, 9, 5, 1, 2, 3, 7, 8, 12, 16, 15, 11]

[6, 10, 14, 13, 9, 5, 1, 2, 3, 7, 8, 12, 11]

[6, 10, 14, 13, 9, 5, 1, 2, 3, 4, 8, 12, 16, 15, 11]

[6, 10, 14, 13, 9, 5, 1, 2, 3, 4, 8, 12, 11]

[6, 10, 14, 13, 9, 5, 1, 2, 3, 4, 8, 7, 11]

[6, 10, 11]

[6, 10, 9, 5, 1, 2, 3, 7, 11]

[6, 10, 9, 5, 1, 2, 3, 7, 8, 12, 16, 15, 11]

[6, 10, 9, 5, 1, 2, 3, 7, 8, 12, 11]

[6, 10, 9, 5, 1, 2, 3, 4, 8, 12, 16, 15, 11]

[6, 10, 9, 5, 1, 2, 3, 4, 8, 12, 11]

[6, 10, 9, 5, 1, 2, 3, 4, 8, 7, 11]

[6, 10, 9, 13, 14, 15, 11]

[6, 10, 9, 13, 14, 15, 16, 12, 8, 4, 3, 7, 11]

[6, 10, 9, 13, 14, 15, 16, 12, 8, 7, 11]

[6, 10, 9, 13, 14, 15, 16, 12, 11]

[6, 7, 3, 4, 8, 12, 16, 15, 11]

[6, 7, 3, 4, 8, 12, 16, 15, 14, 10, 11]

[6, 7, 3, 4, 8, 12, 16, 15, 14, 13, 9, 10, 11]

[6, 7, 3, 4, 8, 12, 11]

[6, 7, 3, 2, 1, 5, 9, 13, 14, 10, 11]

[6, 7, 3, 2, 1, 5, 9, 13, 14, 15, 11]

[6, 7, 3, 2, 1, 5, 9, 13, 14, 15, 16, 12, 11]

[6, 7, 3, 2, 1, 5, 9, 10, 14, 15, 11]

[6, 7, 3, 2, 1, 5, 9, 10, 14, 15, 16, 12, 11]

[6, 7, 3, 2, 1, 5, 9, 10, 11]

[6, 7, 11]

[6, 7, 8, 4, 3, 2, 1, 5, 9, 13, 14, 10, 11]

[6, 7, 8, 4, 3, 2, 1, 5, 9, 13, 14, 15, 11]

[6, 7, 8, 4, 3, 2, 1, 5, 9, 13, 14, 15, 16, 12, 11]

[6, 7, 8, 4, 3, 2, 1, 5, 9, 10, 14, 15, 11]

[6, 7, 8, 4, 3, 2, 1, 5, 9, 10, 14, 15, 16, 12, 11]

[6, 7, 8, 4, 3, 2, 1, 5, 9, 10, 11]

[6, 7, 8, 12, 16, 15, 11]

[6, 7, 8, 12, 16, 15, 14, 10, 11]

[6, 7, 8, 12, 16, 15, 14, 13, 9, 10, 11]

[6, 7, 8, 12, 11]

[6, 5, 1, 2, 3, 7, 11]

[6, 5, 1, 2, 3, 7, 8, 12, 16, 15, 11]

[6, 5, 1, 2, 3, 7, 8, 12, 16, 15, 14, 10, 11]

[6, 5, 1, 2, 3, 7, 8, 12, 16, 15, 14, 13, 9, 10, 11]

[6, 5, 1, 2, 3, 7, 8, 12, 11]

[6, 5, 1, 2, 3, 4, 8, 12, 16, 15, 11]

[6, 5, 1, 2, 3, 4, 8, 12, 16, 15, 14, 10, 11]

[6, 5, 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 10, 11]

[6, 5, 1, 2, 3, 4, 8, 12, 11]

[6, 5, 1, 2, 3, 4, 8, 7, 11]

[6, 5, 9, 13, 14, 10, 11]

[6, 5, 9, 13, 14, 15, 11]

[6, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 7, 11]

[6, 5, 9, 13, 14, 15, 16, 12, 8, 7, 11]

[6, 5, 9, 13, 14, 15, 16, 12, 11]

[6, 5, 9, 10, 14, 15, 11]

[6, 5, 9, 10, 14, 15, 16, 12, 8, 4, 3, 7, 11]

[6, 5, 9, 10, 14, 15, 16, 12, 8, 7, 11]

[6, 5, 9, 10, 14, 15, 16, 12, 11]

[6, 5, 9, 10, 11]

mayuqiang (mayuqiang) 在 ta 的帖子中提到：

一个4*4的棋盘如下图，在这个棋盘上可以沿上下左右四个方向行动。起初一只蚂蚁在6的位置，而终点在11的位置。请问蚂蚁从起点到终点共有多少个不同的路径？注意，在同一个路径里，不可以访问同一个格点超过1次（也就是不可以出现6->7->8->7->11这种路径）。

+----+----+----+----+

|  1  |  2   |  3  |  4 |

……

大学牲可能当做算法题做，初中生的解法能说明下不

mayuqiang (mayuqiang) 在 ta 的帖子中提到：

一个4*4的棋盘如下图，在这个棋盘上可以沿上下左右四个方向行动。起初一只蚂蚁在6的位置，而终点在11的位置。请问蚂蚁从起点到终点共有多少个不同的路径？注意，在同一个路径里，不可以访问同一个格点超过1次（也就是不可以出现6->7->8->7->11这种路径）。

+----+----+----+----+

|  1  |  2   |  3  |  4 |

……

同好奇，初中生有啥更快的做法么？

Fighttodeath (superb11) 在 ta 的帖子中提到：

大学牲可能当做算法题做，初中生的解法能说明下不

用bfs或者dfs的方法太暴力啦，我说一下初中生都能理解的方法吧

只考虑右上角的矩阵，即

1 2  3   4

   6  7   8

     11 12

          16

显然，只在这半边矩阵里面从6到达11的走法共7种

而从6到1的走法有3种，从6到16的走法有4种

如果只经过一次1或者16，总计有3*4+3*4+4*3+4*3=48种走法（考虑对称性）

如果不经过1或者16，则是7*2=14种走法

如果同时经过1和16，则6只能先到1再到16（先到16的话封住了路），分情况讨论：

1）6-7-8-4-3-2-1 ，则16那边只能是16-12-11

2）6-7-3-2-1 ，则16那边只能是16-12-11

3) 6-2-1,则16到11有3种走法

因此，上面共有5种，注意到1到16只有2种走法以及对称性，5*2*2=20种

因此总共有48+14+20=82种走法

Fighttodeath (superb11) 在 ta 的帖子中提到：

大学牲可能当做算法题做，初中生的解法能说明下不