(Easy) BackTracking- Rat in a Maze. LeetCode

发布时间：2020-12-14 05:08:05 所属栏目：大数据来源：网络整理

导读：Description: A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e.,maze[0][0] and destination block is lower rightmost block i.e.,maze[N-1][N-1]. A rat starts from source and has to reach the d

Description:

A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e.,maze[0][0] and destination block is lower rightmost block i.e.,maze[N-1][N-1]. A rat starts from source and has to reach the destination. The rat can move only in two directions: forward and down.
In the maze matrix,0 means the block is a dead end and 1 means the block can be used in the path from source to destination. Note that this is a simple version of the typical Maze problem. For example,a more complex version can be that the rat can move in 4 directions and a more complex version can be with a limited number of moves.

Following is an example maze.

 Gray blocks are dead ends (value = 0).

Following is binary matrix representation of the above maze.

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

Following is a maze with highlighted solution path.

Following is the solution matrix (output of program) for the above input matrx.

                {1,0}
                {0,1}
 All enteries in solution path are marked as 1.

Solution:

class Main {
  public static void main(String[] args) {
     Main rat = new Main(); 
        int maze[][] = { { 1,0 },{ 1,1 },{ 0,1 } }; 
       
       int [][] sol = new int[4][4];
      if(rat.CheckSol(maze,0,sol)){
      
       rat.printSolution(sol); 
      }
         
  }

  void printSolution(int sol[][]) 
    { 
        for (int i = 0; i < sol.length; i++) { 
            for (int j = 0; j < sol[0].length; j++) 
                System.out.print(" " + sol[i][j] + " "); 
            System.out.println(); 
        } 
    } 
  
  boolean CheckSol(int[][]maze,int i,int j,int[][] sol){
    //goal
    if(i==maze.length-1 && j ==maze[0].length-1){
      sol[i][j]=1;
      return true;
    }
    if(isSafe(maze,i,j)){
       sol[i][j] = 1; 
      if(CheckSol(maze,i+1,j,sol)){
        return true;
      }

      if(CheckSol(maze,j+1,sol)){
        return true;
      }
      sol[i][j]=0;
      return false;
    }

    

    return false;
  }
  boolean isSafe(int[][] maze,int j ){
    if((i>=0 &&i<maze.length )&& (j>=0&&j<maze[0].length)&&maze[i][j]==1){
      return true;
    }
    return false;
  }


}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!