该程序实现广度优先算法走迷宫功能,用数字模拟迷宫格子,每格子对应数组maze[][]的一个元素,若该格元素为0表示该格可以穿过,1则不能,最后输出找到的路径,路径用sq[]记录并输出。编译没错但运行抛出如下异常:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at Tuwidely.check(Tuwidely.java:54)
at Tuwidely.search(Tuwidely.java:33)
at Tuwidely.main(Tuwidely.java:62)
请高手帮忙看看阿,在下实在不知道错在哪!
程序如下:class Struct
{
public int x,y,pre;
}
public class Tuwidely
{
int maze[][]={{0,0,0,0,0,0,0,0},{0,1,1,1,1,0,1,0},{0,0,0,0,1,0,1,0},{0,1,0,0,0,0,1,0},
{0,1,0,1,1,0,1,0},{0,1,0,0,0,0,1,1},{0,1,0,0,1,0,0,0},{0,1,1,1,1,1,1,0}};
int fx[]={1,-1,0,0},fy[]={0,0,-1,1};
int qh,qe,i,j,k;
Struct[] sq;
public Tuwidely()
{
sq=new Struct[50];
for(i=0;i<50;i++)
{sq[i]=new Struct();sq[i].x=0;sq[i].y=0;}
}
void search()
{
Tuwidely tu1=new Tuwidely();
qh=0;
maze[0][0]=-1;
sq[0].x=1;sq[0].y=1;
while(qh<=8)
{
for(k=1;k<=4;k++)
{
i=sq[qh].x+fx[k];
j=sq[qh].y+fy[k];
qh++;
if(this.check(i,j)==1)
{
sq[qh].x=i;sq[qh].y=j;
maze[i][j]=-1;
if(sq[qh].x==8&&sq[qh].y==8)
{
for(qh=0;qh<=sq.length-1;qh++)
System.out.print("("+sq[qh].x+","+sq[qh].y+")");
}
System.out.println("No avalible way.");
}
}
}
}
int check(int i,int j)
{
int flag=1;
if(i<1||i>8||j<1||j>8)
flag=0;
if(maze[i][j]==1||maze[i][j]==-1)
flag=0;
return flag;
}
public static void main(String args[])
{
Tuwidely tu2=new Tuwidely();
tu2.search();
}
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at Tuwidely.check(Tuwidely.java:54)
at Tuwidely.search(Tuwidely.java:33)
at Tuwidely.main(Tuwidely.java:62)
请高手帮忙看看阿,在下实在不知道错在哪!
程序如下:class Struct
{
public int x,y,pre;
}
public class Tuwidely
{
int maze[][]={{0,0,0,0,0,0,0,0},{0,1,1,1,1,0,1,0},{0,0,0,0,1,0,1,0},{0,1,0,0,0,0,1,0},
{0,1,0,1,1,0,1,0},{0,1,0,0,0,0,1,1},{0,1,0,0,1,0,0,0},{0,1,1,1,1,1,1,0}};
int fx[]={1,-1,0,0},fy[]={0,0,-1,1};
int qh,qe,i,j,k;
Struct[] sq;
public Tuwidely()
{
sq=new Struct[50];
for(i=0;i<50;i++)
{sq[i]=new Struct();sq[i].x=0;sq[i].y=0;}
}
void search()
{
Tuwidely tu1=new Tuwidely();
qh=0;
maze[0][0]=-1;
sq[0].x=1;sq[0].y=1;
while(qh<=8)
{
for(k=1;k<=4;k++)
{
i=sq[qh].x+fx[k];
j=sq[qh].y+fy[k];
qh++;
if(this.check(i,j)==1)
{
sq[qh].x=i;sq[qh].y=j;
maze[i][j]=-1;
if(sq[qh].x==8&&sq[qh].y==8)
{
for(qh=0;qh<=sq.length-1;qh++)
System.out.print("("+sq[qh].x+","+sq[qh].y+")");
}
System.out.println("No avalible way.");
}
}
}
}
int check(int i,int j)
{
int flag=1;
if(i<1||i>8||j<1||j>8)
flag=0;
if(maze[i][j]==1||maze[i][j]==-1)
flag=0;
return flag;
}
public static void main(String args[])
{
Tuwidely tu2=new Tuwidely();
tu2.search();
}
}
最大下标是7 java.lang.ArrayIndexOutOfBoundsException异常很明确了.
int fx[] = {1, -1, 0, 0}, fy[] = {0, 0, -1, 1};
和
for (k = 1; k <= 4; k++) {
i = sq[qh].x + fx[k];
j = sq[qh].y + fy[k];
qh++;
当k=4的时候,fx[k]和fy[k]就会溢出
int check(int i, int j) {
int flag = 1;
if (i < 1 || i > 8 || j < 1 || j > 8) {
flag = 0;
}
if (maze[i][j] == 1 || maze[i][j] == -1) {
flag = 0;
}
return flag;
}当i与j越界的时候,maze[i][j]就越界了对广度优先算法 不是很熟悉,和楼主一起学习了
package test;
/**该程序实现广度优先算法走迷宫功能,用数字模拟迷宫格子,每格子对应数组maze[][]的一个元素,
* 若该格元素为0表示该格可以穿过,1则不能,最后输出找到的路径,路径用sq[]记录并输出。编译没错但运行抛出如下异常:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at Tuwidely.check(Tuwidely.java:54)
at Tuwidely.search(Tuwidely.java:33)
at Tuwidely.main(Tuwidely.java:62)
请高手帮忙看看阿,在下实在不知道错在哪!
*/class Struct {
public int x, y, pre;//该点的位置坐标和走过的上一邻接点的记录偏移量
}public class Tuwidely {
int maze[][] = {//迷宫
{
0, 0, 0, 0, 0, 0, 0, 0}, {
0, 1, 1, 1, 1, 0, 1, 0}, {
0, 0, 0, 0, 1, 0, 1, 0}, {
0, 1, 0, 0, 0, 0, 1, 0}, {
0, 1, 0, 1, 1, 0, 1, 0}, {
0, 1, 0, 0, 0, 0, 1, 1}, {
0, 1, 0, 0, 1, 0, 0, 0}, {
0, 1, 1, 1, 1, 1, 1, 0}
};
int i, j;
int fx[] = {
1, -1, 0, 0}, fy[] = {
0, 0, -1, 1};//一个点的相邻四个点的坐标与该点坐标的相对位置
Struct[] sq;
public Tuwidely() {
sq = new Struct[64];//记录走过的点,应该大于等于所有的点数,原先为sq = new Struct[50];
for (int i = 0; i < 64; i++) {//初始化所有的点
sq[i] = new Struct();
sq[i].x = -1;
sq[i].y = -1;
sq[i].pre = -2;
}
}
//从源点开始访问
void search(int initialx, int initialy) {
sq[0].x = initialx;
sq[0].y = initialy;//记录访问过的点,此处为源点,从(0,0)开始记录,那么最后的点为(7,7)
sq[0].pre = -1;
boolean found = visitLinJieDian(0);
if(!found){
System.out.println("No avalible way.");
}
}
//访问点的邻接点
boolean visitLinJieDian(int initialqh){
for (int k = 0; k < 4; k++) {//访问该点的四个相邻的点
i = sq[initialqh].x + fx[k];//得到该点一个邻接点的x坐标
j = sq[initialqh].y + fy[k];//得到该点一个邻接点的y坐标
//首先判断该点是否走过,如果没有走过,则走下去,如果走过,则选另外的邻接点走下去
boolean visited = false;
for(int count = 0; count < sq.length; count++){
if(sq[count].pre == -2){
break;
}
if(sq[count].x == i && sq[count].y == j){//已经走过
visited = true;
break;
}
}
if(!visited){//没有走过,则走下去
if (this.check(i, j) == 1) { //该邻接点可以走通,值为0
initialqh++;
sq[initialqh].x = i; //记录该邻接点的坐标
sq[initialqh].y = j;
sq[initialqh].pre= initialqh - 1; //记录走向该邻接点的上一点的偏移量
if (sq[initialqh].x == 7 && sq[initialqh].y == 7) { //到达终点
for (int seq = 0; seq < sq.length && seq < initialqh + 1; seq++) { //打印路径信息
System.out.print("(" + sq[seq].x + "," + sq[seq].y + ")");
}
return true;
} //end if (sq[qh].x == 7 && sq[qh].y == 7)
//如果没有走到终点,则访问该点的邻接点
visitLinJieDian(initialqh);
} //end if (this.check(i, j) == 1)
}//end if(!visited){
}//end for (k = 0; k < 4; k++)
//如果四个邻接点都访问过了,那么就倒回到前面访问过的节点
initialqh = initialqh -1;
visitLinJieDian(initialqh);
return false;
} int check(int i, int j) {
int flag = 1;
if (i < 0 || i > 7 || j < 0 || j > 7) {//如果越界,则直接返回
flag = 0;
return flag;
}
if (maze[i][j] == 1) {//如果不能够走通,则返回
flag = 0;
return flag;
}
return flag;//能够走通,则正确返回
} public static void main(String args[]) {
Tuwidely tu2 = new Tuwidely();
tu2.search(0, 0);//从(0,0)开始走
}
}
/**广度优先遍历(Breadth-FirstTraversal)1、广度优先遍历的递归定义
设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点,则广度优先遍历可以定义为:首先访问出发点v,接着依次访问v的所有邻接点w1,w2,…,wt,然后再依次访问与wl,w2,…,wt邻接的所有未曾访问过的顶点。依此类推,直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。
若G是连通图,则遍历完成;否则,在图C中另选一个尚未访问的顶点作为新源点继续上述的搜索过程,直至G中所有顶点均已被访问为止。
广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索,故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。2、广度优先搜索过程
在广度优先搜索过程中,设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x1,x2,…,xs和y1,y2,…,yt。
为确保先访问的顶点其邻接点亦先被访问,在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时,这两个顶点相继入队。此后,当x和y相继出队时,我们分别从x和y出发搜索其邻接点x1,x2,…,xs和y1,y2,…,yt,对其中未访者进行访问并将其人队。这种方法是将每个已访问的顶点人队,故保证了每个顶点至多只有一次人队。3、广度优先搜索算法
(1)邻接表表示图的广度优先搜索算法
void BFS(ALGraph*G,int k)
{// 以vk为源点对用邻接表表示的图G进行广度优先搜索
int i;
CirQueue Q; //须将队列定义中DataType改为int
EdgeNode *p;
InitQueue(&Q);//队列初始化
//访问源点vk
printf("visit vertex:%e",G->adjlist[k].vertex);
visited[k]=TRUE;
EnQueue(&Q,k);//vk已访问,将其人队。(实际上是将其序号人队)
while(!QueueEmpty(&Q)){//队非空则执行
i=DeQueue(&Q); //相当于vi出队
p=G->adjlist[i].firstedge; //取vi的边表头指针
while(p){//依次搜索vi的邻接点vj(令p->adjvex=j)
if(!visited[p->adivex]){ //若vj未访问过
printf("visitvertex:%c",C->adjlistlp->adjvex].vertex); //访问vj
visited[p->adjvex]=TRUE;
EnQueue(&Q,p->adjvex);//访问过的vj人队
}//endif
p=p->next;//找vi的下一邻接点
}//endwhile
}//endwhile
}//end of BFS *
*/楼主的算法也有点问题
我写了一个,虽然可以完成任务,但是堆栈溢出,可能是迭代的太厉害了,哪位高手可以修改一下,谢谢!