/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1026
Name : 1026 Ignatius and the Princess I
Date : Monday, April 2, 2012
Time Stage : 3 hours
Result:
5689062 2012-04-02 12:05:54 Accepted 1026
15MS 496K 4200 B
C++ pyy
5688705 2012-04-02 11:02:19 Wrong Answer 1026
15MS 404K 4449 B
C++ pyy
5688696 2012-04-02 11:01:44 Compilation Error
1026
0MS 0K 4493 B
C++ pyy
5688688 2012-04-02 11:00:26 Compilation Error
1026
0MS 0K 4493 B
C++ pyy
5688467 2012-04-02 10:36:55 Wrong Answer 1026
15MS 404K 3747 B
C++ pyy
Test Data :
Review :
要用优先队列来做,但我不明白原理,本来格式比较清晰,
后来改来改去,代码就比较乱了~
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std ;
#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define INF (0x3f3f3f3f)
#define MAXN (102)
#define MAXM (100)
#define DB /##/
#define LL __int64
#define SEC(pt) path[(pt).x][(pt).y].sec
#define PRE(pt) path[(pt).x][(pt).y].pre
#define MAP(pt) map[(pt).x][(pt).y]
#define _IN_RANGE(a, s, e) ((s) <= (a) && (a) < (e))
#define _IN_X(a) (_IN_RANGE(a, 0, n))
#define _IN_Y(b) (_IN_RANGE(b, 0, m))
#define _IN(pt) (_IN_X(pt.x) && _IN_Y(pt.y))
#define _IS_NUM(a) _IN_RANGE(a, '0', '9'+1)
#define _NUM(n) ((n)-'0')
#define PATH(p) path[p.x][p.y]
int n, m;
char map[MAXN][MAXN];
const int dir[4][2] = {0,1, 0,-1, 1,0, -1,0};
struct POINT {
int x, y;
POINT(int i = -1, int j = -1): x(i), y(j) {}
bool operator== (const POINT &pt) {
return pt.x == x && pt.y == y;
}
POINT operator+ (const POINT &pt) {
return POINT(this->x + pt.x, this->y + pt.y);
}
};
struct NODE {
NODE(POINT cu = POINT(), POINT pt = POINT(), int s = INF):
cur(cu), pre(pt), sec(s) {}
POINT pre, cur;
int sec;
bool operator< (const NODE nd) const {
return sec > nd.sec;
}
} path[MAXN][MAXN];
NODE BEG, END;
void bfs()
{
int i, j, flag;
priority_queue<NODE> q;
q.push(BEG);
while (!q.empty())
{
NODE nd = q.top();
POINT t = nd.cur;
q.pop();
if (t == END.cur)
break;
DB printf ("----for -----\n");
for (i = 0; i < 4; ++i)
{
POINT nt = t + POINT(dir[i][0], dir[i][1]);
if (!_IN(nt) || 'X' == MAP(nt))
continue;
DB flag = 0;
if ('.' == MAP(nt))
{
if (SEC(nt) > SEC(t) + 1)
{
SEC(nt) = SEC(t) + 1;
PRE(nt) = t;
q.push(PATH(nt));
DB flag = 1;
}
}
else if (_IS_NUM(MAP(nt)))
{
if (SEC(nt) > SEC(t) + 1 + _NUM(MAP(nt)))
{
SEC(nt) = SEC(t) + 1 + _NUM(MAP(nt));
PRE(nt) = t;
q.push(PATH(nt));
DB flag = 1;
}
}
DB printf ("t: %d, %d. MAP: %c, NODE: sec: %d, pre(%d,%d)\n", \
t.x, t.y, MAP(t), SEC(t), PRE(t).x, PRE(t).y);
DB printf ("nt: %d, %d. MAP: %c .NODE: sec: %d\n", \
nt.x, nt.y, MAP(nt), SEC(nt));
DB if (flag) printf ("push: (%d, %d)\n", nt.x, nt.y);
DB getchar();
}
}
}
void dfs(POINT pt)
{
if (pt == BEG.cur)
{
return ;
}
dfs(PRE(pt));
if (_IS_NUM(MAP(pt)))
{
int cnt = _NUM(MAP(pt));
printf ("%ds:(%d,%d)->(%d,%d)\n", SEC(pt)-cnt, PRE(pt).x, PRE(pt).y,
pt.x, pt.y);
for (int i = 1; i <= cnt; ++i)
{
printf ("%ds:FIGHT AT (%d,%d)\n", i+SEC(pt)-cnt, pt.x, pt.y);
}
}
else {
printf ("%ds:(%d,%d)->(%d,%d)\n", SEC(pt), PRE(pt).x, PRE(pt).y,
pt.x, pt.y);
}
}
void out()
{
POINT T = END.cur;
if (INF == SEC(T))
{
printf ("God please help our poor hero.\n");
printf ("FINISH\n");
return ;
}
printf ("It takes %d seconds to reach the target position, let me show "
"you the way.\n", SEC(END.cur));
dfs(END.cur);
printf ("FINISH\n");
}
void init()
{
int i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < m; ++j)
{
path[i][j].cur = POINT(i, j);
path[i][j].pre = POINT(-1, -1);
path[i][j].sec = INF;
}
BEG = NODE(POINT(0, 0), POINT(-1, -1), 0);
END = NODE(POINT(n-1, m-1));
SEC(BEG.cur) = 0;
}
int main()
{
int i, j;
while (scanf("%d %d", &n, &m) != EOF)
{
init();
for (i = 0; i < n; ++i)
{
getchar();
for (j = 0; j < m; ++j)
scanf("%c", &map[i][j]);
}
bfs();
out();
}
return 0;
}
分享到:
相关推荐
BFS++ 是西门子一个优秀的资产管理软件。主要应用于电厂等大型资产密集型企业。
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
BFS++是以网络为支撑、数据库为核心,以设备的运行和维修管理为主要对象的一套综合性的电厂生产管理系统。它提供的主要功能包括:基本系统、设备数据、维修管理、运行管理、备件管理、文档管理等六个部分。
代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 ...
ACM入门题,BFS + hash 的使用与结合
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
this is code for bfs in c++
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS 算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS 算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS 算法面试通关40讲完整课件 27-31 深度...
图的相关算法比较全面的总结,包括了图的深度和广度遍历算法,prim和kruskal两种最小生成树的算法,邻接矩阵和邻接表两种储存结构,做课程设计、实验报告或者数据结构学习者可以参考参考啊``源代码都是我亲手打的,...
DFS+BFS深度+广度优先遍历.cpp
bfs ,dfs algoritm in TC
MATLAB源码集锦-基于BFS广度优先搜索算法代码
ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文...
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于...
搜索入门之BFS深度优先搜索.ppt 搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。 搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合...
广度优先搜索算法—BFS的相关代码,包括循环队列的代码
用邻接矩阵来存储图,Floyed算法求任意两点间的最短路径并输出,广度优先遍历,深度优先遍历
1.包含了8个文档。 2.大部分为集训队文档。 3.部分算法详解文档。 4.文库搜索,全部下载需要十几分。
基于DFS和BFS广度优先搜索算法的路线搜索算法仿真+含代码操作演示视频 运行注意事项:使用matlab2021a或者更高版本测试,运行里面的Runme.m文件,不要直接运行子函数文件。运行时注意matlab左侧的当前文件夹窗口...
基于python实现的广度优先遍历搜索(BFS)实验源码+代码详细注释+项目说明+实验结果及总结.7z 广度优先搜索算法(英语:Breadth-First-Search,缩写为BFS),是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树...