Longest Possible Route in a Matrix with Hurdles

Problem Overview

Find the longest simple path from (xs,ys) to (xd,yd) on a binary grid (1 = free, 0 = hurdle).

Intuition

Find the longest simple path from (xs,ys) to (xd,yd) on a binary grid (1 = free, 0 = hurdle). Shortest-path BFS is wrong here — we want the maximum number of edges among all simple paths. Exhaustive DFS with backtracking explores every route, marking cells visited so a path never revisits a cell, then unmarking so other routes can use it.

Algorithm

1If start or destination is a hurdle (0), return −1. If start equals destination on a free cell, return 0.
2DFS from (x,y) with currentNodes = path length in cells so far.
3When (x,y) is the destination, update maxEdges = max(maxEdges, currentNodes − 1).
4Otherwise mark visited[x][y], recurse to four neighbors that are in-bounds, free, and unvisited, then unmark (backtrack).
5Return maxEdges, or −1 if the destination was never reached.

Example Walkthrough

Input: mat with free cells and hurdles, source (0,0), dest (1,2)

1. From the source, try up/down/left/right on cells with value 1.
2. Mark each cell visited along the current path so you cannot loop.
3. Whenever the destination is hit, record edges = nodes − 1 and keep the maximum.
4. Backtrack (unmark) so a longer detour that still reaches the destination can be tried.

Output: length of the longest simple path in edges, or -1

Common Pitfalls

• Return edge count (nodes − 1), not the number of cells visited.
• Must backtrack — without unmarking visited, you only explore one path tree.
• Unlike maze shortest path, do not stop at the first time you reach the destination.
• Exponential time is expected; grids for this problem are small.

Longest Possible Route in a Matrix with Hurdles.java

Java

// Approach: DFS + backtracking — explore all 4-direction paths on free cells (1), mark
// visited to avoid cycles, unmark on return. Track max edge count when destination is reached.
// Time: O(4^(r*c)) worst case Space: O(r*c)

class Solution {

    private int maxEdges;
    private int rows;
    private int cols;
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};

    public int longestPath(int[][] mat, int xs, int ys, int xd, int yd) {
        rows = mat.length;
        cols = mat[0].length;

        // Edge case: start and destination are the same
        if (xs == xd && ys == yd) {
            return mat[xs][ys] == 1 ? 0 : -1;
        }

        // If start or destination is blocked
        if (mat[xs][ys] == 0 || mat[xd][yd] == 0) {
            return -1;
        }

        maxEdges = -1;
        boolean[][] visited = new boolean[rows][cols];

        // Start DFS, initial path length (nodes) = 1
        dfs(mat, xs, ys, xd, yd, 1, visited);

        // Return edges (nodes - 1)
        return maxEdges == -1 ? -1 : maxEdges;
    }

    private void dfs(int[][] mat, int x, int y, int xd, int yd, int currentNodes, boolean[][] visited) {
        if (x == xd && y == yd) {
            int edges = currentNodes - 1;
            if (edges > maxEdges) {
                maxEdges = edges;
            }
            return;
        }

        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols
                    && mat[nx][ny] == 1 && !visited[nx][ny]) {
                dfs(mat, nx, ny, xd, yd, currentNodes + 1, visited);
            }
        }

        // Backtrack
        visited[x][y] = false;
    }
}

Was this solution helpful?