/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1180
Name : 1180 诡异的楼梯
Date : Tuesday, April 03, 2012
Time Stage : 3 hours
Result:
5696313 2012-04-03 14:44:43 Accepted 1180
0MS 280K 3502 B
C++ pyy
Test Data :
Review :
WA了无数次之后,看到有人说用优先队列……于是AC了,但不明白有人没用优先队列是怎么
AC的,求解答!
//----------------------------------------------------------------------------*/
#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 (22)
#define DB /##/
#define LL __int64
#define _IN_RANGE(a, s, t) ((s) <= (a) && (a) < (t))
#define _IN(x, y) (_IN_RANGE(x, 0, m) && _IN_RANGE(y, 0, n))
#define _MAP(pt) map[pt.x][pt.y]
struct POINT {
POINT(int ax = -1, int ay = -1): x(ax), y(ay) {}
bool operator== (const POINT &pt) const {
return pt.x == x && pt.y == y;
}
bool operator< (const POINT &pt) const { // 两个 const 的限定是必须的,否则会报错
return mi > pt.mi;
}
int x, y;
int mi;
} path[MAXN][MAXN];
const int dir[4][2] = {0,1, 0,-1, 1,0, -1,0};
int m, n;
char map[MAXN][MAXN];
//bool vis[MAXN][MAXN];
POINT S, T, np, tm;
int bfs()
{
char c ;
int i, j;
priority_queue<POINT> q; // 因为有楼梯的存在,所以每个格子的花费不是完全相同
// 因此要用到优先队列
// 要注意 m = n = 0 的情况
S.mi = 0;
T.mi = 0;
path[T.x][T.y] = T;
q.push(S);
while (!q.empty())
{
tm = q.top();
path[tm.x][tm.y] = tm;
q.pop();
if (tm == T)
break;
DB printf("\ntm:(%d,%d), map:%c, mi:%d\n", tm.x, tm.y, _MAP(tm), tm.mi);
DB printf("---- for ----\n");
for (i = 0; i < 4; ++i)
{
np = tm;
np.x = np.x + dir[i][0];
np.y = np.y + dir[i][1];
if (!_IN(np.x, np.y) || '*' == _MAP(np))
continue;
DB printf("1. np: (%d,%d), map:%c, mi:%d\n", np.x, np.y, _MAP(np), np.mi);
if ('.' == _MAP(np))
{
np.mi = tm.mi + 1;
_MAP(np) = '*';
q.push(np);
}
else
{
if (tm.mi & 1) // 时间为奇数,则楼梯转向
{
if ('|' == _MAP(np))
c = '-';
else
c = '|';
}
else
c = _MAP(np);
// 楼梯与自己的方向不同,则等一分钟,并使楼梯转向
if ('|' == c && np.y != tm.y)
{
c = '-';
np.mi = tm.mi + 1;
}
else if ('-' == c && np.x != tm.x)
{
c = '|';
np.mi = tm.mi + 1;
}
// 把harry送到对面
if ('|' == c)
{
if (np.x < tm.x) // 向上送
--np.x;
else if (np.x > tm.x) // 向下送
++np.x;
}
else
{
if (np.y < tm.y) // 向左边送
--np.y;
else if (np.y > tm.y) // 向右边送
++np.y;
}
// 送的过程要一分钟
++np.mi;
// 如果不判断楼梯背后的点是否被访问过,则会 MLE
if (_IN(np.x, np.y) && '*' != _MAP(np))
q.push(np);
}
DB printf("2. np: (%d,%d), map:%c, mi:%d\n", np.x, np.y, _MAP(np), np.mi);
}
}
return path[T.x][T.y].mi;
}
int main()
{
int i, j;
while (scanf("%d %d", &m, &n) != EOF)
{
for (i = 0; i < m; ++i)
{
getchar();
for (j = 0; j < n; ++j)
{
scanf("%c", &map[i][j]);
if (map[i][j] == 'S')
{
S = POINT(i, j);
map[i][j] = '*'; // 起点没有用了,标记为墙
}
else if ('T' == map[i][j])
{
T = POINT(i, j);
map[i][j] = '.'; // 终点标记为走廊,方便bfs统一处理
}
}
}
printf ("%d\n", bfs());
}
return 0;
}
分享到:
相关推荐
BFS++ 是西门子一个优秀的资产管理软件。主要应用于电厂等大型资产密集型企业。
BFS++是以网络为支撑、数据库为核心,以设备的运行和维修管理为主要对象的一套综合性的电厂生产管理系统。它提供的主要功能包括:基本系统、设备数据、维修管理、运行管理、备件管理、文档管理等六个部分。
代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 ...
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
ACM入门题,BFS + hash 的使用与结合
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
this is code for bfs in c++
图的相关算法比较全面的总结,包括了图的深度和广度遍历算法,prim和kruskal两种最小生成树的算法,邻接矩阵和邻接表两种储存结构,做课程设计、实验报告或者数据结构学习者可以参考参考啊``源代码都是我亲手打的,...
bfs ,dfs algoritm in TC
算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS 算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS 算法面试通关40讲完整课件 27-31 深度优先DFS+广度优先BFS 算法面试通关40讲完整课件 27-31 深度...
DFS+BFS深度+广度优先遍历.cpp
MATLAB源码集锦-基于BFS广度优先搜索算法代码
ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文...
搜索入门之BFS深度优先搜索.ppt 搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。 搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合...
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于...
用邻接矩阵来存储图,Floyed算法求任意两点间的最短路径并输出,广度优先遍历,深度优先遍历
1.包含了8个文档。 2.大部分为集训队文档。 3.部分算法详解文档。 4.文库搜索,全部下载需要十几分。
广度优先搜索算法—BFS的相关代码,包括循环队列的代码
基于DFS和BFS广度优先搜索算法的路线搜索算法仿真+含代码操作演示视频 运行注意事项:使用matlab2021a或者更高版本测试,运行里面的Runme.m文件,不要直接运行子函数文件。运行时注意matlab左侧的当前文件夹窗口...
最终效果是实现了Prim随机生成迷宫,BFS&DFS路径显示、最短路长度显示、过程动态展示,主函数中有菜单,操作方便。 不仅可以用来读代码长知识、还可以用作算法演示。 附带第五版的exe文件,欢迎使用!