#P18508. Snake Move

Snake Move

Snake Move

Putata 正在玩贪吃蛇游戏,地图是一个 n×mn\times m 的网格,其中某些格子有障碍。蛇的身体依次位于

(x1,y1),(x2,y2),…,(xk,yk).(x_1,y_1),(x_2,y_2),\ldots,(x_k,y_k).

kk 是蛇的长度,第一节是头,最后一节是尾。相邻两节位于共边相邻格子。

可以使用以下五种命令,每个命令算一次操作:

  • L:头向左移动一格,变为 (x1,y1−1)(x_1,y_1-1);
  • R:头向右移动一格,变为 (x1,y1+1)(x_1,y_1+1);
  • U:头向上移动一格,变为 (x1−1,y1)(x_1-1,y_1);
  • D:头向下移动一格,变为 (x1+1,y1)(x_1+1,y_1);
  • S:把蛇缩短一节,删去当前尾部,长度由 kk 变为 k−1k-1。长度已经为一时不能使用此命令。

头移动时,其他身体部分同时跟随移动:移动后第 ii 节(2≤i≤k2\le i\le k)占据移动前第 i−1i-1 节的位置。蛇不能进入障碍格,不能离开地图,也不能与自己碰撞,即每次命令结束后所有身体位置必须两两不同。

特别地,头可以移动到当前尾巴所在的格子,因为头进入的同时尾部正好移走。长度为二时,允许用一次移动命令交换头和尾的位置。

给定地图和蛇的初始身体。令 f(i,j)f(i,j) 表示让蛇头到达格子 (i,j)(i,j) 所需的最少操作次数;无法到达时定义为零。请计算

$$\left(\sum_{i=1}^n\sum_{j=1}^m f(i,j)^2\right)\bmod 2^{64}.$$

蛇头初始所在格子的最少操作次数为零。

输入格式

第一行包含三个整数 n,m,kn,m,k(1≤n,m≤30001\le n,m\le3000,1≤k≤min⁡{nm,105}1\le k\le\min\{nm,10^5\})。

接下来 kk 行,第 ii 行包含 xi,yix_i,y_i(1≤xi≤n1\le x_i\le n,1≤yi≤m1\le y_i\le m),按从头到尾的顺序给出身体位置。保证所有位置两两不同,且对于 1≤i<k1\le i<k,有 ∣xi−xi+1∣+∣yi−yi+1∣=1|x_i-x_{i+1}|+|y_i-y_{i+1}|=1。保证身体全部位于无障碍格中。

接下来 nn 行,每行一个长度为 mm 的字符串。第 ii 行第 jj 个字符为 . 时格子 (i,j)(i,j) 为空,为 # 时该格子有障碍。

输出格式

输出一行,一个整数,表示上述取模后的答案。

完整原样例 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