POJ｜拯救公主 BFS

这里需要注意的问题就是，移动到有宝石的位置，也需要时间，只是拿宝石不花费时间。在输入的时候，遇到起始位置或者结束位置就记录下来，并将其改为.，因为实际上在移动的过程当中，起始点和结束点也只是普通的点。
用了二进制压缩的方法来存储。也需要注意visit数组，与一般的visit数组不同，这里又多加了一个维度，用来存储当前位置的宝石个数。
另外，应该把direction的循环放在内层，这样可以一定程度简化问题。

#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数组只有两维，有可能在遍历的过程中宝石数目增加 而之前的visit如果已经被设置为true 那么之后也不会再访问到
bool visit[200][200][1<<5];  // 记录特定的发现宝石状态下，特定位置的被访问情况
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;  // 当前宝石的个数
     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));  // 初始状态
          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;

}