HBC233874[SCOI2005]骑士精神,深度优先搜索(DFS),启发式搜索(A*),搜索Turtles题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

一张nnn行mmm列的网格图，图中的有些格子上面有障碍物，但保证(1,1)(1,1)(1,1)和(n,m)(n,m)(n,m)上面都没有障碍物，在(1,1)(1,1)(1,1)处有两只乌龟，都想要去(n,m)(n,m)(n,m)，乌龟每次都可以向下或者向右走一格，前提是格子上没有任何障碍物，要求两只乌龟在前往(n,m)(n,m)(n,m)的路途中不可以相遇，即除了起点和终点，他们的路径没有其他公共点，求出从起点到终点的不同路径对数，答案对109+710^9+7109+7取模， 注：和被视为同一对路径。

一张nnn行mmm列的网格图，图中的有些格子上面有障碍物，但保证(1,1)(1,1)(1,1)和(n,m)(n,m)(n,m)上面都没有障碍物。在(1,1)(1,1)(1,1)处有两只乌龟，都想要去(n,m)(n,m)(n,m)。乌龟每次都可以向下或者向右走一格，前提是格子上没有任何障碍物。要求两只乌龟在前往(n,m)(n,m)(n,m)的路途中不可以相遇，即除了起点和终点，他们的路径没有其他公共点。求出从起点到终点的不同路径对数。答案对109+710^9+7109+7取模。 注：(routea,routeb)(route_a,route_b)(routea​,routeb​)和(routeb,routea)(route_b,route_a)(routeb​,routea​)被视为同一对路径。

标签： HBC233874[SCOI2005]骑士精神 深度优先搜索(DFS) 启发式搜索(A*) 搜索Turtles题解