OpenJudge Save Tang Monk(拯救唐僧)
目录
Save Tang Monk
时间与内存要求:
时间限制:1000ms
内存限制:65536kB
描述：
《Journey to the West》(also 《Monkey》) is one of the Four Great Classical Novels of Chinese literature. It was written by Wu Cheng'en during the Ming Dynasty. In this novel, Monkey King Sun Wukong, pig Zhu Bajie and Sha Wujing, escorted Tang Monk to India to get sacred Buddhism texts.
During the journey, Tang Monk was often captured by demons. Most of demons wanted to eat Tang Monk to achieve immortality, but some female demons just wanted to marry him because he was handsome. So, fighting demons and saving Monk Tang is the major job for Sun Wukong to do.
Once, Tang Monk was captured by the demon White Bones. White Bones lived in a palace and she cuffed Tang Monk in a room. Sun Wukong managed to get into the palace. But to rescue Tang Monk, Sun Wukong might need to get some keys and kill some snakes in his way.
The palace can be described as a matrix of characters. Each character stands for a room. In the matrix, 'K' represents the original position of Sun Wukong, 'T' represents the location of Tang Monk and 'S' stands for a room with a snake in it. Please note that there are only one 'K' and one 'T', and at most five snakes in the palace. And, '.' means a clear room as well '#' means a deadly room which Sun Wukong couldn't get in.
There may be some keys of different kinds scattered in the rooms, but there is at most one key in one room. There are at most 9 kinds of keys. A room with a key in it is represented by a digit(from '1' to '9'). For example, '1' means a room with a first kind key, '2' means a room with a second kind key, '3' means a room with a third kind key... etc. To save Tang Monk, Sun Wukong must get ALL kinds of keys(in other words, at least one key for each kind).
For each step, Sun Wukong could move to the adjacent rooms(except deadly rooms) in 4 directions(north,west,south and east), and each step took him one minute. If he entered a room in which a living snake stayed, he must kill the snake. Killing a snake also took one minute. If Sun Wukong entered a room where there is a key of kind N, Sun would get that key if and only if he had already got keys of kind 1,kind 2 ... and kind N-1. In other words, Sun Wukong must get a key of kind N before he could get a key of kind N+1 (N>=1). If Sun Wukong got all keys he needed and entered the room in which Tang Monk was cuffed, the rescue mission is completed. If Sun Wukong didn't get enough keys, he still could pass through Tang Monk's room. Since Sun Wukong was a impatient monkey, he wanted to save Tang Monk as quickly as possible. Please figure out the minimum time Sun Wukong needed to rescue Tang Monk.
输入 :
There are several test cases.
For each case, the first line includes two integers N and M(0 < N <= 100, 0 <= M <= 9), meaning that the palace is a N * N matrix and Sun Wukong needed M kinds of keys(kind 1, kind 2, ... kind M).
Then the N*N matrix follows.
The input ends with N = 0 and M = 0.
输出：
For each test case, print the minimum time (in minute) Sun Wokong needed to save Tang Monk. If it's impossible for Sun Wokong to complete the mission, print "impossible".
样例输入：
3 1
K.S
##1
1#T
3 1
K#T
.S#
1#.
3 2
K#T
.S.
21.
0 0样例输出：
5
impossible
8问题分析：
观察这个题目的样例输入，我们不难发现这是一个加强加难版的迷宫，其中出现了一些特殊位置，比如：钥匙位置和蛇位置。
我们先来解释一下题意，孙悟空要去救被白骨精关在宫殿中的唐僧，白骨精的宫殿由许多小房间组成，我们用一个矩阵来表示。矩阵中的‘K’位置就是悟空一开始所在的位置，‘T'位置是唐僧被关押的位置，也就是孙悟空的目的地。孙悟空的移动方向是上下左右四个方向，每次移动一格，花费1分钟。在宫殿中有这样的一些房间：‘ . '是正常的房间，直接通过即可；‘#’是致命房间，孙悟空不得通过；’S'是有蛇的房间，孙悟空想要通过就要杀掉这只蛇，而这一过程就要多花1分钟（蛇被杀死之后不会复活，也就是再次通过时只用花1分钟即可）；数字房间代表着这个房间里面有哪个钥匙。孙悟空想要拯救唐僧，就需要先按顺序集齐所有钥匙（每种各一个）。而我们所要计算的就是悟空最快需要多长时间来拯救唐僧，或者说悟空救不出唐僧（输出impossible）。
第一行输入的N(1~100)代表矩阵的大小，M(0~9)代表钥匙的数目，‘S’房间最多有5个。
对于这个题目，我们很自然地会想到用广度优先搜索来计算出最短时间，但我们会遇到这样一些问题：
1）传统的广度优先搜索需要构建一个数组来记录自己是否走过该节点，以避免自己重复走已经走过的路，而造成重复计算。但此题中悟空一定是需要走重复的路来获得所有的钥匙，进而拯救唐僧，但我们又不能对重复计算视而不见（比如在起点左右反复横跳），如何处理？
2）第一次遇到一个'S'房间时，悟空需要多花1分钟的时间，但是我们通常将广度优先搜索的层数记为经过的时间。如何处理这种时间不定的‘S'房间？
这两者是困惑我们的最主要的问题。而要处理这些问题，我们首先要处理好我们的输入。
一般输入的想法很简单，建立一个102*102的char的二维数组来存储矩阵。但实际上char二维数组并不好。因为对于悟空而言，他寻找的目标是有连续性的，从‘1’到‘M’，再寻找‘T’，而这个T就不像1～M具有数字上的连续性，所以我们不妨建一个int二维数组，将'T'的位置设置成M+1。(emplace_back类似于push_back，可以省掉构造函数)
while (scanf("%d %d", &N, &M) && (N != 0 || M != 0)) {//输入第一行
int S=20;
memset(Palace,-1,sizeof(Palace));//宫殿，也就是题中的矩阵
memset(KeyNum,0,sizeof(Target));//记录每种钥匙的数量、位置，以及唐僧的位置（vector数组）
cin.get();//读掉第一行的回车
for(int i=1;i<=N;i++) {
for (int j = 1; j <= N; j++) {
char c=cin.get();
switch(c){
case 'K':Palace[i][j]=0;Begin.x=i;Begin.y=j;Begin.CostTime=0;break;//记录一下起始位置
case 'T':Palace[i][j]=M+1;Final.x=i;Final.y=j;Target[M+1].emplace_back(i,j);break;//记录一下末尾位置
case '.':Palace[i][j]=-2;break;
case '#':Palace[i][j]=-1;break;//把不可通过的位置设置为-1
case 'S':Palace[i][j]=S++;break;//利用S记录蛇的数量，因为害怕和钥匙重复，所以从20开始
default:Palace[i][j]=c-'0';Target[c-'0'].emplace_back(i,j);break;//其余的就剩下钥匙房间了
}
if (j == N) { cin.get(); }//读掉每一行末尾的回车
}
}
}接下来我们考虑搜索的过程，我们需要一个表示当前状态State的结构体和只表示位置的结构体Position.
struct State{
int x{},y{};//坐标
int CostTime{};//花费的时间
int Expectation=0;//期望，暂时不用管，后面会讲
bitset<5> Snake;//利用bitset来存储走过的S房间的状态，如果利用int型和位运算也可以（状态压缩）
State(int a,int b):x(a),y(b),CostTime(0){}//构造函数
State()=default;
bool operator>(const State & a) const{//因为后面会用到priority_queue，所以写好比较符的重载
return Expectation>a.Expectation;
}
};
struct Position{
int x,y;
Position(int a,int b):x(a),y(b){}
bool operator==(const Position a) const{
return a.x==x&&y==a.y;
}
};
int N;int M;//矩阵大小和钥匙种类数
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int Palace[102][102]{};
bool visited[102][102]{};//是否走过
State Begin{};State Final{};//起点和终点
vector<Position> Target[11];//目标数量和位置接下来到了最重要的搜索算法：
我们利用两个优先队列来存储，第一个(Goal)用来放有钥匙的状态和终点状态，第二个(Search)用来进行当前已经获得的目标(NowKey)和下一个目标之间的查找。
void SaveTangMonk() {
priority_queue<State,vector<State>,greater<State>> Goal;
Goal.push(Begin);
while (!Goal.empty()) {
State NowKey = Goal.top();
if (Palace[NowKey.x][NowKey.y] == M + 1) break;//找到唐僧了
Goal.pop();//暂时没找到，删除队列中的节点
memset(visited, 0, sizeof(visited));
priority_queue<State, vector<State>, greater<State>> Search;
Search.push(NowKey);
int NumOfKey=0;
while (!Search.empty()) {
State NowSearch = Search.top();
Search.pop();
visited[NowSearch.x][NowSearch.y]=true;//只是为了保证起点的visited是true
if (Palace[NowSearch.x][NowSearch.y] == Palace[NowKey.x][NowKey.y] + 1) {//NowSearch找到了下一个目标
Goal.push(NowSearch);
NumOfKey++;//已经找到了多少钥匙
if (NumOfKey==Target[Palace[NowSearch.x][NowSearch.y]].size()) break;//如果已经找到了所有的钥匙，就直接结束查找
continue;
}
for (int i = 0; i < 4; i++) {//四个方向
if (Palace[NowSearch.x + dx[i]][NowSearch.y + dy[i]] != -1&&!visited[NowSearch.x+dx[i]][NowSearch.y+dy[i]]) {//没有走过
State NextSearch(NowSearch.x + dx[i], NowSearch.y + dy[i]);
NextSearch.Snake = NowSearch.Snake;//把上一个State的蛇的状态传给下一个State
if (Palace[NextSearch.x][NextSearch.y] >= 20 && !NextSearch.Snake[Palace[NextSearch.x][NextSearch.y] - 20]) {//大于等于20代表走到了‘S'房间，Palace[NextSearch.x][NextSearch.y] - 20就是蛇的序号
NextSearch.CostTime = NowSearch.CostTime + 2;
int MinDist = 99999;
for (auto &it : Target[Palace[NowKey.x][NowKey.y] + 1]) {
if(!visited[it.x][it.y])
MinDist = min(MinDist, abs(it.x - NextSearch.x)+abs(it.y - NextSearch.y));
}
NextSearch.Expectation = NextSearch.CostTime + MinDist;
NextSearch.Snake[Palace[NextSearch.x][NextSearch.y] - 20] = true;
} else {
NextSearch.CostTime = NowSearch.CostTime + 1;
int MinDist = 99999;
for (auto &it : Target[Palace[NowKey.x][NowKey.y] + 1]) {
if(!visited[it.x][it.y])
MinDist = min(MinDist, abs(it.x - NextSearch.x)+abs(it.y - NextSearch.y));
}
NextSearch.Expectation = NextSearch.CostTime + MinDist;
}
visited[NextSearch.x][NextSearch.y] = true;//代表走过了该节点
Search.push(NextSearch);
}
}
}
}
if (Goal.empty()) {//搜索结束后，目标节点已经删完了，代表没有找到唐僧
printf("impossible\n");
return;
}
State a = Goal.top();//因为是优先队列，所以第一个是最小的
Goal.pop();
printf("%d\n", a.CostTime);
}可能看到这里，很多人会疑惑Expectation是干嘛的，Expectation是我本来想利用启发式函数来进行A*算法的工具，结果好像优化效果不佳，其含义就是当前State的CostTime加上该点到最近的下一目标的曼哈顿距离（横坐标相减的绝对值+纵坐标相减的绝对值）。 Expectation一定小于我从当前位置到达下一目标的实际距离，所以是一个下限。如果这个下限都很大的话，实际距离就会更大，那么这个点就不会优先考虑。所以优先队列会先考虑期望值较小的点。
那么基于这个“较傻”的启发式函数得到的完整代码如下：
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<bitset>
#include<cmath>
using namespace std;
struct State{
int x{},y{};
int CostTime{};
int Expectation=0;
bitset<5> Snake;
explicit State(int a,int b):x(a),y(b),CostTime(0){}
State()=default;
bool operator>(const State & a) const{
return Expectation>a.Expectation;
}
};
struct Position{
int x,y;
Position(int a,int b):x(a),y(b){}
bool operator==(const Position a) const{
return a.x==x&&y==a.y;
}
};
int N;int M;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int Palace[102][102]{};
bool visited[102][102]{};
State Begin{};State Final{};
vector<Position> Target[11];
void SaveTangMonk() {
priority_queue<State,vector<State>,greater<State>> Goal;
Goal.push(Begin);
while (!Goal.empty()) {
State NowKey = Goal.top();
if (Palace[NowKey.x][NowKey.y] == M + 1) break;
Goal.pop();
memset(visited, 0, sizeof(visited));
priority_queue<State, vector<State>, greater<State>> Search;
Search.push(NowKey);
int NumOfKey=0;
while (!Search.empty()) {
State NowSearch = Search.top();
Search.pop();
visited[NowSearch.x][NowSearch.y]=true;
if (Palace[NowSearch.x][NowSearch.y] == Palace[NowKey.x][NowKey.y] + 1) {
Goal.push(NowSearch);
NumOfKey++;
if (NumOfKey==Target[Palace[NowSearch.x][NowSearch.y]].size()) break;
continue;
}
for (int i = 0; i < 4; i++) {
if (Palace[NowSearch.x + dx[i]][NowSearch.y + dy[i]] != -1&&!visited[NowSearch.x+dx[i]][NowSearch.y+dy[i]]) {
State NextSearch(NowSearch.x + dx[i], NowSearch.y + dy[i]);
NextSearch.Snake = NowSearch.Snake;
if (Palace[NextSearch.x][NextSearch.y] >= 20 && !NextSearch.Snake[Palace[NextSearch.x][NextSearch.y] - 20]) {
NextSearch.CostTime = NowSearch.CostTime + 2;
int MinDist = 99999;
for (auto &it : Target[Palace[NowKey.x][NowKey.y] + 1]) {
if(!visited[it.x][it.y])
MinDist = min(MinDist, abs(it.x - NextSearch.x)+abs(it.y - NextSearch.y));
}
NextSearch.Expectation = NextSearch.CostTime + MinDist;
NextSearch.Snake[Palace[NextSearch.x][NextSearch.y] - 20] = true;
} else {
NextSearch.CostTime = NowSearch.CostTime + 1;
int MinDist = 99999;
for (auto &it : Target[Palace[NowKey.x][NowKey.y] + 1]) {
if(!visited[it.x][it.y])
MinDist = min(MinDist, abs(it.x - NextSearch.x)+abs(it.y - NextSearch.y));
}
NextSearch.Expectation = NextSearch.CostTime + MinDist;
}
visited[NextSearch.x][NextSearch.y] = true;
Search.push(NextSearch);
}
}
}
}
if (Goal.empty()) {
printf("impossible\n");
return;
}
State a = Goal.top();
Goal.pop();
printf("%d\n", a.CostTime);
}
void Input(){
int S=20;
memset(Palace,-1,sizeof(Palace));
memset(Target,0,sizeof(Target));
cin.get();
for(int i=1;i<=N;i++) {
for (int j = 1; j <= N; j++) {
char c=cin.get();//NOLINT
switch(c){
case 'K':Palace[i][j]=0;Begin.x=i;Begin.y=j;Begin.CostTime=0;break;
case 'T':Palace[i][j]=M+1;Final.x=i;Final.y=j;Target[M+1].emplace_back(i,j);break;
case '.':Palace[i][j]=-2;break;
case '#':Palace[i][j]=-1;break;
case 'S':Palace[i][j]=S++;break;
default:Palace[i][j]=c-'0';Target[c-'0'].emplace_back(i,j);break;
}
if (j == N) { cin.get(); }//读掉回车
}
}
}
int main() {
while (scanf("%d %d", &N, &M) && (N != 0 || M != 0)) {
Input();
SaveTangMonk();
}
}总结：
如果你对于广度优先搜索和优先队列不太了解的话，一定要先去查一查这方面的资料（不用查实现原理，只需要明白作用就行）。这个题其实我做的很狼狈，这样16ms的代码在面对一些三四十大小的矩阵时已经跑的很慢了（我也不明白为什么会是16ms）。希望这篇文章可以帮到您。最后附上一个测试数据生成代码，可以生成一些测试数据。求点赞，求关注！
#include<iostream>
#include<ctime>
using namespace std;
int main(){
srand(time(nullptr));
int N=rand()%30+1;//代表N是从1～30（大小可以自己调）
int M=rand()%10;//代表M是从0～9
int x=5;//保证生成5个以内的S
char Palace[102][102];
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(i==1&&j==1) {
Palace[1][1] = 'K';//设置起点为左上角
continue;
}
if(i==N&&j==N){
Palace[N][N]='T';//设置终点为右下角，比较极限
continue;
}
int temp=rand()%(M+3)+1;
if(temp<=M){
Palace[i][j]=temp+'0';
}
else if(temp==M+1){
Palace[i][j]='.';
}
else if(temp==M+2){
Palace[i][j]='#';
}
else if(temp==M+3){
if(x!=0) {
Palace[i][j] = 'S';
x--;
}
else{
Palace[i][j]='.';
}
}
}
}
printf("%d %d\n",N,M);
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
printf("%c",Palace[i][j]);
}
printf("\n");
}
}