3670: 迷宫(第四轮04)
题目描述
迷宫是一个n × m的网格，第i第j列的格子会包含一个方向指示di,j和一个权值vi,j。假设起点为格子(sx, sy)（即第sx行第sy列的格子），一开始牛妹左脚踏入格子 (sx, sy)，分数加上vsx,sy ，然后该格子的权值变为它的相反数−vsx,sy。
之后有两种选择:
(1) 结束游戏，当前分数为最终分数。
(2) 按照当前格子的方向指示走到下一个格子(x, y)。如果踏入当前格子的是左脚， 则右脚踏入(x, y)，并且分数减去 vx,y；如果踏入当前格子的是右脚，则左脚踏入(x, y)，分数加上 vx,y。之后vx,y变为它的相反数−vx,y。然后继续做下一个选择。注意，必须存在下一个格子才能选择(2)，否则只能选择(1)。具体的下一个格子的定义如下：
格子的方向指示由 `^v<>` 四个字符表示，假设当前格子为(i, j)， 如果di,j= '^'，则表示往上走，即下一个格子为(i − 1, j)；
如果di,j= 'v'，则表示往下走，即下一个格子为 (i + 1, j)； 如果di,j= '<'，则表示往左走，即下一个格子为(i, j − 1)； 如果di,j= '>'，则表示往右走，即下一个格子为 (i, j + 1)；
如果格子(i, j)的下一个格子(x, y)不满足1 ≤ x ≤ n且1 ≤ y ≤ m，那么认为格子
(i, j)不存在下一个格子。
牛妹的初始分数为 0，她想知道，对于每个(i, j) (1 ≤ i ≤ n, 1 ≤ j ≤ m)作为起点， 她能得到的最高的最终分数是多少。由于她不想输出文件太大，假设答案为
如果以(i, j)为起点，能得到比任意正整数大的最终分数，则令 ansi,j = B。
输入
第一行，两个正整数n, m，以空格相隔。
接下来n行，第i 行是字符串di，其第j个字符（从 1 开始）di,j表示第i行第j列格子的方向指示。
接下来n行，第i行m个整数 vi,1, vi,2, . . . , vi,m ，以空格相隔，vi,j表示第i行第j列格子的初始权值。
输出
输出一个整数，表示答案。
样例输入 复制
3 3
><>
>vv
^<< 1 2 3
4 5 6
7 8 9样例输出 复制
3946712175731523781提示
【样例 1 说明】
对应的答案为
1 2 3
7 5 6
8 8 17
【数据范围】
对于 10数据，满足1 ≤ n, m ≤ 10。对于 40数据，满足1 ≤ n, m ≤ 100。
对于 100数据，满足1 ≤ n, m ≤ 1000。
di,j= ^ 或 v 或 < 或 >, −1e9 ≤ vi,j ≤ 1e9, ∀1 ≤ i ≤ n, 1 ≤ j ≤ m。
注意：由于答案可能较大，对于 C/C++语言，你可能需要使用 `long long` 数据类型进行计算。在输出答案时，可能不需要实际的取模，只需要使用 `unsigned long long` 数据类型的自然溢出即可。