BFS走迷宫传送门超时怎么改进啊?

第一次提问哈- -,想知道1000ms不超时的解决方法,比较笨
告诉我下思路或f'xiang就可以了

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

char m[100][100];
int r,c;
int sc,sr;
int ec,er;
int d[4][2]= {{-1,0},{0,1},{1,0},{0,-1}};
typedef struct
{
    int c;
    int r;
    int step;
} LOC;
struct
{
    int sc;
    int sr;
    int ec;
    int er;
} P[100];

int main()
{
    freopen("data.txt","r",stdin);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>c>>r;
        getchar();
        for(int i=0; i<c; i++)
            gets(m[i]);
        int W;
        cin>>W;
        for(int i=0; i<W; i++)
        {
            cin>>P[i].sc>>P[i].sr>>P[i].ec>>P[i].er;
        }
        cin>>sc>>sr;
        cin>>ec>>er;
        queue<LOC> qu;
        LOC cur;
        cur.c=sc;
        cur.r=sr;
        cur.step=0;
        qu.push(cur);
        int flag;
here:
        while(!qu.empty())
        {
            flag=0;
            cur=qu.front();
            qu.pop();
            if((cur.c==ec)&&(cur.r==er))
            {
                cout<<cur.step<<endl;
                flag=1;
                break;
            }
            for(int i=0; i<W; i++)
            {
                if(P[i].sc == cur.c && P[i].sr == cur.r)
                {
                    if(m[P[i].ec][P[i].er]=='0')
                    {
                        LOC New;
                        New.c=P[i].ec;
                        New.r=P[i].er;
                        New.step=cur.step+1;
                        m[New.c][New.r]='1';
                        qu.push(New);
                    }
                    goto here;
                }
            }
            for(int i=0; i<4; i++)
            {
                LOC New;
                New.c=cur.c+d[i][0];
                New.r=cur.r+d[i][1];
                if(New.c<0||New.c>c-1||New.r<0||New.r>r-1||m[New.c][New.r]=='1')
                    continue;
                New.step=cur.step+1;
                m[New.c][New.r]='1';
                qu.push(New);
            }
        }
        if(!flag)
        cout<<"die"<<endl;
    }
    return 0;
}


c++

1个回答

用DFS走迷宫。 BFS不适合走迷宫。

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
走迷宫--bfs
题意:走迷宫,但是加入了传送门,传送门分为入口和出口 输入:多case           迷宫大小n,m           输入无空格间隔n行01串(0代表可以走,1代表是墙)           输入q           q行传送门的入口和出口的坐标           终点和起点的坐标 思路:bfs,传送门无非就是换个地方继续bfs 代码:       #includ...
BFS走迷宫
第一篇先来写写关于广度优先搜索的东西,由于“涉世未深”,理解难免有偏差,还望指正。/* 以下程序实现简单走迷宫 注意: 1.起始坐标为(1,1),终点坐标为(deep,bro); 2.0表示通畅,1表示不通; 3.没有考虑无法走出去的情况 */ #include <iostream> #include <cmath> #include <cstring> using namespace std; #
3752走迷宫(bfs)
题目描述 一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。 Input 第一行是两个整数,R和C,代表迷宫的长和宽。( 1&lt;= R,C &lt;= 40) 接下来是R行,每行C个字符,代表整个迷宫。 空地格子用’.’表示,有障碍物的格子用’#’表...
BFS 走迷宫
默认从最左上角到最右下角
bfs走迷宫宽度优先搜索
要实现的是判断一个输入的迷宫,从起点(1,1)能否走到终点;这个比较简单,回头发一个记录路径的代码 既然是宽度优先搜索,肯定要用到队列,又因为每一个搜索对象有x,y两个参数决定,所以简单明了起见,我用了一个结构体表示。 #include using namespace std; char p[1200][1200]; int f[1200][1200]; int step[4][2]={{0
nyoj-306-走迷宫(bfs)
Dr.Kong设计的机器人卡多非常爱玩,它常常偷偷跑出实验室,在某个游乐场玩之不疲。这天卡多又跑出来了,在SJTL游乐场玩个不停,坐完碰碰车,又玩滑滑梯,这时卡多又走入一个迷宫。整个迷宫是用一个N * N的方阵给出,方阵中单元格中填充了一个整数,表示走到这个位置的难度。 这个迷宫可以向上走,向下走,向右走,向左走,但是不能穿越对角线。走迷宫的取胜规则很有意思,看谁能更快地找到一条路径,其路径
走迷宫(bfs, 最短路)
Input 10 10 #S######.# ......#..# .#.##.##.# .#........ ##.##.#### ....#....# .#######.# ....#..... .####.###. ....#...G# Output 22 代码: #include&lt;iostream&gt; #include&lt;cstring&gt; #inclu...
走迷宫(bfs)
给你一个 n 行 m 列的二维迷宫。'S'表示起点,'T' 表示终点,'#' 表示墙壁,'.' 表示平地。你需要从 'S' 出发走到 'T',每次只能上下左右走动,并且不能走出地图的范围以及不能走到墙壁上。请你计算出走到终点需要走的最少步数。输入格式第一行输入 nnn, mmm 表示迷宫大小。(1≤n,m≤100)(1 \leq n,m \leq 100)...
简单BFS - 走迷宫
描述 L上次旅行进入了一个迷宫,他被困在了一个N*M的矩形迷宫中。L开始在左上角的点,他知道出口在右下角,他可以向四个方向移动到相邻的点。不过这个迷宫有些魔法,每个格子有一种颜色,不同的颜色代表不一样的功能: 如果格子是红色的,表示当前格子无法通行 如果格子是粉红,表示格子可以正常通行 如果是橙色,当前格子也可以通行,不过会让L身上散发臭气 如果是蓝色,这个格子里有鳄鱼,如果L想通过身上要带有臭气...
广度优先搜索(bfs)-走迷宫
广度优先搜索 1、算法思想 广度,顾名思义,和之前的深度优先(点击查看)相对应。用走迷宫的例子来说,深度优先就是指每次走一步之后,优先考虑下一步,而广度优先则是在这一步之后,把接下来一步的所有路都列出来,在之后的所有扩展之中,在以一个为下一步,再将所有的该步可以到达的下一步,全部列举出来,再看第二部除了该步以外,还有那些其他的选择,再将第二步的其他选择中的每一步,都一一做扩展,每次扩展,都要检查所...
走迷宫最短步数--BFS
X:墙; .:可以走的路; D:出口; s:出生点; 源程序: #include #include #include #include using namespace std; struct node { int x,y; int step; }pr,pl; char map[50][50]; int  pos[50][50]; int h,w; int
走迷宫+钥匙和门(bfs)
就是走迷宫但会加上门,钥匙(不一定必须拿钥匙)#include&amp;lt;bits/stdc++.h&amp;gt; using namespace std; char mapp[506][506]; int b[506][506][2]; int d[4][2]={0,1,0,-1,1,0,-1,0}; int n,m,x,y; struct nomd { int x,y,s,f; }; void bfs...
【BFS】电子老鼠走迷宫
题目 如下图12×12方格图,找出一条自入口(2,9)到出口(11,8)的最短路径。 输入 第一行为一个数n,表示迷宫大小 第二行为4个数,表示起点和终点 第三起为n*n的矩阵,0表示通路,1表示墙。 输出 第一行为路径(见样例) 第二行为总的步数 思路 (表示不会用循环队列)用一个队列存要搜的节点,搜过的节点删除。从前往后搜,搜到头h==尾t的时候就说明搜完了。还有步...
POJ-2251___走迷宫——解题报告 BFS
原题地址:http://poj.org/problem?id=2251   Dungeon Master Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 41530   Accepted: 15736 Description You are trapped in a 3D dungeo...
bfs队列的算法,走迷宫
problem description 有一个二维迷宫,n行m列,‘s’表示迷宫的起点,‘T’表示迷宫的终点,‘#’表示围墙,‘.’表示通路。 现在从S出发,你不能穿墙,问到达终点T最少需要多少步? 输入格式 第一行输入n,m(1&lt;=n,m&lt;=50)表示迷宫的行列大小。 接下来输入n行字符串表示迷宫。 输出格式 一个整数,表示走出迷宫所需的最小步数,若走不出迷宫则输出 -...
BFS 走迷宫 与STL的低效
Maze(for lab)来源:http://eden.sysu.edu.cn/m/ass/6275/ You are provided a maze(迷宫), and you need to program to find the least steps to walk from the start to the end.And you can only walk in four directi
POJ 3984 BFS走迷宫问题
POJ 3984 BFS走迷宫问题,题目的链接如下: http://poj.org/problem?id=3984A - 迷宫问题
习题:走迷宫2 (java bfs)
package lanqiaobei; import java.util.*; /* 习题:走迷宫2 给你一个n行m列的二维迷宫。'S'表示起点,'T' 表示终点,'#' 表示墙壁,'.' 表示平地。你需要从 'S' 出发走到 'T',每次只能上下左右走动,并且不能走出地图的范围以及不能走到墙壁上。请你计算出走到终点需要走的最少步数。 输入格式 第一行输入n, m表示迷宫大小。(1≤n,m...
【蓝桥杯-bfs队列】走迷宫2
#include&amp;lt;iostream&amp;gt; #include&amp;lt;bits/stdc++.h&amp;gt; using namespace std; #include&amp;lt;queue&amp;gt; int xx[4]={0,0,1,-1}; int yy[4]={1,-1,0,0}; int step[150][150]; struct point { int x,y; point(...
BFS和DFS方法解决走迷宫问题
链接:https://www.nowcoder.com/questionTerminal/6276dbbda7094978b0e9ebb183ba37b9来源:牛客网题目:NowCoder最喜欢游乐场的迷宫游戏,他和小伙伴们比赛谁先走出迷宫。 现在把迷宫的地图给你,你能帮他算出最快走出迷宫需要多少步吗?输入描述:输入包含多组数据。 每组数据包含一个10*10,由“#”和“.”组成的迷宫。其中“#...
计蒜客 走迷宫2(bfs搜索)
计蒜客 走迷宫2#include &amp;lt;bits/stdc++.h&amp;gt; using namespace std; #define maxn 110 int n, m; char board[maxn][maxn]; bool visited[maxn][maxn]; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; bool ok ...
走迷宫--图的搜索(bfs)并记录路径
题目描述: 一个网格迷宫由n行m列的单元格组成,每个单元格要么是空地(用1表示),要么是障碍物(用0来表示)。你的任务是找一条从起点到终点的最短步数和移动序列,其中UDLR表示上下左右操作。任何时候都不能在障碍物格子中,也不能走到迷宫之外。起点和终点保证都是空地。n,m 样例输入: 6 5 11011 10111 10100 10111 11101 11111 样例输出:
hud 1010 走迷宫 搜索—bfs
题目: B - 迷宫问题 Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Submit Status Description 定义一个二维数组:  int maze[5][5] = {  0, 1, 0, 0, 0,  0, 1, 0, 1, 0,  0, 0, 0, 0
华为OJ 走迷宫 Java BFS
class Node{ int x; int y; int prex; //上一个结点的坐标,为方便计算路径 int prey; } public class Maze{ public static void main(String args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){
zcmu 1185: 走迷宫(bfs板子)
【题目】 1185: 走迷宫 Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 354  Solved: 140 [Submit][Status][Web Board] Description 给一张个迷宫,问能否从起点走到终点,只能往上下左右走,不能斜着走 Input 多组测试数据,每组第一行两个正整数,分别为n和m 表示n这个迷宫有n...
POJ 3984 走迷宫(BFS模板题)
Description 定义一个二维数组: int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。 Input 一个5 × ...
地牢逃脱-网易python(走迷宫BFS)
题目描述 给定一个 n 行 m 列的地牢,其中 ‘.’ 表示可以通行的位置,’X’ 表示不可通行的障碍,牛牛从 (x0 , y0 ) 位置出发,遍历这个地牢,和一般的游戏所不同的是,他每一步只能按照一些指定的步长遍历地牢,要求每一步都不可以超过地牢的边界,也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下,他需要多少步才可以离开这个地牢。 输入描述: 每个输入包含
BFS DFS (2) 走迷宫 炸弹人
1.走迷宫迷宫的行n和列m不超过50 广度优先搜索(Breadth First Search, BFS) 用队列模拟这个过程#include<stdio.h>struct note{ int x; int y; int s; }; int main(){ struct note que[2501]; int book[51][51]={0}; in
迷宫(bfs)
链接:https://ac.nowcoder.com/acm/contest/332/J 来源:牛客网   时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld 题目描述 你在一个 n 行 m 列的网格迷宫中,迷宫的每一格要么为空,要么有一个障碍。 你当前在第 r 行第 c 列(保证该格子为空)。每...
BFS之迷宫
给定一个n*m大小的迷宫,其中*代表不可通过的墙壁,而‘.代表平地,S表示起点,T表示终点。移动过程中,如果当前位置是(x,y)(下标从0开始),且每次只能前往上下左右四个位置的平地,求从起点S到达终点T的最少步数。 样例: ..... .*.*. .*S*. .***. ...T* 在上面样例中,S的坐标为(2,2),T的坐标为(4,3)。 #include&amp;lt;cstdio...
走迷宫
#include using namespace std; #include #define N 10 struct Point { size_t _row; size_t _col; }; Point entry = {2,0}; stack s; void InitMain(int array[][N],int size)//初
相关热词 c# 标准差 计算 c#siki第五季 c#入门推荐书 c# 解码海康数据流 c# xml的遍历循环 c# 取 查看源码没有的 c#解决高并发 委托 c#日期转化为字符串 c# 显示问号 c# 字典对象池