#D. 迷宫

    Type: Default 1000ms 256MiB

迷宫

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[丛雨]来到了一个迷宫,这个迷宫是一个 n×mn × m 的网格,第 iijj 列的格子会包含一个方向指示 d(i,j)d(i,j) 和一个权值 v(i,j)v(i,j) 。假设起点为格子 (sx,sy)(sx,sy)(即第 sxsx 行第 sysy 列的格子),一开始丛雨左脚踏入格子 (sx,sy)(sx,sy) ,分数加上 v(sx,sy)v(sx,sy) ,然后该格子的权值变为它的相反数 v(sx,sy)−v(sx,sy) 。之后有两种选择: (1)结束游戏,当前分数为最终分数。 (2)按照当前格子的方向指示走到下一个格子 (x,y)(x,y)。如果踏入当前格子的是左脚,则右脚踏入 (x,y)(x,y) ,并且分数减去 v(x,y)v(x,y) ;如果踏入当前格子的是右脚,则左脚踏入 (x,y)(x,y) ,分数加上 v(x,y)v(x,y) 。之后 v(x,y)v(x,y) 变为它的相反数 v(x,y)−v(x,y) 。然后继续做下一个选择。 注意,必须存在下一个格子才能选择 (2)(2) ,否则只能选择 (1)(1) 。 具体的下一个格子的定义如下: 格子的方向指示由^ v < >四个字符表示,假设当前格子为 (i,j)(i,j), 如果 d(i,j)=d(i,j)=^,则表示往上走,即下一个格子为 (i1,j)(i−1,j) ; 如果 d(i,j)=d(i,j)=v,则表示往下走,即下一个格子为 (i+1,j)(i+1,j) ; 如果 d(i,j)=d(i,j)=<,则表示往左走,即下一个格子为 (i,j1)(i,j−1) ; 如果 d(i,j)=d(i,j)=>,则表示往右走,即下一个格子为 (i,j+1)(i,j+1) ; 如果格子 (i,j)(i,j) 的下一个格子 (x,y)(x,y) 不满足 1xn1 \le x \le n1ym1 \le y \le m ,那么认为格子 (i,j)(i,j) 不存在下一个格子。 丛雨的初始分数为 00 ,她想知道,对于每个 (i,j)(i,j) (1in,1jm)(1 \le i \le n, 1 \le j \le m) 作为起点,她能得到的最高的最终分数是多少。由于她不想输出文件太大,假设对于每个 (i,j)(i,j) ,答案为 ans(i,j)ans(i,j) ,那么你只需要输出

$$(\sum_{i=1}^n \sum_{j=1}^m (ans(i,j)+B) C^{(i-1)m+j-1}) mod \ {2^{64}} $$

其中 B=1015B = 10^{15} , C=2×1015+21C = 2 \times 10^{15} + 21。如果以某个 (i,j)(i, j) 为起点,能得到比任意正整数大的最终分数,则令 ans(i,j)=Bans(i,j) = B

输入格式(maze.in)

第一行,两个正整数 nn , mm ,以空格相隔。 接下来 nn 行,第 ii 行是字符串 did_i ,其第 jj 个字符 d(i,j)d(i,j) 表示第 ii 行第 jj 列格子的方向指示。 接下来 nn 行,第 iimm 个整数 v(i,1),v(i,2),...,v(i,m)v(i,1), v(i,2), ..., v(i,m) ,以空格相隔,v(i,j)v(i,j) 表示第 ii 行第 jj 列格子的初始权值。

输出格式(maze.out)

输出一个整数,表示答案。

输入样例

3 3
><>
>vv
^<<
1 2 3
4 5 6
7 8 9

输出样例

3946712175731523781

样例解释

对应的答案为

1 2 3
7 5 6
8 8 17

数据范围

对于 10%10\% 的数据,满足 1n,m101 \le n, m \le 10 。 对于 40%40\% 的数据,满足 1n,m1001 \le n, m \le 100 。 对于 100%100\% 的数据,满足 1n,m1000,v(i,j)1091 \le n, m \le 1000, |v(i,j)| \le 10^9 。 注意:由于答案可能较大,对于C/C++语言,你可能需要使用 long long数据类型进行计算。在输出答案时,可能不需要实际的取模,只需要使用unsigned long long数据类型的自然溢出即可。

0724

Not Attended
Status
Done
Rule
IOI
Problem
4
Start at
2024-7-24 9:00
End at
2024-7-24 12:30
Duration
3.5 hour(s)
Host
Partic.
29