Facebook
From yoben, 3 Years ago, written in Java.
Embed
Download Paste or View Raw
Hits: 145
  1. class MazePath {
  2.  
  3.         boolean isPath(int[][] matrix, int ROWS, int COLS, int row, int col) {
  4.                 if(matrix[row][col] == 9){
  5.                         return true;
  6.                 }
  7.  
  8.                 // visit this path
  9.                 matrix[row][col] = 2;
  10.                 boolean exist = false;
  11.  
  12.                 // right
  13.                 if(!exist && col+ 1 < COLS && (matrix[row][col+1] == 1 || matrix[row][col+1] == 9)) {
  14.                         exist = isPath(matrix, ROWS, COLS, row, col+1);
  15.                 }
  16.  
  17.  
  18.                 // down
  19.                 if(!exist && row+1 < ROWS && (matrix[row+1][col] == 1 || matrix[row+1][col] == 9)) {
  20.                         exist = isPath(matrix, ROWS, COLS, row+1, col);
  21.                 }
  22.  
  23.                
  24.                 // left
  25.                 if(!exist && col-1 >=0 && (matrix[row][col-1] == 1 || matrix[row][col-1] == 9)) {
  26.                         exist = isPath(matrix, ROWS, COLS, row, col-1);
  27.                 }
  28.                
  29.                 // top
  30.                 if(!exist && row-1 >=0 && (matrix[row-1][col] == 1 || matrix[row-1][col] == 9)) {
  31.                         exist = isPath(matrix, ROWS, COLS, row-1, col);
  32.                 }
  33.  
  34.                 // un-visit this path
  35.                 matrix[row][col] = 1;
  36.                 return exist;
  37.         }
  38.         public static void main(String[] args) {
  39.                 MazePath mcr = new MazePath();
  40.                
  41.                 int matrix[][] = {{1, 0, 1, 1, 1, 0, 0, 1},
  42.                                                   {1, 0, 0, 0, 1, 1, 1, 1},
  43.                                                   {1, 0, 0, 0, 0, 0, 0, 0},
  44.                                                   {1, 0, 1, 0, 9, 0, 1, 1},
  45.                                                   {1, 1, 1, 0, 1, 0, 0, 1},
  46.                                                   {1, 0, 1, 0, 1, 1, 0, 1},
  47.                                                   {1, 0, 0, 0, 0, 1, 0, 1},
  48.                                                   {1, 1, 1, 1, 1, 1, 1, 1}};
  49.                
  50.                
  51.                 System.out.println(mcr.isPath(matrix, matrix.length, matrix[0].length, 0, 0));
  52.         }
  53.  
  54. }