/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1240
Name : 1240 Asteroids!
Date : Wednesday, April 4, 2012
Time Stage : half an hour
Result:
5703343 2012-04-04 15:07:36 Accepted 1240
0MS 296K 2347 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 (12)
#define DB /##/
#define LL __int64
struct NODE {
int x, y, z;
int step;
bool operator== (const NODE &nd) {
return x == nd.x && y == nd.y && z == nd.z;
}
};
#define SPACE(nd) space[(nd).z][(nd).y][(nd).x]
#define MAP(nd) map[(nd).z][(nd).y][(nd).x]
#define BEG SPACE(beg)
#define END SPACE(end)
#define _IN_S(x) (0 <= (x) && (x) < n)
#define _IN(nd) (_IN_S(nd.x) && _IN_S(nd.y) && _IN_S(nd.z))
const int dir[6][3] = {0,0,1, 0,0,-1, 0,1,0, 0,-1,0, 1,0,0, -1,0,0};
char map[MAXN][MAXN][MAXN];
int n;
NODE space[MAXN][MAXN][MAXN], beg, end;
void bfs()
{
int i, j, k;
queue<NODE> q;
NODE t, nn;
beg.step = 0;
q.push(beg);
while (!q.empty())
{
t = q.front();
q.pop();
SPACE(t) = t;
if (t == END)
break;
for (i = 0; i < 6; ++i)
{
nn = t;
nn.z += dir[i][0];
nn.y += dir[i][1];
nn.x += dir[i][2];
if (!_IN(nn) || 'X' == MAP(nn))
continue;
++nn.step;
MAP(nn) = 'X';
q.push(nn);
}
}
}
int main()
{
int i, j, k;
char st[MAXN], en[MAXN];
while (scanf("%s %d", st, &n) != EOF)
{
MEM(space, INF);
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
getchar();
for (k = 0; k < n; ++k)
{
scanf("%c", &map[i][j][k]);
}
}
}
scanf("%d %d %d", &beg.x, &beg.y, &beg.z);
scanf("%d %d %d", &end.x, &end.y, &end.z);
getchar();
scanf("%s", en);
bfs();
if (INF == END.step)
printf("NO ROUTE\n");
else
printf ("%d %d\n", n, END.step);
}
return 0;
}
分享到:
相关推荐
讲解了BFS。 这个视频的联系地址可以在这里查看:https://www.acwing.com/problem/search/1/?csrfmiddlewaretoken=TovleMBNSFUoIg1I0cdL4vIKiggOzDXxQl9ELwj0iVTiZ6OyRwzVOnbYGlHNBPU5&search_content=BFS
ACM培训好资料!能帮助你快速提高ACM AC题目的能力,值得一下
详细地介绍BFS的思路模式以及用几个案例教授怎么运用BFS去解题。
hdu 3085 一道bfs题 一点值得注意的,鬼魅先走,mm与gg后走,直接模拟这个这个场景,突出时间的先后性,一秒与一秒的区别。。。这样模拟很难出错
代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 ...
算法之BFS与DFS
广度优先搜索算法—BFS的相关代码,包括循环队列的代码
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于...
搜索入门之BFS深度优先搜索.ppt 搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。 搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合...
bfs广度优先搜索(BFS)是一种计算机科学中的算法,用于遍历或搜索树或图。它通过从起始节点开始,逐层向外扩展,直到找到目标节点或遍历完所有节点。BFS算法保证了在遍历过程中,先访问的节点具有较小的深度。 BFS...
基于python的广度优先搜索算法BFS设计与实现
个人新项目可作毕设基于python实现的广度优先遍历搜索(BFS)源码含实验结果及总结操作说明.zip个人新项目可作毕设基于python实现的广度优先遍历搜索(BFS)源码含实验结果及总结操作说明.zip个人新项目可作毕设基于...
2分图匹配的BFS实现,C/C++源码。适用于稀疏二分图,边较少,增广路较短。
能够提取最短路径 和最长路径 的 广度优先搜索 BFS (Breadth-first search)代码, 编写语言C++
这是ACM中也比较重要的一个知识点,其中的资源包含文档和PPT,当中有搜索的概述,有bfs和dfs,有需要的可以看看!
MATLAB源码集锦-基于BFS广度优先搜索算法代码
从最基础的迷宫问题看深搜和宽搜的内涵,理解最基础的穷举搜索。
ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文...
bfsk在高斯信道和锐利多径衰落信道中传输的性能比较,使用simulink!!!!!!!!!