钉子人 - 题目

在使用 Google 街景时，你可能曾经拖拽过小黄人（Pegman）。今天，一个淘气的用户要把小黄人放在一个 $R$ 行 $C$ 列的矩形网格的某个单元格中。网格中的每个单元格可能是空白的，也可能标有一个指向四个方向（上、右、下、左）之一的箭头。

当小黄人被放置在一个网格单元格上时，如果该单元格是空白的，小黄人就会永远站在原地不动。然而，如果该单元格有一个箭头，小黄人就会开始向那个方向走。在他行走的过程中，每当遇到一个空白单元格，他会保持当前方向继续行走；但每当遇到另一个箭头时，他会转向该箭头所指的方向，然后继续行走。

你知道，小黄人可能会在网格中快乐地走来走去，永远不会停下，但也可能走出网格的边界！你可以通过改变一个或多个箭头的方向来防止这种情况并拯救他。（每个箭头的方向只能改变为其他三个可能方向中的一个；箭头只能被改变，不能被添加或移除。）

为了确保无论小黄人最初被放置在网格的哪个位置，他都不会走出网格边界，你需要改变的最少箭头数量是多少？

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个空格分隔的整数 $R$ 和 $C$。接下来的 $R$ 行，每行包含 $C$ 个字符，描述网格单元格，字符含义如下：

. period = 无箭头

^ caret = 向上箭头

> greater than = 向右箭头

v lowercase v = 向下箭头

< less than = 向左箭头

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是为了确保小黄人无论初始位置在哪里都不会离开网格而必须改变的最少箭头数量；如果无论如何改变箭头都无法确保这一点，则输出 IMPOSSIBLE。

$1 \le T \le 100$。

$1 \le R, C \le 4$。

$1 \le R, C \le 100$。

4
2 1
^
^
2 2
>v
^<
3 3
...
.^.
...
1 1
.

Case #1: 1
Case #2: 0
Case #3: IMPOSSIBLE
Case #4: 0

在 Case #1 中，无论小黄人被放在哪里，他都注定会从网格的上边缘走出去。你可以通过将最上面的箭头改为指向下方来防止这种情况，这将使他在两个箭头之间来回走动，永远不会离开。

在 Case #2 中，无论小黄人被放在哪里，他都会在棋盘上顺时针绕圈行走。不需要改变任何箭头。

在 Case #3 中，淘气的用户可能会把小黄人放在网格中间的向上箭头处，在这种情况下，他会开始行走并从网格的上边缘走出去。改变这个箭头的方向没有用：这只会让他从另一个边缘走出去。

在 Case #4 中，唯一可能的起始单元格是空白的，所以小黄人会永远站在原地，没有危险。

QOJ.ac