0
\$\begingroup\$

I have applied a DFS solution for to check finding path if exist from beginning point to the end point.

OA: Given 2d array, check if there is path from one beginning point to given endpoint in the matrix

public class StartToEnd {

    // OA: Given a 2d matrix with chars and a target string.
    // Check if the matrix contains this target string
    // by only going right or down each time from the beginning point.

    public static void main(String[] argv) {

        int[][] matricesThree ={
                { 0, 0, 0, 1, 0},
                { 1, 0, 1, 1, 1},
                { 0, 0, 0, 1, 0},
                { 1, 0, 0, 0, 0},
                { 0, 0, 1, 0, 0}};

        int[][] matrixNo = {{0, 0, 0, -1, 0},
                            {-1, 0, 0, -1, -1},
                            {0, 0, 0, -1, 0},
                            {-1, 0, -1, 0, 0},
                            {0, 0, -1, 0, 0}};

        int[][] matrixYes = {{0, 0, 0, -1, 0},
                            {-1, 0, 0, -1, -1},
                            { 0, 0, 0, -1, 0},
                            {-1, 0, 0, 0, 0},
                            { 0, 0, -1, 0, 0}};

        int startingRow = 0;
        int startingColumn = 0;

        System.out.println(hasPathDfs(matricesThree, startingRow, startingColumn, matricesThree.length-1, matricesThree[0].length-1));
        System.out.println(hasPathDfs(matrixYes, startingRow, startingColumn, matrixYes.length-1, matrixYes[0].length-1));
        System.out.println(hasPathDfs(matrixNo, startingRow, startingColumn, matrixNo.length-1, matrixNo[0].length-1));
    }

    public static boolean hasPathDfs(int[][] matrix, int row, int column, int endRow, int endColumn){

        if(row == endRow && column == endColumn && matrix[endRow][endColumn] == 0) return true;

        if(row <0 || column <0 || row>=matrix.length|| column>= matrix[row].length || 0 != matrix[row][column] ) return false;

        int temp = matrix[row][column];
        matrix[row][column] = '#';

        boolean flag = hasPathDfs(matrix,row+1,column, endRow, endColumn) ||
                hasPathDfs(matrix,row, column+1, endRow, endColumn) ||
                hasPathDfs(matrix,row-1,column, endRow, endColumn) ||
                hasPathDfs(matrix,row, column-1, endRow, endColumn) ;

        matrix[row][column] = temp;

        return flag;
    }
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ how is beginning point and beginning point defined? What does the assignment in your question have to do with the comments in your class? OA: Given a 2d matrix with chars and a target string. Check if the matrix contains this target string by only going right or down each time from the beginning point. ? \$\endgroup\$ Aug 5 at 6:52
  • \$\begingroup\$ Updated a new version for adapting change in given points \$\endgroup\$ Aug 5 at 7:25
  • \$\begingroup\$ What do you want to achieve? Do you want to "check if the matrix contains this target string by only going right or down each time from the beginning point"? \$\endgroup\$
    – adambene
    Sep 19 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.