這里需要注意的問題就是，移動到有寶石的位置荠卷，也需要時間模庐，只是拿寶石不花費時間。在輸入的時候油宜，遇到起始位置或者結束位置就記錄下來掂碱，并將其改為.，因為實際上在移動的過程當中慎冤，起始點和結束點也只是普通的點疼燥。
用了二進制壓縮的方法來存儲。也需要注意visit數(shù)組蚁堤，與一般的visit數(shù)組不同醉者，這里又多加了一個維度，用來存儲當前位置的寶石個數(shù)披诗。
另外湃交，應該把direction的循環(huán)放在內(nèi)層，這樣可以一定程度簡化問題藤巢。

#include<iostream>
#include<vector>
#include<map>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

int direction[4][2] = {{1,0}, {-1, 0}, {0,1},{0,-1}};
int r,c,k;
int sx, sy, ex, ey; // 開始的點和結束的點
// 如果visit數(shù)組只有兩維，有可能在遍歷的過程中寶石數(shù)目增加 而之前的visit如果已經(jīng)被設置為true 那么之后也不會再訪問到
bool visit[200][200][1<<5];  // 記錄特定的發(fā)現(xiàn)寶石狀態(tài)下息罗，特定位置的被訪問情況
char board[200][200];
vector<pair<int, int>> door; // 傳送門的位置

bool Check(int gem){
     int cnt = 0;
     for(int i = 0; i <= 4; i++){
          if(((gem >> i) & 1) == 1)
               cnt++;
     }
     return (cnt >=k);
}

bool Judge(int x, int y, int s){
     if(x < 0 || y < 0 || x >= r || y >= c || visit[x][y][s] || board[x][y] == '#')
          return false;
     return true;
}

struct Status{
     int step;  // 到當前這一步花費的時間
     int gem;  // 當前寶石的個數(shù)
     int x,y;  // 當前位置
     Status(int x,int y,int s,int g):x(x), y(y), step(s), gem(g){}
};

int main(){
     int T;
     cin>>T;
     while(T--){
          memset(visit, 0, sizeof(visit));
          memset(board, 0, sizeof(board));
          door.clear();  // 全局變量 這里要記得清空
          bool flag = 0;
          queue<Status> q;
          cin>>r>>c>>k;
          for(int i = 0; i < r; i++){
               for(int j =0; j < c; j++){
                    cin>>board[i][j];
                    if(board[i][j] == 'S'){
                         sx = i;
                         sy = j;
                         board[i][j] = '.';
                    }
                    if(board[i][j] == 'E'){
                         ex = i;
                         ey = j;
                         board[i][j] = '.';
                    }
                    if(board[i][j] == '$'){
                         door.push_back(pair<int, int>(i,j));
                    }
               }
          }
          q.push(Status(sx,sy,0,0));  // 初始狀態(tài)
          visit[sx][sy][0] = true;
          while(!q.empty()&&!flag){
               Status cur = q.front();
               q.pop();
               if(Check(cur.gem) && cur.x == ex && cur.y == ey){
                    cout<<cur.step<<endl;
                    flag= 1;
                    break;
               }
               // visit[cur.x][cur.y] = true;
               // 擴展四個方向
               if(board[cur.x][cur.y] == '.'){
                    for(int i = 0; i < 4; i++){
                         int nx = cur.x+direction[i][0];
                         int ny = cur.y+direction[i][1];
                         if(!Judge(nx, ny, cur.gem))
                            continue;
                         visit[nx][ny][cur.gem] = true;
                         q.push(Status(nx,ny, cur.step+1, cur.gem));
                    }
               }

               if(board[cur.x][cur.y] == '$'){
                    for(int j = 0; j < door.size(); j++){
                         // 把所有傳送門周圍的坐標放入隊列
                         int fir = door[j].first;
                         int sec = door[j].second;
                         for(int i = 0; i < 4; i++){
                              int nx = fir+direction[i][0];
                              int ny = sec+direction[i][1];
                              if(!Judge(nx, ny, cur.gem))
                                 continue;
                              visit[nx][ny][cur.gem] = true;
                              q.push(Status(nx,ny, cur.step+1, cur.gem));
                         }
                    }
               }
               
               if(board[cur.x][cur.y] <= '4' && board[cur.x][cur.y] >= '0' ){
                    int cur_gem_cnt = cur.gem | (1 << (board[cur.x][cur.y]-'0'));
                    
                    for(int i = 0; i < 4; i++){
                         int nx = cur.x+direction[i][0];
                         int ny = cur.y+direction[i][1];
                         if(!Judge(nx, ny, cur_gem_cnt))
                              continue;
                         visit[nx][ny][cur_gem_cnt] = true;
                         q.push(Status(nx, ny, cur.step+1, cur_gem_cnt));
                    }
               }
               
          }
          if(!flag)
               cout<<"oop!"<<endl;
          
     }
     
     
     return 0;

}