CF382D Ksenia and Pawns

Ksenia 有一个大小为 $n \times m$ 的国际象棋棋盘。棋盘的每个格子上都包含以下字符之一：“”、“^”、“v”、“\#”。包含字符“\#”的格子为阻塞格子。所有触及棋盘边界的格子都是阻塞格子。 Ksenia 在这个棋盘上玩两个卒子的游戏。一开始，她将在棋盘上放置这两个卒子。只有阻塞格（含“\#”）允许两个卒子站在同一个格子里，在其它情况下，两个卒子不能站在同一个格子。游戏在卒子被放置到棋盘上后开始。每个回合，Ksenia 会按照当前卒子所在格子的箭头方向，将每个卒子移动到相邻的格子（如果卒子在“\#”格上，则不移动）。假设 Ksenia 是同时移动两个卒子的（见第二个样例）。 当然，Ksenia 玩游戏是为了得分。怎么计算每局的得分呢？很简单！统计第一个卒子走过的步数，以及第二个卒子走过的步数，将这两个数字相加，就是该局比赛的得分。 Ksenia 想知道：她最多能获得多少分（也就是说，要求她在一开始最优地放置卒子）。请你帮她计算最大得分。

第一行包含两个整数 $n$ 和 $m$，$1\leq n, m\leq 2000$，表示棋盘的大小。接下来的 $n$ 行，每行包含 $m$ 个字符，描述棋盘的布局。每个字符都是以下之一：“”、“^”、“v”、“\#”。 保证表格的边界格子都是阻塞格子（字符为“\#”）。

如果 Ksenia 能获得无限多的分数，输出 $-1$。否则，输出她能获得的最大分数。

由 ChatGPT 5 翻译