[BFS广度优先搜索] 迷宫

2024-08-30 07:20
文章标签 搜索 bfs 优先 广度 迷宫

本文主要是介绍[BFS广度优先搜索] 迷宫,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

描述

给定一个仅由数字 0 与 1 组成的 n 行 m 列的迷宫。若你位于一格 0 上,那么你可以移动到相邻 4 格中的任意一格 1 上;同样地,若你位于一格 1 上, 那么你可以移动到相邻 4 格中的任意一格 0 上。

现在,有 q 次询问。每次询问从给定的某一格 (第 x 行,第 y 列,均从 0 开始标号) 开始,在规则内任意移动。这样,有一些格子是可能到达的,而其余格子是无法到达的。求可能到达的格子数量。

输入

输入第一行包含两个整数 n 和 m(1 ≤ n, m ≤ 103)。
接下来 n 行,每行包含 m 个 0 或 1 的整数,表示迷宫的内容。
接下来一行包含一个整数 q(0 ≤ q ≤ 105)。
接下来 q 行,每行包含两个整数 x 和 y,表示一次询问(0 ≤ x < n,0 ≤ y < m)。

输出

输出 q 行,每行一个整数,依次表示每个询问的答案。

样例输入

5 4
1 1 0 1
1 1 1 1
1 1 0 0
0 0 1 1
0 1 0 0
4
4 3
0 1
3 0
1 1

样例输出

4
11
2
1

提示

对于第二条询问,如图所示,从黄色格子 (0, 1) 出发,可分别到达所有绿色格子,包含自身共 11 格。

 解题分析

这道题目首先可以看出是一道很经典的BFS广度优先搜索的题目。我们只需要用一个队列,一个visited数组,一些规则与判断就可以比较容易地去遍历我们能够到达的所有格子。但是很显然,如果我们每一个格子都这样去遍历的话,最后询问次数一旦多了起来,就很容易超时。所以我们想到了一个可以用一个数组记录下来的方法,这个时候我们还要想到其实按照题目所述的做法,我们这样是对称的。也就是说这是一个“连通块”,我们只需要找出这些连通块,每次遍历一遍后把所有走过的连通块都标记上相同的步数即可。为了更加便捷快速,我们可以用一个巧妙的自定义结构体Node创建一个数组,然后记录下我们走过的格子的位置路径,一路保存下来然后最后直接用一个循环去遍历更新即可。最后,我们的输入输出就变简单了,如果是我们已经遍历更新过的位置,那么我们直接输出路径的长度(或者说是遍历的所有格子的数量),如果是我们还没有遍历的位置,我们就调用bfs函数遍历一遍再输出我们的答案即可。

代码实现

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
// #include <iomanip>
#include <map>
#include <stack>
#include <list>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <sstream>
#define INF (1<<30)using namespace std;struct node{int x,y;
} f[10000100];int n,m;
char maze[1001][1001]={0};
int record[1001][1001]={0};
bool visited[1001][1001]={0};
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};void bfs(int x,int y){queue<node> q;q.push({x,y});visited[x][y]=1;node tmp;int t=0;while(!q.empty()){tmp=q.front();q.pop();if(record[tmp.x][tmp.y]) continue;for(int i=0;i<4;i++){int nx = tmp.x + dx[i] , ny = tmp.y + dy[i];if(nx <= 0 || ny <= 0 || nx > n || ny > n) continue;if(visited[nx][ny] || record[nx][ny]) continue;if(maze[nx][ny]==maze[tmp.x][tmp.y]) continue;q.push({nx,ny});visited[nx][ny]=1;f[t].x=nx; f[t].y=ny;t++;}}record[x][y]=t+1;for(int i=0;i<t;i++){record[f[i].x][f[i].y]=t+1;}
}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",maze[i]+1);}int tmpx,tmpy;for(int i=0;i<m;i++){scanf("%d%d",&tmpx,&tmpy);if(record[tmpx][tmpy]) printf("%d\n",record[tmpx][tmpy]);else {bfs(tmpx,tmpy);printf("%d\n",record[tmpx][tmpy]);}}return 0;
}

这篇关于[BFS广度优先搜索] 迷宫的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

hdu1254(嵌套bfs,两次bfs)

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

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

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

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

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;