0
\$\begingroup\$

I have implemented the following question and looking forward for the reviews.

Question Explanation : We have a two-dimensional board game involving snakes. The board has two types of squares on it: +'s represent impassable squares where snakes cannot go, and 0's represent squares through which snakes can move. Snakes can only enter on the edges of the board, and each snake can move in only one direction. We'd like to find the places where a snake can pass through the entire board, moving in a straight line.

Here is an example board:

col-->        0  1  2  3  4  5  6
           +----------------------
row      0 |  +  +  +  0  +  0  0
 |       1 |  0  0  0  0  0  0  0
 |       2 |  0  0  +  0  0  0  0
 v       3 |  0  0  0  0  +  0  0
         4 |  +  +  +  0  0  0  +

Write a function that takes a rectangular board with only +'s and 0's, and returns two collections:

  • one containing all of the row numbers whose row is completely passable by snakes, and
  • the other containing all of the column numbers where the column is completely passable by snakes.

Complexity Analysis:

r: number of rows in the board c: number of columns in the board

straightBoard1 = [['+', '+', '+', '0', '+', '0', '0'],
                  ['0', '0', '0', '0', '0', '0', '0'],
                  ['0', '0', '+', '0', '0', '0', '0'],
                  ['0', '0', '0', '0', '+', '0', '0'],
                  ['+', '+', '+', '0', '0', '0', '+']]

findPassableLanes(straightBoard1) // = Rows: [1], Columns: [3, 5]

straightBoard2 = [['+', '+', '+', '0', '+', '0', '0'],
                  ['0', '0', '0', '0', '0', '+', '0'],
                  ['0', '0', '+', '0', '0', '0', '0'],
                  ['0', '0', '0', '0', '+', '0', '0'],
                  ['+', '+', '+', '0', '0', '0', '+']]

findPassableLanes(straightBoard2) // = Rows: [], Columns: [3]

straightBoard3 = [['+', '+', '+', '0', '+', '0', '0'],
                  ['0', '0', '0', '0', '0', '0', '0'],
                  ['0', '0', '+', '+', '0', '+', '0'],
                  ['0', '0', '0', '0', '+', '0', '0'],
                  ['+', '+', '+', '0', '0', '0', '+']]

findPassableLanes(straightBoard3) // = Rows: [1], Columns: []

straightBoard4 = [['+']]
findPassableLanes(straightBoard4) // = Rows: [], Columns: []

Solution Class

import java.util.ArrayList;

public class MazePathFinder {

    public static void main(String[] argv) {
        
        char[][] straightBoard1 = {{'+', '+', '+', '0', '+', '0', '0'},
                {'0', '0', '0', '0', '0', '0', '0'},
                {'0', '0', '+', '0', '0', '0', '0'},
                {'0', '0', '0', '0', '+', '0', '0'},
                {'+', '+', '+', '0', '0', '0', '+'}};

        char[][] straightBoard2 = {{'+', '+', '+', '0', '+', '0', '0'},
                {'0', '0', '0', '0', '0', '+', '0'},
                {'0', '0', '+', '0', '0', '0', '0'},
                {'0', '0', '0', '0', '+', '0', '0'},
                {'+', '+', '+', '0', '0', '0', '+'}};

        char[][] straightBoard3 = {{'+', '+', '+', '0', '+', '0', '0'},
                {'0', '0', '0', '0', '0', '0', '0'},
                {'0', '0', '+', '+', '0', '+', '0'},
                {'0', '0', '0', '0', '+', '0', '0'},
                {'+', '+', '+', '0', '0', '0', '+'}};

        char[][] straightBoard4 = {{'+'}};

        ArrayList<ArrayList<Integer>> lists1 = findPassableLanes(straightBoard1);
        System.out.println("Rows: " + lists1.get(0) + ", Columns: " + lists1.get(1));

        ArrayList<ArrayList<Integer>> lists2 = findPassableLanes(straightBoard2);
        System.out.println("Rows: " + lists2.get(0) + ", Columns: " + lists2.get(1));

        ArrayList<ArrayList<Integer>> lists3 = findPassableLanes(straightBoard3);
        System.out.println("Rows: " + lists3.get(0) + ", Columns: " + lists3.get(1));

        ArrayList<ArrayList<Integer>> lists4 = findPassableLanes(straightBoard4);
        System.out.println("Rows: " + lists4.get(0) + ", Columns: " + lists4.get(1));

    }

    public static ArrayList<ArrayList<Integer>> findPassableLanes(char[][] matrix) {

        ArrayList<Integer> rowList = new ArrayList<>();
        ArrayList<Integer> columnList = new ArrayList<>();

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        for (int row = 0; row < matrix.length - 1; row++) {
            if (matrix[row][0] == '0' && dfs(matrix, row, 0, 1)) {
                rowList.add(row);
            }
        }

        for (int column = 0; column < matrix[0].length - 1; column++) {
            if (matrix[0][column] == '0' && dfs(matrix, 0, column, 0)) {
                columnList.add(column);
            }
        }

        result.add(rowList);
        result.add(columnList);
        return result;
    }

    public static boolean dfs(char[][] matrix, int row, int column, int flag) {

        if (flag == 1 && column == matrix[0].length - 1 && matrix[row][matrix[0].length - 1] == '0') return true;

        if (flag == 0 && row == matrix.length - 1 && matrix[matrix.length - 1][column] == '0') return true;

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

        boolean result;

        if (flag == 1) {
            result = dfs(matrix, row, column + 1, 1);
        } else {
            result = dfs(matrix, row + 1, column, 0);
        }

        return result;
    }

}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ This is the third question involving depth first search you have posted in a short time. You may have fallen into the good old "hammer trap." I.e. thinking that all problems look like "nails" if you only have a "hammer" as a tool. This problem is literally: checking if a one dimensional array consists of only zeros. You don't need DFS for that. Did you get tricked by your professor? \$\endgroup\$ Aug 9, 2021 at 7:29
  • \$\begingroup\$ This is just the second question and only intersection of this algorithms are borh of the operations on maze. So this is totaly fine \$\endgroup\$ Aug 9, 2021 at 7:32
  • \$\begingroup\$ Sorry, your problem description was misleading. You are just asking the same question about path finding using DFS again and again. \$\endgroup\$ Aug 9, 2021 at 7:38
  • \$\begingroup\$ All you need to do is convert the pluses to ones, and then get the column sums and row sums, and find which of those sums are 0. \$\endgroup\$
    – Jonah
    Aug 10, 2021 at 5:05

1 Answer 1

1
\$\begingroup\$

The one big thing worth saying has already been said: This isn't a problem where DFS is needed. This could and should be checked using nested for-loops, iteratively checking all rows and columns. Recursion is probably slower, certainly heavier on memory and doesn't make much sense here.

Regarding the dfs function:

  • Use curly brackets for the three long ifs and put the return on a new line. It improves readability and prevents bugs. (hence it's considered a good practice to do so).
  • The last if is useless. You only increment row and column by one, so the third and fourth conditions will always be caught by the ifs before them since row == matrix.length - 1 will always be hit before row > matrix.length - 1. The first and second tests won't happen since you start the two values at 0 and only ever increment them. The last one just doesn't make sense. It's probably a leftover from a DFT maze path search where this field is the exit.
  • int flag is poorly named and the type doesnt make much sense. It should be changed to boolean doRows or boolean doCols with the rest of the code changed accordingly. As is, the reader is left to wonder what this flag is for.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.