请高手看看错在哪

    该程序实现广度优先算法走迷宫功能，用数字模拟迷宫格子，每格子对应数组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();
     }
}

解决方案 »

  1.   

    while(qh <=8) maze[][] 应该是 int [7][7]
    最大下标是7 java.lang.ArrayIndexOutOfBoundsException异常很明确了.
      

  2.   

    问题在于
    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]就会溢出
      

  3.   

    还有
    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]就越界了对广度优先算法 不是很熟悉，和楼主一起学习了
      

  4.   


    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  * 
     */楼主的算法也有点问题
    我写了一个，虽然可以完成任务，但是堆栈溢出，可能是迭代的太厉害了，哪位高手可以修改一下，谢谢！