Поиск пути в булевой матрице

Question

Проблема, которую я пытаюсь решить, является стандартным вопросом для интервью. С учетом булевой матрицы найдите путь от начальной точки до конечной точки.

The start point is assumed the left top corner 
The finishing point the right bottom corner. 
Only grids with 0 can be moved into. 
No diagonal moves are allowed. 

Вот мой код.

public class PathFinder { 

    public static ArrayList<Pair> dfs(int[][] arr, int row, int col, Pair sp, Pair fp){ 
     int[][] check = new int[row][col]; 
     ArrayList<Pair> path = new ArrayList<>(); 
     dfs(arr, row, col, path, check, sp, fp); 
     return path; 

    } 
    private static void dfs(int[][] arr, int row, int col, ArrayList<Pair> path, int[][] check, Pair sp, Pair fp){ 

     if(sp.getRow() == fp.getRow() && sp.getCol() == fp.getCol()) return; 

     if((sp.getRow() +1 < row) &&(arr[sp.getRow() +1][sp.getCol()] == 0) && (check[sp.getRow()+1][sp.getCol()] == 0)){ 
      check[sp.getRow()+1][sp.getCol()] = 1; 
      path.add(new Pair(sp.getRow()+1, sp.getCol())); 
      dfs(arr, row, col, path, check, new Pair(sp.getRow()+1, sp.getCol()), fp); 
     }else if((sp.getRow() -1 >= 0) &&(arr[sp.getRow() -1][sp.getCol()] == 0) && (check[sp.getRow()-1][sp.getCol()] == 0)){ 
      check[sp.getRow()-1][sp.getCol()] = 1; 
      path.add(new Pair(sp.getRow()-1, sp.getCol())); 
      dfs(arr, row, col, path, check, new Pair(sp.getRow()-1, sp.getCol()), fp); 
     }else if((sp.getCol() +1 < col) &&(arr[sp.getRow()][sp.getCol() +1] == 0) && (check[sp.getRow()][sp.getCol()+1] == 0)){ 
      check[sp.getRow()][sp.getCol()+1] = 1; 
      path.add(new Pair(sp.getRow(), sp.getCol()+1)); 
      dfs(arr, row, col, path, check, new Pair(sp.getRow(), sp.getCol()+1), fp); 
     }else if((sp.getCol() -1 >= 0) &&(arr[sp.getRow()][sp.getCol() -1] == 0) && (check[sp.getRow()][sp.getCol()-1] == 0)) { 
      check[sp.getRow()][sp.getCol() - 1] = 1; 
      path.add(new Pair(sp.getRow(), sp.getCol() - 1)); 
      dfs(arr, row, col, path, check, new Pair(sp.getRow(), sp.getCol() - 1), fp); 
     } 

    } 

    public static void printPath(ArrayList<Pair> list){ 
     for(Iterator itr = list.iterator(); itr.hasNext();){ 
      Pair p = (Pair) itr.next(); 
      System.out.println(p.getRow()+","+p.getCol()); 
     } 
    } 
} 

Вот моя пара

public class Pair { 
    private int row; 
    private int col; 

    public Pair(int row, int col){ 
     this.row = row; 
     this.col = col; 
    } 

    public int getRow(){ 
     return row; 
    } 
    public int getCol(){ 
     return col; 
    } 
} 

И вот мой код вызова.

public class Main { 

    public static void printArray(int[][] arr, int row, int col){ 
     for (int i = 0; i < row; i++) { 
      for (int j = 0; j <col ; j++) { 
       System.out.print(arr[i][j] + " "); 
      } 
      System.out.println(); 
     } 
    } 

    public static void main(String[] args) { 
    // write your code here 
     int row = 5; 
     int col = 7; 
     int[][] matrix = new int[row][col]; 
     matrix[0][1] = 1; 
     matrix[0][3] = 1; 
     matrix[0][5] = 1; 
     matrix[1][1] = 1; 
     matrix[1][3] = 1; 
     matrix[1][6] = 1; 
     matrix[2][1] = 1; 
     matrix[2][2] = 1; 
     matrix[2][6] = 1; 
     matrix[3][3] = 1; 
     matrix[3][5] = 1; 
     matrix[3][6] = 1; 
     matrix[4][0] = 1; 


     printArray(matrix, row, col); 
     ArrayList<Pair> list = PathFinder.dfs(matrix, row, col, new Pair(0,0), new Pair(row-1, col-1)); 
     PathFinder.printPath(list); 
    } 
} 

Проблема в том, что этот поиск по глубине работает только для конкретных случаев. Может кто-то помочь мне изменить код, чтобы он работал для всех случаев. Пожалуйста, имейте в виду, что я не хочу, чтобы вы искали первый поиск.

Answer 1

Это решение с использованием Stack, содержащего подпуты между соединениями и связанным с ним связанным списком Pairs. Уже посещенные поля сохраняются в матрице. В конце матрица снова печатается, где результирующие поля (найденный путь) имеют значение 3, а остальные посещенные поля имеют значение 2.

public class Pair { 
    private int row; 
    private int col; 
    private Pair next; 

    public Pair(int row, int col){ 
     this.row = row; 
     this.col = col; 
    } 

    public int getRow(){ 
     return row; 
    } 
    public int getCol(){ 
     return col; 
    } 

    public Pair getNext() { 
     return next; 
    } 

    public void setNext(Pair next) { 
     this.next = next; 
    } 

} 

/////////////////////// 

import java.util.*; 

public class PathFinder { 

    private int[][] arr; 
    private int rowCount; 
    private int colCount; 
    private Stack<Pair> junctions = new Stack<>(); 

    public PathFinder(int[][] arr){ 
     this.arr = arr; 
     this.rowCount = arr.length; 
     if(rowCount > 0) { 
      this.colCount = arr[0].length; 
     } 
    } 

    public Pair dfs(Pair sp){ 

     int actualRow = sp.getRow(); 
     int actualCol = sp.getCol(); 

     //we where already here 
     arr[actualRow][actualCol] = 2; 

     if(actualRow >= rowCount - 1 && actualCol >= colCount - 1) { 
      //ready 
      return sp; 
     } 

     boolean deeper = actualRow +1 < rowCount && arr[actualRow +1][actualCol] == 0; 
     boolean left = actualCol -1 >= 0 && arr[actualRow][actualCol -1] == 0; 
     boolean right = actualCol +1 < colCount && arr[actualRow][actualCol +1] == 0; 
     boolean up = actualRow -1 >= 0 && arr[actualRow-1][actualCol] == 0; 

     //test for junctions 
     int possibilities = 0; 
     if(left){ 
      possibilities++; 
     } 
     if(right) { 
      possibilities++; 
     } 
     if(deeper){ 
      possibilities++; 
     } 
     if(up){ 
      possibilities++; 
     } 
     if(possibilities > 1) { 
      this.junctions.push(sp); 
     } 

     Pair nextPair; 
     if(deeper){ 
      nextPair = new Pair(actualRow + 1, actualCol); 
     } else if(left) { 
      nextPair = new Pair(actualRow, actualCol-1); 
     } else if(right) { 
      nextPair = new Pair(actualRow, actualCol+1); 
     } else if(up) { 
      nextPair = new Pair(actualRow-1, actualCol); 
     } else { 
      if(!this.junctions.empty()) { 
       Pair lastJunction = this.junctions.pop(); 
       lastJunction.setNext(null); 
       return dfs(lastJunction); 
      } 
      return sp; 
     } 
     sp.setNext(nextPair); 
     return dfs(nextPair); 
    } 
} 

///////////////////// 


public class Main { 

    public static void printArray(int[][] arr, int row, int col){ 
     for (int i = 0; i < row; i++) { 
      for (int j = 0; j <col ; j++) { 
       System.out.print(arr[i][j] + " "); 
      } 
      System.out.println(); 
     } 
    } 

    public static void main(String[] args) { 
     int rowCount = 6; 
     int colCount = 8; 
     int[][] matrix = new int[rowCount][colCount]; 
     matrix[0] = new int[]{0, 1, 0, 1, 0, 0, 0, 1}; 
     matrix[1] = new int[]{0, 1, 0, 0, 0, 1, 0, 0}; 
     matrix[2] = new int[]{0, 0, 0, 1, 0, 1, 0, 0}; 
     matrix[3] = new int[]{0, 1, 1, 1, 1, 0, 0, 1}; 
     matrix[4] = new int[]{0, 0, 0, 0, 0, 1, 0, 0}; 
     matrix[5] = new int[]{0, 1, 0, 1, 0, 0, 1, 0}; 


     printArray(matrix, rowCount, colCount); 
     Pair pair = new Pair(0,0); 
     PathFinder finder = new PathFinder(matrix); 
     Pair finish = finder.dfs(pair); 
     if(finish.getRow() == rowCount-1 && finish.getCol() == colCount -1) { 

      while(pair != null){ 
       System.out.println(pair.getRow()+","+pair.getCol()); 
       matrix[pair.getRow()][pair.getCol()] = 3; 
       pair = pair.getNext(); 
      } 
     } else { 
      System.out.println("no path found"); 
     } 
     printArray(matrix, rowCount, colCount); 
    } 
}