Finden von Pfad in einer booleschen Matrix

Question

Das Problem, das ich versuche zu lösen, ist eine Standard-Interviewfrage. Bei einer booleschen Matrix finde den Pfad vom Startpunkt zum Endpunkt.

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. 

Hier ist mein Code.

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()); 
     } 
    } 
} 

Hier ist mein Pair

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; 
    } 
} 

Und hier ist meine Berufung Code.

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); 
    } 
} 

Das Problem ist, dass diese Tiefensuche zuerst nur für bestimmte Fälle funktioniert. Kann mir jemand helfen, den Code so zu ändern, dass er in allen Fällen funktioniert? Bitte beachten Sie, dass ich keine Suche nach dem ersten Atemzug möchte.

Answer 1

Hier ist eine Lösung mit der Verwendung eines Stack enthält Unterpfade zwischen Junctions und eine selbst implementierte verkettete Liste von Pairs. Die bereits besuchten Felder werden in der Matrix gespeichert. Am Ende wird die Matrix erneut gedruckt, wobei die Ergebnisfelder (gefundener Pfad) den Wert 3 haben und die anderen besuchten Felder den Wert 2 haben.

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); 
    } 
}