http://acm.hdu.edu.cn/showproblem.php?pid=1026
题意:问从图的左上角到达右下角需要的最短时间,如果格子是数字n(1-9),说明有怪兽,要打死他花费n的时间
Sample Input
Sample Output
It takes 13 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
FINISH
It takes 14 seconds to reach the target position, let me show you the way.
1s:(0,0)->(1,0)
2s:(1,0)->(1,1)
3s:(1,1)->(2,1)
4s:(2,1)->(2,2)
5s:(2,2)->(2,3)
6s:(2,3)->(1,3)
7s:(1,3)->(1,4)
8s:FIGHT AT (1,4)
9s:FIGHT AT (1,4)
10s:(1,4)->(1,5)
11s:(1,5)->(2,5)
12s:(2,5)->(3,5)
13s:(3,5)->(4,5)
14s:FIGHT AT (4,5)
FINISH
God please help our poor hero.
FINISH
速度还不错:
#include <iostream>
#include <queue>
using namespace std;
#define M 105
struct point{
int x;
int y;
int times;
friend bool operator < (point a, point b)
{
return a.times > b.times; //重载小于号使得小的先出队列
}
};
struct Pre{
int px, py;
}pre[M][M];
int r, c;
int x_move[4] = {-1, 0, 1, 0};
int y_move[4] = {0, 1, 0, -1};
char map[M][M];
bool vis[M][M];
void bfs (int x, int y)
{
int i, v;
vis[x][y] = true;
point ft, tp;
pre[x][y].px = -1; //终点标记
ft.x = x, ft.y = y, ft.times = 0;
if (map[x][y] != '.')
ft.times = map[x][y] - '0';
priority_queue<point> q; //优先队列
q.push (ft);
while (!q.empty())
{
ft = q.top();
q.pop();
if (ft.x == 0 && ft.y == 0)
{
printf ("It takes %d seconds to reach the target position, let me show you the way.\n", ft.times);
int key = 1, total = ft.times;
x = ft.x, y = ft.y;
while (pre[x][y].px != -1) //不断寻找前驱直到到达终点
{
int tx = pre[x][y].px;
int ty = pre[x][y].py;
printf ("%ds:(%d,%d)->(%d,%d)\n", key++, x, y, tx, ty);
if (map[tx][ty] != '.')
for (i = 0; i < map[tx][ty] - '0'; i++)
printf ("%ds:FIGHT AT (%d,%d)\n", key++, tx, ty);
x = tx;
y = ty;
}
return ;
}
for (i = 0; i < 4; i++)
{
tp.x = ft.x + x_move[i];
if (tp.x < 0 || tp.x >= r)
continue;
tp.y = ft.y + y_move[i];
if (tp.y < 0 || tp.y >= c)
continue;
if (vis[tp.x][tp.y])
continue;
vis[tp.x][tp.y] = true;
if (map[tp.x][tp.y] == 'X')
continue;
if (map[tp.x][tp.y] == '.')
v = 1;
else v = map[tp.x][tp.y] - '0' + 1;
tp.times = ft.times + v;
/**********记录tp的前驱ft**********/
pre[tp.x][tp.y].px = ft.x;
pre[tp.x][tp.y].py = ft.y;
/**********记录tp的前驱ft**********/
q.push (tp);
}
}
puts ("God please help our poor hero.");
}
int main()
{
int i;
while (~scanf ("%d%d", &r, &c))
{
for (i = 0; i < r; i++)
scanf ("%s", map[i]);
memset (vis, false, sizeof(vis));
bfs (r-1, c-1); //倒过来搜索就可以不用栈了
puts ("FINISH");
}
return 0;
}
- 大小: 3.4 KB
- 大小: 6.1 KB
分享到:
相关推荐
搜索 dfs 解题代码 hdu1241
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
08暑假集训搜索组解题报告 An Introduction to Recursion, Part 1.mht ...深度优先搜索-bylove8909.doc 搜索基础.pdf 搜索入门 - from hdu.ppt 搜索算法的通用优化方法.pdf 谈搜索算法的剪枝优化.pdf
hdu2101AC代码
For a positive integer n, let’s denote function f(n,m) as the m-th smallest integer x that x>n and gcd(x,n)=1. For example, f(5,1)=6 and f(5,5)=11. You are given the value of m and (f(n,m)?n)⊕n,...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1695 GCD(欧拉函数+容斥原理).docx