Find a longest path (like domino) in 2d array [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 3 years ago.

Improve this question

I need to find a longest path from certain point (it is like domino), it can be shown on file:

So the longest domino from cell (0,0) I can create is to (1,4) point, not to (3,0) point.

I already trying to solve this problem with dfs and I achieved to find size of whole area - I don't know how to change this code to calculate longest path for domino.

public class Main {

    static int totalRows = 4;
    static int totalCols = 6;
    static int[] rowNbr = {1, -1, 0, 0};
    static int[] colNbr = {0, 0, 1, -1};
    static int count = 0;
    static boolean[][] visited = new boolean[4][6];

    public static void main(String[] args) {
        int mat[][] = {
                {1, 0, 0, 0, 0, 0},
                {1, 1, 1, 1, 1, 0},
                {1, 0, 0, 0, 0, 0},
                {1, 0, 0, 0, 0, 0}};

        dfs(mat, 0, 0);
        System.out.println(count);
    }

    static void dfs(int[][] matrix, int startRow, int startCol) {    
        visited[startRow][startCol] = true;
        for (int k = 0; k < 4; k++) {
            int row1 = startRow + rowNbr[k];
            int col1 = startCol + colNbr[k];
            if (isValid(row1, col1)) {
                if (!visited[row1][col1] && matrix[row1][col1] == 1) {
                    count++;
                    dfs(matrix, row1, col1);
                }
            }
        }
    }

    static boolean isValid(int row, int col) {
        if (row < 0 || row > totalRows - 1) return false;
        if (col < 0 || col > totalCols - 1) return false;
        return true;
    }
}

Answer 1

The problem of your deepth first search seems to be that you count up the for every field you visit. No matter if the field is a part of the longest path.

So if you change the code like this it should work:

public class Main {

    static int totalRows = 4;
    static int totalCols = 6;
    static int[] rowNbr = {1, -1, 0, 0};
    static int[] colNbr = {0, 0, 1, -1};
    //static int count = 0; //count is no longer needed
    static boolean[][] visited = new boolean[4][6];

    public static void main(String[] args) {
        int mat[][] = {{1, 0, 0, 0, 0, 0}, //
                {1, 1, 1, 1, 1, 0}, //
                {1, 0, 0, 0, 0, 0}, //
                {1, 0, 0, 0, 0, 0}};

        int maxDepth = dfs(mat, 0, 0, 1);
        System.out.println(maxDepth);

        //test second row {1, 1, 0, 0, 0, 0} like Damien mentioned
        mat = new int[][] {{1, 0, 0, 0, 0, 0}, //
                {1, 1, 0, 0, 0, 0}, //
                {1, 0, 0, 0, 0, 0}, //
                {1, 0, 0, 0, 0, 0}};
        visited = new boolean[4][6];

        maxDepth = dfs(mat, 0, 0, 1);
        System.out.println(maxDepth);

        //test a loop
        mat = new int[][] {{1, 0, 0, 0, 0, 0}, //
                {1, 1, 1, 1, 1, 0}, //
                {1, 0, 0, 0, 1, 0}, //
                {1, 1, 1, 1, 1, 0}};
        visited = new boolean[4][6];

        maxDepth = dfs(mat, 0, 0, 1);
        System.out.println(maxDepth);

        //test problem case
        mat = new int[][] {{1, 0, 1, 1, 0, 0}, //
                {1, 1, 1, 1, 1, 1}, //
                {1, 0, 0, 0, 0, 1}, //
                {1, 0, 0, 0, 0, 0}};
        visited = new boolean[4][6];

        maxDepth = dfs(mat, 0, 0, 1);
        System.out.println(maxDepth);
    }

    static int dfs(int[][] matrix, int startRow, int startCol, int depth) {//added a parameter for the recursion depth here
        visited[startRow][startCol] = true;
        int maxDepth = depth;//the maximum depth is the current recursion depth (until you find a deeper one)
        for (int k = 0; k < 4; k++) {
            int row1 = startRow + rowNbr[k];
            int col1 = startCol + colNbr[k];
            if (isValid(row1, col1)) {
                if (!visited[row1][col1] && matrix[row1][col1] == 1) {
                    int newDepth = dfs(matrix, row1, col1, depth + 1);//find the next cell in the path
                    if (newDepth > maxDepth) {//if the path is deeper than the deepest known path update the length
                        maxDepth = newDepth;
                    }
                }
            }
        }
        return maxDepth;
    }

    static boolean isValid(int row, int col) {
        if (row < 0 || row > totalRows - 1)
            return false;
        if (col < 0 || col > totalCols - 1)
            return false;
        return true;
    }
}

This code finds the deepest path in the recursion and only updates the maximum length if the new length is bigger than the current longest path.

It still uses the deepth first search. I added some more test cases to show it works on all input fields:

The first test case is the test you provided in your question:

int mat[][] = {{1, 0, 0, 0, 0, 0}, //
                {1, 1, 1, 1, 1, 0}, //
                {1, 0, 0, 0, 0, 0}, //
                {1, 0, 0, 0, 0, 0}};

The output is 6, which seems to be correct.

The second test is the test case Damien mentioned in the comments:

//test second row {1, 1, 0, 0, 0, 0} like Damien mentioned
mat = new int[][] {{1, 0, 0, 0, 0, 0}, //
        {1, 1, 0, 0, 0, 0}, //
        {1, 0, 0, 0, 0, 0}, //
        {1, 0, 0, 0, 0, 0}};
visited = new boolean[4][6];//reset visited for the next test

Here the output is 4 which seems to be correct to (because of the depth first search it still works in this case).

The third test is a loop:

//test a loop
mat = new int[][] {{1, 0, 0, 0, 0, 0}, //
        {1, 1, 1, 1, 1, 0}, //
        {1, 0, 0, 0, 1, 0}, //
        {1, 1, 1, 1, 1, 0}};
visited = new boolean[4][6];

The output is 13. Still correct.

The fourth test is a test case of which I thought that it would be problematic, but it seems to work too:

//test problem case
mat = new int[][] {{1, 0, 1, 1, 0, 0}, //
        {1, 1, 1, 1, 1, 1}, //
        {1, 0, 0, 0, 0, 1}, //
        {1, 0, 0, 0, 0, 0}};
visited = new boolean[4][6];

The output is 10, which is corret too.

There need to be much more tests to verify it works for every input, but for most of the inputs it will work.