709901. Longest Possible Route in a Matrix with Hurdles
Medium
Here is the detailed Markdown blog post for the problem "Longest Possible Route in a Matrix with Hurdles":
Longest Possible Route in a Matrix with Hurdles
Summary
Given an M x N matrix where some cells are hurdles, find the longest possible route from the top-left cell to the bottom-right cell. The route can only move either down or right and cannot traverse over hurdles.
Detailed Explanation
To solve this problem, we will use a backtracking algorithm. We start from the top-left cell and try to move either down or right. If the current cell is a hurdle, we backtrack to the previous cell until we find an unobstructed path. When we reach the bottom-right cell, we have found the longest possible route.
Here's the step-by-step breakdown of the solution:
- Initialize a 2D array
dpwith all elements set to -1. - Start from the top-left cell (0, 0) and try to move either down or right.
- If the current cell is not a hurdle (i.e., its value is 0), mark it as visited by setting
dp[i][j] = 1. - Recursively call the function for the adjacent cells that are not hurdles.
- If we reach the bottom-right cell, return the length of the longest path found so far.
- If we encounter a hurdle or reach the boundary of the matrix, backtrack to the previous cell.
Time complexity: O(M * N) Space complexity: O(M * N)
Optimized Solutions
Java
public int longestRoute(int[][] matrix) {
int M = matrix.length;
int N = matrix[0].length;
boolean[][] visited = new boolean[M][N];
return longestRoute(matrix, 0, 0, visited);
}
private int longestRoute(int[][] matrix, int i, int j, boolean[][] visited) {
if (i == M - 1 && j == N - 1) {
return 1;
}
if (visited[i][j] || matrix[i][j] == 1) {
return 0;
}
visited[i][j] = true;
int maxPath = Math.max(longestRoute(matrix, i + 1, j, visited),
longestRoute(matrix, i, j + 1, visited));
visited[i][j] = false;
return maxPath + 1;
}