java - 迷宫递归 - 少数输入出错(可能是逻辑错误)

Question

我是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

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

Answer 1

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

而且不需要检查一个 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;
       }