A39803. 拯救公主
题目描述
拯救公主
题目描述
多灾多难的公主又被大魔王抓走啦！国王派遣了第一勇士阿福去拯救她。
身为超级厉害的术士，同时也是阿福的好伙伴，你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图，上面标记了阿福和公主所在的位置，以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门，通过一个传送门可以瞬间转移到任意一个传送门，当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外，你还查探到公主所在的地方被设下了结界，需要集齐K种宝石才能打开。当然，你在地图上也标记出了不同宝石所在的位置。
你希望阿福能够带着公主早日凯旋。于是在阿福出发之前，你还需要为阿福计算出他最快救出公主的时间。
地图用一个R×C的字符矩阵来表示。字符S表示阿福所在的位置，字符E表示公主所在的位置，字符#表示不能踏入的禁区，字符$表示传送门，字符.表示该位置安全，数字字符0至4表示了宝石的类型。阿福每次可以从当前的位置走到他上下左右四个方向上的任意一个位置，但不能走出地图边界。阿福每走一步需要花费1个单位时间，从一个传送门到达另一个传送门不需要花费时间。当阿福走到宝石所在的位置时，就视为得到了该宝石，不需要花费额外时间。
输入
第一行是一个正整数T（1 <= T <= 10），表示一共有T组数据。
每一组数据的第一行包含了三个用空格分开的正整数R、C（2 <= R, C <= 200）和K，表示地图是一个R×C的矩阵，而阿福需要集齐K种宝石才能够打开拘禁公主的结界。
接下来的R行描述了地图的具体内容，每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。$的数量不超过10个。宝石的类型在数字0至4范围内，即不会超过5种宝石。
输出
对于每一组数据，输出阿福救出公主所花费的最少单位时间。若阿福无法救出公主，则输出“oop!”（只输出引号里面的内容，不输出引号）。每组数据的输出结果占一行。
样例输入
1
7 8 2
........
..S..#0.
.##..1..
.0#.....
...1#...
...##E..
...1....
样例输出
11
参考答案
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
int t;
char map[205][205];
bool diamond[5];
struct node{
int x, y;
int jewel,time;
node(int xx, int yy, int j, int t):x(xx),y(yy),jewel(j),time(t){}
};
bool operator<(const node&a, const node&b){
return a.time>b.time;
}
priority_queue<node> pq;
bool visited[205][205][20];
int dirx[4] = {0,0,1,-1};
int diry[4] = {-1,1,0,0};
vector<node>v;
bool judge(int x, int y){
if(map[x][y]!='#'&&map[x][y]!=0)
return true;
return false;
}
bool isjewel(int x, int y){
if(map[x][y]=='0'||map[x][y]=='1'||map[x][y]=='2'||map[x][y]=='3'||map[x][y]=='4')
return true;
return false;
}
bool finished(int n){
int temp = 0;
for(int i = 1; i <= 32; i*=2){
temp++;
if((i&n)==0&&diamond[temp-1]!=0)
return false;
}
return true;
}
int main(){
cin>>t;
while(t--){
int r, c, k;
cin>>r>>c>>k;
memset(map, 0, sizeof(map));
memset(visited,0,sizeof(visited));
memset(diamond,0,sizeof(diamond));
while(!pq.empty())pq.pop();
v.clear();
int i, j;
for(i = 1; i <= r; i++)
for(j = 1; j <= c; j++){
cin>>map[i][j];
if(map[i][j]=='S'){
pq.push(node(i,j,0,0));
visited[i][j][0] = true;
}
else if(map[i][j]=='$')
v.push_back(node(i,j,0,0));
else if(map[i][j]>='0'&&map[i][j]<='4'){
diamond[map[i][j]-'0'] = true;
}
}
int flag = 0;
while(!pq.empty()){
node no = pq.top();
pq.pop();
// cout<<no.x<<" "<<no.y<<" "<<no.jewel<<" "<<no.time<<":"<<endl;
if(map[no.x][no.y]=='E'&&finished(no.jewel)){
cout<<no.time<<endl;
flag = 1;
break;
}
for(i = 0; i < 4; i++){
int nx = no.x+dirx[i];
int ny = no.y+diry[i];
int nj = no.jewel;
if(isjewel(nx,ny)){
if((int(pow(2,map[nx][ny]-'0'))&no.jewel)==0){
nj+=pow(2, map[nx][ny]-'0');
}
}//位运算 加钻石
if(!visited[nx][ny][nj]&&judge(nx,ny)){
if(map[nx][ny]=='$'){
for(j = 0; j < v.size(); j++){
pq.push(node(v[j].x,v[j].y,nj,no.time+1));
visited[v[j].x][v[j].y][nj] = true;
// cout<<v[j].x<<" "<<v[j].y<<" "<<nj<<" "<<no.time+1<<endl;
}
}
else{
pq.push(node(nx,ny,nj,no.time+1));
visited[nx][ny][nj] = true;
// cout<<nx<<" "<<ny<<" "<<nj<<" "<<no.time+1<<endl;
}
}
}
// getchar();
}
if(!flag) cout<<"oop!"<<endl;
}
return 0;
}