求调：T：Spring

一个游戏的地图可以看作是一个 N 行 M 列的字符矩阵，矩阵的每个元素可能是 '.'，表示空地，玩家可以自由走到这一位置；或者是 '#'，表示障碍，玩家不能走到这一位置；或者是 '1'~'9'的数字，表示这一位置中有一只攻击力为相应数字的怪兽，玩家如果走到这一位置将损失相应数值的血量，如果血量小于等于 0，游戏就将以玩家失败结束；或者是字符 'S'，表示这一位置有神奇泉水，玩家走到这一位置血量将恢复为 10。游戏开始时，玩家处于第一行第一列，血量为 10，玩家每步可以走到上下左右相邻的格子，但不能走出地图，玩家目标是走到地图的第 N 行第 M 列，你的任务是判断玩家是否有可能达到这一目标。

注意，游戏允许玩家重复经过某个位置，而且如果重复经过的位置中有怪兽或泉水，那么每经过一次，相应的作用就会生效一次。

输入格式

从文件 spring.in 中读入数据。 输入有多组数据。输入的第一行是数据的组数 。 每组数据的第一行有两个整数 N 和 M，分别表示地图的行数和列数。接下来的 N 行，每行有 M 个字符，表示游戏的地图，每个字符是 '.', '#', '1'~'9'或者大写字母'S'。输入保证地图的第一行第一列和第 N 行第 M 列一定是 '.'。

输出格式

输出到文件 spring.out 中。 对于每组数据，如果玩家可能顺利到达目标，就输出possible，否则就输出impossible，每个输出占一行。

#include <cstdio>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
bool vis[25][25];
char g[25][25];
int n, m;
bool dfs(int x, int y, int s){
    memset(vis, false, sizeof(vis));
    if(x == n && y == m) return true;
    if(g[x][y] == '#') return false;
    if(g[x][y] >= '0' && g[x][y] <= '9'){
        s -= (g[x][y] - '0');
    }
    if(s <= 0) return false;
    if(vis[x][y]) return false;
    vis[x][y] = true;
    if(g[x][y] == 'S') s = 10;
    bool ans = false;
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 1 || nx > n || ny < 1 || ny > n || vis[x][y] || g[x][y] == '#') continue;
        ans |= dfs(nx, ny, s);
    }
    return ans;
}
int main(){
//    freopen("spring.in", "r", stdin);
//    freopen("spring.out", "w", stdout);
    int T;
    cin >> T;
    for(int i = 1; i <= T; i++){
        cin >> n >> m;
        for(int I = 1; I <= n; I++){
            for(int J = 1; J <= m; J++){
                cin >> g[I][J];
            }
        }
        if(dfs(1, 1, 10) == true) cout << "possible" << endl;
        else cout << "impossible" << endl;
    }
    return 0;
}