java - 在 boolean 矩阵中查找路径

Question

我试图解决的问题是一个标准的面试问题。给定一个 boolean 矩阵，找到从起点到终点的路径。

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