784 - Maze Exploration(bfs)

2024-08-24 04:48
文章标签 bfs maze exploration 784

本文主要是介绍784 - Maze Exploration(bfs),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:784 - Maze Exploration


题目大意:类似走迷宫, 八个方向走,空格的表示可以走,‘X’不可以走,‘*’是起点。


解题思路:BFS;


#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;const int N = 35;
const int M = 85;
int t, k;char maze[N][M];
int visit[N][M];int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
struct node {int x, y;
};
queue<node> q;void bfs(int x, int y) {visit[x][y] = 1;maze[x][y] = '#';node n;n.x = x;n.y = y;q.push(n);while(!q.empty()) {n = q.front();q.pop();for(int i = 0; i < 8; i++) {int x = n.x + dir[i][0];int y = n.y + dir[i][1];if(x >= 0 && x < k && y >= 0 && y < strlen(maze[x])) {if(maze[x][y] == ' ' && !visit[x][y]) {visit[x][y] = 1;maze[x][y] = '#';node n1;n1.x = x;n1.y = y;q.push(n1);}}}}}int main() {scanf("%d%*c", &t);while(t--) {memset(maze, 0, sizeof(maze));memset(visit, 0, sizeof(visit));k = 0;while(gets(maze[k])) {if(maze[k][0] == '_')break;k++;}int i, j;for(i = 0; i < k; i++)  {for(j = 0; j < strlen(maze[i]); j++)if(maze[i][j] == '*')break;if(maze[i][j] == '*')break;}bfs(i, j);for(i = 0; i <= k; i++)printf("%s\n", maze[i]);}return 0;
}


这篇关于784 - Maze Exploration(bfs)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1101490

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

双头BFS

牛客月赛100 D题,过了80%数据,调了一下午。。。烦死了。。。 还是没调试出来,别人的代码用5维的距离的更新有滞后性,要在遍历之前要去重。。。 #include<bits/stdc++.h>using namespace std;const int N=2e3+10;char g[N][N];int dis[N][N],d1[N][N];int n,m,sx,sy;int dx

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历,在uva上找了个题敲了出来,感觉还不错,最近敲代码挺有手感的,希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in

【CF】D. Arthur and Walls(BFS + 贪心)

D题 解题思路就是每次检查2X2的方格里是否只有一个‘*’,如果有的话这个*就需要变成‘.’,利用BFS进行遍历,入队的要求是这个点为. 一开始将所有的'.'全部加入队列,如果碰到一个'*'变成'.'就入队,判断的时候从4个方向就行判断 题目链接:http://codeforces.com/contest/525/problem/D #include<cstdio>#include<

【HDU】5222 Exploration(并查集+拓扑排序)

对于无向边使用并查集合并成一个集合,对于有向边使用判断是否存在环 唯一无语的地方就是看输入是百万级的,加个输入挂跑9s,不加挂跑了5s #include<cstdio>#include<cstring>#include<vector>#include<algorithm>using namespace std;#pragma comment(linker, "/STACK:102

hdu2717(裸bfs广搜)

Catch That Cow Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7304 Accepted Submission(s): 2308 题目链接: http://acm.hdu.edu.cn/showproblem.

Codeforces#295(Div.2)A、B(模拟+BFS)

解题报告链接:点击打开链接 C. 题目链接:点击打开链接 解题思路: 对于给定的字符串,取出现次数最多的字母(可以同时有多个)。由这些字母组成长度为n的字符串,求有多少种组合。最后用数学知识即可。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <climits>