5

我是java初学者。我一直在研究一个迷宫问题，试图通过递归来解决它。我编写的代码似乎适用于少数输入而不是其他输入。输入是一个由 0 和 1 组成的迷宫。# 是开始，@ 是出口。0 是墙，1 是开放的。输出将是从 # 到 @ 的跳数。虽然我正在通过递归解决问题，但我的逻辑一定有问题。请让我知道我错在哪里。

课堂练习次数

 import java.util.Scanner;

 class practisenumwords {
 public static void main(String[] args){
 Scanner in=new Scanner(System.in);
 int r=in.nextInt();
 int c=in.nextInt();
 maze maz=new maze(r,c);                    /*input in string copied to array*/
 char[] ch;                                        
 ch = "00000000111111101111011001101@#11100".toCharArray();  
 int l=0;
 for(int i=0;i<r;i++)
   {
    for(int j=0;j<c;j++)                /*initialising the maze elements*/
    {                               
     maz.m[i][j]=new cells();
     maz.m[i][j].c=ch[l];
     maz.m[i][j].row=i;
     maz.m[i][j].col=j;
     l++;
    }
  }
for(int i=0;i<r;i++)                             /*print the input maze */
  {
    for(int j=0;j<c;j++)
    {
    System.out.print(""+maz.m[i][j].c);
  }
  System.out.println();
}

maz.escape();
maz.find(maz.startx,maz.starty,maz.hops);
}
}

类细胞

class cells {
char c;
int row;
int col;
boolean done=false;                 /*initially all cells are unvisited*/ 
}

类迷宫

class maze{                       
maze (int a,int b){                                
    rows=a;
    cols=b;
    m=new cells[rows][cols];
}
int rows;
int cols;
cells[][] m;
int startx,starty;
int hops=0;
void escape()
{
    for(int i=0;i<rows;i++)
    {
       for(int j=0;j<cols;j++)
       {
        if(m[i][j].c=='#') 
         {
               startx=i;
               starty=j;
               System.out.println(startx+" "+starty);
         }
       }
    }
}
void find(int x,int y,int h)
{    
    if   ((x+1<rows && m[x+1][y].c=='@'   &&  m[x+1][y].done!=true) 
        ||(x-1>=0   && m[x-1][y].c=='@'   &&  m[x-1][y].done!=true)
        ||(y+1<cols && m[x][y+1].c=='@'   &&  m[x][y+1].done!=true)   
        ||(y-1>=0   && m[x][y-1].c=='@'   &&  m[x][y-1].done!=true)){
        h++;
        System.out.println(h);   
         }
      else
       {  
        if(x-1>=0   &&  m[x-1][y].c=='1' && m[x-1][y].done!=true){   /*north cell*/
                    m[x][y].done=true;
                    h++;
                    find(x-1,y,h);
        }
        if(x+1<rows && m[x+1][y].c=='1'  && m[x+1][y].done!=true){   /*south cell*/
                     m[x][y].done=true;
                     h++;
                     find(x+1,y,h);
        }
        if(y+1<cols && m[x][y+1].c=='1'  && m[x][y+1].done!=true){   /*east cell*/
                    m[x][y].done=true;
                    h++;
                    find(x,y+1,h);
        }
        if(y-1>=0 && m[x][y-1].c=='1'    && m[x][y-1].done!=true){   /*west cell*/
                    m[x][y].done=true;
                    h++;
                    find(x,y-1,h);
        }
       }   
      }
    }

现在，我得到正确的输入输出作为程序中的 1。

000000
001111
111011
110110
01101@
#11100

output- 12 （获得正确的输出）

00@000
001111
111011
110110
011011
#11100

output- 7（获得正确的输出）

但不适用于其他输入，例如

0 0 0 0 @ 0
0 1 0 1 1 0
1 1 1 1 0 1
0 1 0 1 0 0
0 0 # 1 1 1
0 1 1 0 0 1

正确输出 - 6 获得输出 -7

输出也随着检查相邻单元格的顺序而变化。

4

3 回答 3

2

老实说，我会以不同的方式实现您的递归函数：

并且不需要检查 bool 值是否是!= true,!boolValue就可以了。

int find(int x,int y,int h)
{    
    int result = -1;
    if   ((x+1<rows && m[x+1][y].c=='@'   &&  !m[x+1][y].done) 
        ||(x-1>=0   && m[x-1][y].c=='@'   &&  !m[x-1][y].done)
        ||(y+1<cols && m[x][y+1].c=='@'   &&  !m[x][y+1].done)   
        ||(y-1>=0   && m[x][y-1].c=='@'   &&  !m[x][y-1].done)){   
        return h + 1;
         }
      else
       {

        if(x-1>=0   &&  m[x-1][y].c=='1' && !m[x-1][y].done){   /*north cell*/
                   m[x][y].done=true;

                   result = find(x-1,y,h + 1)
                   if (result > -1) {
                       return result; 
                   }
                   m[x][y].done=false;
        }

以同样的方式实现其他三个方向，如果没有找到解决方案，结果应该仍然是-1。

        return result;
       }
于 2012-10-10T17:03:22.557 回答
0

在快速阅读中，我注意到：

if(...) {
    ...
    h++;
    find(x-1,y,h);
}

对于每个 if 块。

当第一个 if 条件满足时，在第二个 if 块内 h == h+2，第三个和第四个 if 块也是如此

也许你应该写：

if(...) {
    ...
    // h++;
    find(x-1,y,h+1);
}
于 2012-10-10T14:33:34.203 回答
0 
int find(int x, int y, int h) {
    if ((x + 1 < rows && m[x + 1][y].c == '@' && m[x + 1][y].done != true)
            || (x - 1 >= 0 && m[x - 1][y].c == '@' && m[x - 1][y].done != true)
            || (y + 1 < cols && m[x][y + 1].c == '@' && m[x][y + 1].done != true)
            || (y - 1 >= 0 && m[x][y - 1].c == '@' && m[x][y - 1].done != true)) {
        h++;
        finish = true;
        return h;
    } else {
        if (x - 1 >= 0 && m[x - 1][y].c == '1' && m[x - 1][y].done != true
                && !finish) { /* north cell */
            m[x][y].done = true;
            int temp = find(x - 1, y, h);
            if (temp != 0)
                h = temp + 1;
            return h;

        }
        if (x + 1 < rows && m[x + 1][y].c == '1'
                && m[x + 1][y].done != true && !finish) { /* south cell */
            m[x][y].done = true;
            int temp = find(x + 1, y, h);
            if (temp != 0)
                h = temp + 1;
            return h;

        }
        if (y + 1 < cols && m[x][y + 1].c == '1'
                && m[x][y + 1].done != true && !finish) { /* east cell */
            m[x][y].done = true;

            int temp = find(x, y + 1, h);
            if (temp != 0)
                h = temp + 1;
            return h;

        }
        if (y - 1 >= 0 && m[x][y - 1].c == '1' && m[x][y - 1].done != true
                && !finish) { /* west cell */
            m[x][y].done = true;

            int temp = find(x, y - 1, h);
            if (temp != 0) {
                h = temp + 1;
            }
            return h;
        }
        return 0;
    }
}

还包括一个布尔完成 = false; 在你的迷宫课上。并更改主函数的返回

    maz.hops = maz.find(maz.startx, maz.starty, maz.hops);
    System.out.println(maz.hops);
于 2012-10-10T16:44:06.583 回答