1 #include <cstdio>

  2 #include <queue>

  3 #include <set>

  4 #include <cstring>

  5 #include <string>

  6 #define N 205

  7 using namespace std;

  8 int r, c, k;

  9 char mp[N][N];            //地图位置

 10 int tag[N][N];            //标志位，判断是否重复走

 11 int door[N*N][2] = {};    //传送门位置

 12 int door_cnt = 0;        //有多少道传送门

 13 int sx, sy, ex, ey;        //起点和终点

 14 int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};    //方向

 15 typedef struct Node{    //每一个状态的结构体

 16     int x, y, step;        //位置和步数

 17     //set<int> s;        //开始是使用set保存宝石种类，发现0 > -1 为假，遂改为复杂形态

 18     int ecnt;            //宝石数量

 19     bool e[5] = {};        //5种宝石是否被发现

 20     Node(int x, int y, int step, int ecnt):x(x), y(y), step(step), ecnt(ecnt){};    //构造函数

 21 }node;

 22

 23 bool judge(node nx){    //判断是否往下走

 24     if(nx.x >= 0 && nx.x < r && nx.y >= 0 && nx.y < c && mp[nx.x][nx.y] != '#' &&

 25         nx.ecnt > tag[nx.x][nx.y]){

 26         return true;

 27     }

 28     return false;

 29 }

 30 int bfs(){

 31     node cur(sx, sy, 0, 0), next(sx, sy, 0, 0);    //当前状态和下一下状态

 32     queue<node> q;        //队列

 33     q.push(cur);

 34     while(!q.empty()){

 35         cur = q.front();

 36         q.pop();

 37         if(cur.x == ex && cur.y == ey && cur.ecnt >= k){    //满足结束条件，返回

 38             //printf("%d ", cur.s.size());

 39             return cur.step;

 40         }

 41         //printf("%d %d %d %d\n", cur.x, cur.y, cur.ecnt, cur.step);

 42         //getchar();

 43         for(int i = 0; i < 4; i++){        //上下左右试探

 44             next.x = cur.x + dir[i][0];

 45             next.y = cur.y + dir[i][1];

 46             next.step = cur.step + 1;

 47             next.ecnt = cur.ecnt;

 48             memcpy(next.e, cur.e, 5);    //计算下一步的所有数据

 49             //printf("tag:%d %d %d\n", next.ecnt > tag[next.x][next.y], next.ecnt, tag[next.x][next.y]);

 50             if(judge(next)){    //判断是否可以继续往下走

 51                 tag[next.x][next.y] = next.ecnt;

 52                 if(isdigit(mp[next.x][next.y])){    //是否是宝石

 53                     int e_cnt = 0;

 54                     next.e[mp[next.x][next.y]-48] = true;

 55                     for(int j = 0; j < 5; j++){

 56                         if(next.e[j]){

 57                             e_cnt++;

 58                         }

 59                     }

 60                     next.ecnt = e_cnt;

 61                     q.push(next);

 62                 }else if(mp[next.x][next.y] == '$'){ //是否是传送门

 63                     for(int j = 0; j < door_cnt; j++){

 64                         next.x = door[j][0];

 65                         next.y = door[j][1];

 66                         q.push(next);

 67                     }

 68                 }else if(mp[next.x][next.y] == 'E' || mp[next.x][next.y] == '.'){//正常道路

 69                     q.push(next);

 70                 }

 71             }

 72         }

 73     }

 74     return -1;

 75 }

 76 int main(){

 77     int t;

 78     scanf("%d", &t);

 79     while(t--){

 80         memset(tag, -1, sizeof(tag));    //初始化标志位

 81         memset(mp, 0, sizeof(mp));        //初始化地图

 82         door_cnt = 0;                    //传送门初始化

 83         scanf("%d %d %d", &r, &c, &k);    //地图大小和需要的宝石种类

 84         getchar();

 85         for(int i = 0; i < r; i++){        //记录初始位置，结束位置和所有传送门

 86             scanf("%s", mp[i]);

 87             for(int j = 0; j < c; j++){

 88                 switch(mp[i][j]){

 89                     case 'S':

 90                         sx = i;

 91                         sy = j;

 92                         break;

 93                     case 'E':

 94                         ex = i;

 95                         ey = j;

 96                         break;

 97                     case '$':

 98                         door[door_cnt][0] = i;

 99                         door[door_cnt][1] = j;

100                         door_cnt++;

101                         break;

102                 }

103             }

104         }

105         int cnt = bfs();            // bfs暴搜

106         if(cnt == -1){

107             printf("oop!");

108         }else{

109             printf("%d\n", cnt);

110         }

111     }

112     return 0;

113 }