U505299 Spring & Maze

一个迷宫的地图可以看作是一个 $N$ 行 $M$ 列的字符矩阵，矩阵的每个元素可能是： 1. `.`，表示空地，玩家可以自由走到这一位置； 2. `#` ，表示障碍，玩家不能走到这一位置； 3. $1 - 9$ 的数字，表示这一位置中有一只攻击力为相应数字的怪兽，玩家如果走到这一位置将损失相应数值的血量，**如果血量小于等于 $0$，游戏就将以玩家失败结束**； 4. 字符 $S$，表示这一位置有神奇泉水，玩家走到这一位置血量将恢复为 $10$。 游戏开始时，玩家处于第一行第一列，血量为 $10$，玩家每步可以走到上下左右相邻的格子，但不能走出地图，玩家目标是走到地图的第 $N$ 行第 $M$ 列， 你的任务很简单，请判断玩家是否有可能达到这一目标。 注意，**游戏允许玩家重复经过某个位置**，而且如果重复经过的位置中有怪兽或泉水，那么每经过一次，相应的作用就会生效一次。

### 本题有多组数据。 输入的第一行是数据的组数 $T$。 每组数据的第一行有两个整数 $N$ 和 $M$，分别表示地图的行数和列数。 接下来的 $N$ 行，每行有 $M$ 个字符，表示游戏的地图，每个字符是 `.`, `#`, $1-9$ 的数字或者大写字母 $S$。输入保证地图的第一行第一列和第 $N$ 行第 $M$ 列一定是 `.`。

对于每组数据，如果玩家可能顺利到达目标，就输出 `possible`，否则就输出 `impossible`。 每个输出之间**要换行**。

### 评测约定 **本题采用捆绑测试**，其中： | | Subtask 1 | Subtask 2 | Total | | ----------- | ----------- | ----------- | ----------- | | **分值** | $100$ | $100$ | $100$ | | **评测方式** | 最小值 | 最小值 | 最小值 | | **测试点** | $1$ | $2,\ 3,\ 4$ | ALL | - **本题没有部分分**。只有你通过了所有测试点，才可以得到 $100$ 分，否则你将得到 $0$ 分。 ### 数据约定 对于 **Subtask 1**，保证 $ T \le 10 $。 对于 $100\%$ 的数据，保证 $T\le20$，$2 \le N, M \le 20$。 数据保证终点处的字符为 `.` 或 $S$。