NC23761. 地图优化
描述
给你一张n*m的地图，给一个格点都有一个下一步的指示，右下角的格子是‘End’，你从左上角出发，每次按照指令移动，直到走到右下角。如下图所示。
2E表示向右移动2格，2S表示向下移动2格……
现在，你有一次改变某一个格子的指令的机会，修改后，到达右下角的过程中接收到的指令会有不同。如上图所示，分别接收到6、3、2个指令，我们的目的是使接收到的指令数目最少。
输入描述
本题包含多组数据
第一行两个正整数n、m，分别表示行的数目和列的数目。（n，m<=100）。第二行有nm-1个字符串，按照从上到下，从左到右的顺序描述了地图。格式是rD，r表示表示要移动的数目，D表示移动的方向，是‘N’，‘S’，‘E’或‘W’当中的一个。每一个地图至少包含两个单位，输入文件结束标志是2个0
输出描述
对每个地图，输出下列3中情况中的一种：
如果不修改都无法到达目的地（右下角的格子），输出“impossible”。
如果存在一条路径，但是无法通过一次修改使得接收指令数目更少，输出none l，l表示接收的指令数目。
否则，输出修改的行和列，注意，最上方的行的标号是0，最左边的列的标号也是0。接下来是修改后的新的指令，和总共接收指令的数目。
如果有2种最优的修改方式，输出行标号最小的，如果还有2种或以上最优的，输入列标号最小的，如果还有多种，按照下列优先顺序输出：1E、1N、1S、1W、2E……
示例1
输入:
3 3 2E 2S 1S 1S 1N 1W 2N 1E 2 4 1E 1W 1W 1W 1W 1W 1W 1 4 3E 1E 1E 0 0
输出:
Case 1: 0 2 2S 2 Case 2: impossible Case 3: none 1