#P18508. Snake Move
Snake Move
Snake Move
Putata 正在玩贪吃蛇游戏,地图是一个 的网格,其中某些格子有障碍。蛇的身体依次位于
是蛇的长度,第一节是头,最后一节是尾。相邻两节位于共边相邻格子。
可以使用以下五种命令,每个命令算一次操作:
L:头向左移动一格,变为 ;R:头向右移动一格,变为 ;U:头向上移动一格,变为 ;D:头向下移动一格,变为 ;S:把蛇缩短一节,删去当前尾部,长度由 变为 。长度已经为一时不能使用此命令。
头移动时,其他身体部分同时跟随移动:移动后第 节()占据移动前第 节的位置。蛇不能进入障碍格,不能离开地图,也不能与自己碰撞,即每次命令结束后所有身体位置必须两两不同。
特别地,头可以移动到当前尾巴所在的格子,因为头进入的同时尾部正好移走。长度为二时,允许用一次移动命令交换头和尾的位置。
给定地图和蛇的初始身体。令 表示让蛇头到达格子 所需的最少操作次数;无法到达时定义为零。请计算
$$\left(\sum_{i=1}^n\sum_{j=1}^m f(i,j)^2\right)\bmod 2^{64}.$$蛇头初始所在格子的最少操作次数为零。
输入格式
第一行包含三个整数 (,)。
接下来 行,第 行包含 (,),按从头到尾的顺序给出身体位置。保证所有位置两两不同,且对于 ,有 。保证身体全部位于无障碍格中。
接下来 行,每行一个长度为 的字符串。第 行第 个字符为 . 时格子 为空,为 # 时该格子有障碍。
输出格式
输出一行,一个整数,表示上述取模后的答案。
完整原样例 1
4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....
293
完整原样例 2
2 2 4
1 1
1 2
2 2
2 1
..
..
14
完整原样例 3
5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....
407