题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1026
题目大意:一个人要从N*M矩形地图的左上角走到右下角.且只能向四个方向走.X表示墙不能走.字符1-9表示怪物并且数字代表怪物的血量.也就是杀死怪物需要该数字的单位时间.人每走一个格子花费1个单位的时间.然后要你按照格式打印最短时间的路径和具体的路径.
简单的最短路径题.直接用bfs做.用二维数组保存路径.由终点往起点递归.就可以把完整的顺序路径加到容器中去.
AC代码:
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <stdio.h>
#include <math.h>
#include <memory.h>
#include <functional>
#include <algorithm>
using namespace std;
#define Size 200
typedef std::pair<int, int> pairType;struct Node
{int x;int y;int time;//时间优先.bool operator<(Node a) const{return this->time> a.time;}
};
int dir[4][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
char world[Size][Size];
int visit[Size][Size];
Node path[Size][Size];
int m, n;
char cr;
vector<pairType> filePath;
int num;void advisitath(int x,int y)
{//判断是否到起始点.if (x == 0 && y == 0){return;}advisitath(path[x][y].x, path[x][y].y);//因为是递归.最好其实是顺序加入路径的.filePath.push_back(pairType(path[x][y].x, path[x][y].y));
}
void print()
{//把路径加到容器中.advisitath(m - 1, n - 1);filePath.push_back(pairType(m - 1, n - 1));int secNum = 1;printf("It takes %d seconds to reach the target position, let me show you the way.\n", num);for (int i = 0; i < filePath.size() - 1; ++i){printf("%ds:(%d,%d)->(%d,%d)\n", secNum++, filePath[i].first, filePath[i].second, filePath[i + 1].first, filePath[i + 1].second);//如果不是正常路.也就是怪物.if (world[filePath[i+1].first][filePath[i+1].second] != '.'){for (int j = 0; j < world[filePath[i+1].first][filePath[i+1].second] - '0'; ++j){printf("%ds:FIGHT AT (%d,%d)\n", secNum++, filePath[i+1].first, filePath[i+1].second);}}}printf("FINISH\n");filePath.clear();
}
int bfs()
{//题目要求最短时间.以时间优先即可.priority_queue<Node> temp;Node now, next, s;memset(&s, 0, sizeof(s));temp.push(s);visit[0][0] = 1;while (!temp.empty()){now = temp.top();temp.pop();//判断是否到达.if (now.x == m - 1 && now.y == n - 1){return now.time;}//分别枚举四个方向.for (int i = 0; i < 4; ++i){next.x = now.x + dir[i][0];next.y = now.y + dir[i][1];//进行筛选.if (next.x >= 0 && next.y >= 0 && next.x < m && next.y < n && visit[next.x][next.y] == 0 && world[next.x][next.y] != 'X'){visit[next.x][next.y] = 1;//记录来的路径.path[next.x][next.y].x = now.x;path[next.x][next.y].y = now.y;if (world[next.x][next.y] == '.'){//普通路+1.next.time = now.time + 1;}else{//遇到怪物.先+1.然后再加怪物的血量.记得读取的是字符.next.time = now.time + world[next.x][next.y] - '0' + 1;}temp.push(next);}}}return -1;
}int main()
{while (scanf("%d%d", &m,&n) != EOF){for (int i = 0; i < m; ++i){//要先用getchar()把换行符读取掉.getchar();for (int j = 0; j < n; ++j){scanf("%c", &world[i][j]);visit[i][j] = 0;}}memset(path, 0, sizeof(path));num = bfs();if (num == -1){printf("God please help our poor hero.\n");printf("FINISH\n");}else{print();}}return 0;
}