bfs走迷宫java代码 java走迷宫代码解析

挑战程序设计竞赛上的问题，迷宫的最短路径

typedef pairint, int p;

这就是pbfs走迷宫java代码的定义啊bfs走迷宫java代码，p是一个类型

至于 pair 还是学一下比较好，很常用bfs走迷宫java代码的。

pair bfs走迷宫java代码的定义大概是这样bfs走迷宫java代码：

templateclass _T1, class _T2

struct pair

{

    _T1 first;

    _T2 second;

    // ....

}

相关问答

Q1: 谁帮我写个迷宫求解的程序啊，数据结构，用链表写，，，，急求！！！

代码给你，但是你确定你这个迷宫有解吗？好像没有出来的路径啊

#includestdio.h

#includestdlib.h

#define M 8

#define N 11

struct mark //定义迷宫内点的坐标类型

{

int x;

int y;

};

struct Element //"恋"栈元素，嘿嘿。。

{

int x,y; //x行,y列

int d; //d下一步的方向

};

typedef struct LStack //链栈

{

Element elem;

struct LStack *next;

}*PLStack;

/*************栈函数****************/

int InitStack(PLStack S)//构造空栈

{

S=NULL;

return 1;

}

int StackEmpty(PLStack S)//判断栈是否为空

{

if(S==NULL)

return 1;

else

return 0;

}

int Push(PLStack S, Element e)//压入新数据元素

{

PLStack p;

p=(PLStack)malloc(sizeof(LStack));

p-elem=e;

p-next=S;

S=p;

return 1;

}

int Pop(PLStack S,Element e) //栈顶元素出栈

{

PLStack p;

if(!StackEmpty(S))

{

e=S-elem;

p=S;

S=S-next;

free(p);

return 1;

}

else

return 0;

}

/***************求迷宫路径函数***********************/

void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])

{

int i,j,d;int a,b;

Element elem,e;

PLStack S1, S2;

InitStack(S1);

InitStack(S2);

maze[start.x][start.y]=2; //入口点作上标记

elem.x=start.x;

elem.y=start.y;

elem.d=-1; //开始为-1

Push(S1,elem);

while(!StackEmpty(S1)) //栈不为空 有路径可走

{

Pop(S1,elem);

i=elem.x;

j=elem.y;

d=elem.d+1; //下一个方向

while(d4) //试探东南西北各个方向

{

a=i+diradd[d][0];

b=j+diradd[d][1];

if(a==end.x b==end.y maze[a][b]==0) //如果到了出口

{

elem.x=i;

elem.y=j;

elem.d=d;

Push(S1,elem);

elem.x=a;

elem.y=b;

elem.d=886; //方向输出为-1 判断是否到了出口

Push(S1,elem);

printf("\n0=东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n");

while(S1) //逆置序列 并输出迷宫路径序列

{

Pop(S1,e);

Push(S2,e);

}

while(S2)

{

Pop(S2,e);

printf("--(%d,%d,%d)",e.x,e.y,e.d);

}

return; //跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴

}

if(maze[a][b]==0) //找到可以前进的非出口的点

{

maze[a][b]=2; //标记走过此点

elem.x=i;

elem.y=j;

elem.d=d;

Push(S1,elem); //当前位置入栈

i=a; //下一点转化为当前点

j=b;

d=-1;

}

d++;

}

}

printf("没有找到可以走出此迷宫的路径\n");

}

void main()

{

int maze[M][N]={ {1,1,1,1,1,1,1,1,1,1,1},

{1,0,1,0,0,1,1,1,0,0,1},

{1,0,0,0,0,0,1,0,0,0,1},

{1,0,1,1,1,0,0,0,1,1,1},

{1,0,0,0,1,0,1,1,0,1,1},

{1,1,0,0,1,0,1,1,0,0,1},

{1,1,1,0,0,0,0,0,0,0,1},

{1,1,1,1,1,1,1,1,1,1,1}};

struct mark start,end; //start,end入口和出口的坐标

int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为东西南北 [/M]

//起点(1,1)

start.x=1;

start.y=1;

//终点(7,10)

end.x=7;

end.y=10;

MazePath(start,end,maze,add); //find path

system("PAUSE");

}

Q2: 广度优先搜索代码。也就是迷宫问题

这个bfs问题很容易掌握bfs走迷宫java代码，是一种基础算法

首先记得添加queue队列容器

建立一个队列容器

之后 往里面压迷宫bfs走迷宫java代码的起点 （通常是结构体）

之后在循环中加判断 判断当前取出bfs走迷宫java代码的点是否能走bfs走迷宫java代码，如果可以bfs走迷宫java代码，压入它四周的四个点（视题目情况 不一定是四周） 再进行下一轮循环

循环体一般是while (!q.empty())

循环一开始一般是 p=q.front(); //取出第一个元素

q.pop(); //删除第一个元素

Q3: 深度优先和广度优先 的区别 ，用法。

1、主体区别

深度优先搜索是一种在开发爬虫早期使用较多bfs走迷宫java代码的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件)。

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一bfs走迷宫java代码，这一算法也是很多重要的图的算法的原型。

2、算法区别

深度优先搜索是每次从栈中弹出一个元素bfs走迷宫java代码，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。

广度优先搜索是每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。

3、用法

广度优先属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

深度优先即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。

扩展资料bfs走迷宫java代码：

实际应用

BFS在求解最短路径或者最短步数上有很多的应用，应用最多的是在走迷宫上，单独写代码有点泛化，取来自九度1335闯迷宫一例说明，并给出C++/Java的具体实现。

在一个n*n的矩阵里走，从原点（0,0）开始走到终点（n-1,n-1），只能上下左右4个方向走，只能在给定的矩阵里走，求最短步数。n*n是01矩阵，0代表该格子没有障碍，为1表示有障碍物。

int mazeArr[maxn][maxn]; //表示的是01矩阵int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4个方向，int visit[maxn][maxn]; //表示该点是否被访问过，防止回溯，回溯很耗时。核心代码。基本上所有的BFS问题都可以使用类似的代码来解决。

参考资料来源：百度百科-广度优化

参考资料来源：百度百科-深度优化

Q4: 新手第一次做ACM走迷宫，求指导

P p=que.front();que.pop;

不应该是

P p=que.front();que.pop()；

你的程序没报错吗？

你说没输出，是指死循环了，还是什么问题？

Q5: BFS求源代码及思路？

1、算法用途bfs走迷宫java代码：

是一种图像搜索演算法。用于遍历图中的节点，有些类似于树的深度优先遍历。这里唯一的问题是，与树不同，图形可能包含循环，因此我们可能会再次来到同一节点。

2、主要思想：

主要借助一个队列、一个布尔类型数组、邻接矩阵完成（判断一个点是否查看过，用于避免重复到达同一个点，造成死循环等），先将各点以及各点的关系存入邻接矩阵。

再从第一个点开始，将一个点存入队列，然后在邻接表中找到他的相邻点，存入队列，每次pop出队列头部并将其打印出来（文字有些抽象，实际过程很简单），整个过程有点像往水中投入石子水花散开。

（邻接表是表示bfs走迷宫java代码了图中与每一个顶点相邻的边集的集合，这里的集合指的是无序集）

3、代码（java）：

(以上图为例的代码）

1 import java.util.*; 2  3 //This class represents a directed graph using adjacency list

4 //representation  5 class Graph1 { 6     private static int V; // No. of vertices 7     private LinkedListInteger a Lists 8  9     // Constructor10     Graph1(int v) {11         V = v;12         adj = new LinkedList[v];13         for (int i = 0; i v; ++i)14             adj[i] = new LinkedList();15     }16 17     // Function to add an edge into the graph18     void addEdge(int v, int w) {19         adj[v].add(w);20     }21 22     // prints BFS traversal from a given source s23     public void BFS() {24         // Mark all the vertices as not visited(By default25         // set as false)26         boolean visited[] = new boolean[V];27         // Create a queue for BFS28         LinkedListInteger queue = new LinkedListInteger();29 30         for (int i = 0; i V; i++) {31             if (!visited[i]) {32                 BFSUtil(i, visited, queue);33             }34         }35     }36 37     public void BFSUtil(int s, boolean visited[], LinkedListInteger queue) {38         // Mark the current node as visited and enqueue it39         visited[s] = true;40         queue.add(s);41 42         while (queue.size() != 0) {43             // Dequeue a vertex from queue and print it44             s = queue.poll();45             System.out.print(s + " ");46 47             // Get all adjacent vertices of the dequeued vertex s48             // If a adjacent has not been visited, then mark it49             // visited and enqueue it50             IteratorInteger i = adj[s].listIterator();51             while (i.hasNext()) {52                 int n = i.next();53                 if (!visited[n]) {54                     visited[n] = true;55                     queue.add(n);56                 }57             }58         }59     }60 61     // Driver method to62     public static void main(String args[]) {63         Graph1 g = new Graph1(4);64 65         g.addEdge(0, 1);66         g.addEdge(0, 2);67         g.addEdge(1, 2);68         g.addEdge(2, 0);69         g.addEdge(2, 3);70         g.addEdge(3, 3);71 72         System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)");73         g.BFS();74     }75 }

4、复杂度分析：

算法借助了一个邻接表和队列，故它的空问复杂度为O(V）。 遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用结构。 邻接表表示时，查找所有顶点的邻接点所需时间为O(E)，访问顶点的邻接点所花时间为O（V）,此时，总的时间复杂度为O(V+E)。

关于bfs走迷宫java代码和java走迷宫代码解析的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。