Rat Maze With Multiple Jumps

Problem Overview

From each cell the rat may jump 1..mat[r][c] steps right or down; landing on 0 is blocked (cells jumped over may be 0).

Intuition

From each cell the rat may jump 1..mat[r][c] steps right or down; landing on 0 is blocked (cells jumped over may be 0). Among valid paths, prefer shorter jump lengths first, then right before down. Naive backtracking TLEs on large grids — precompute canReach[r][c] (can this cell still reach the destination?) by DP on decreasing r+c, then greedily take the first move in tie-break order that keeps canReach true.

Algorithm

1If mat[0][0] == 0, return [[-1]].
2Set canReach[n-1][n-1] = true; for sum from 2n−3 down to 0, mark canReach[r][c] if some jump right/down lands on a reachable cell.
3If !canReach[0][0], return [[-1]].
4Build path: start at (0,0). While not at (n−1,n−1), try jump = 1..mat[r][c]: right then down; pick first landing with canReach true.
5Return path matrix as ArrayList<ArrayList<Integer>> with 1 on the path.

Example Walkthrough

Input: mat = [[2,1,0,0],[3,0,0,1],[0,1,0,1],[0,0,0,1]]

1. (0,0) jump 1 down → (1,0).
2. (1,0) jump 3 right → (1,3) over zeros.
3. (1,3) down → (2,3) → (3,3) destination.

Output: [[1,0,0,0],[1,0,0,1],[0,0,0,1],[0,0,0,1]]

Common Pitfalls

• Only the landing cell must be non-zero — intermediate cells under a jump can be 0.
• Greedy works only with canReach pruning; plain backtracking is too slow for n = 50.
• Return [[-1]] as a single-row list when no path exists.

Rat Maze With Multiple Jumps.java

Java

// Approach: Precompute canReach[r][c] via DP (decreasing r+c). Greedily pick the first
// valid move (shortest jump, right before down) that still reaches the destination — same
// path as ordered backtracking but O(n^2 * maxJump) instead of exponential.
// Time: O(n^2 * maxJump) Space: O(n^2)

import java.util.*;

class Solution {

    public ArrayList<ArrayList<Integer>> shortestDist(int[][] mat) {
        int n = mat.length;
        if (mat[0][0] == 0) {
            return noPath();
        }

        boolean[][] canReach = new boolean[n][n];
        canReach[n - 1][n - 1] = true;

        for (int sum = 2 * n - 3; sum >= 0; sum--) {
            for (int r = 0; r < n; r++) {
                int c = sum - r;
                if (c < 0 || c >= n || mat[r][c] == 0) {
                    continue;
                }

                int maxJump = mat[r][c];
                for (int jump = 1; jump <= maxJump; jump++) {
                    int right = c + jump;
                    if (right < n && mat[r][right] != 0 && canReach[r][right]) {
                        canReach[r][c] = true;
                        break;
                    }
                    int down = r + jump;
                    if (down < n && mat[down][c] != 0 && canReach[down][c]) {
                        canReach[r][c] = true;
                        break;
                    }
                }
            }
        }

        if (!canReach[0][0]) {
            return noPath();
        }

        int[][] path = new int[n][n];
        path[0][0] = 1;
        int r = 0, c = 0;

        while (r != n - 1 || c != n - 1) {
            boolean moved = false;
            int maxJump = mat[r][c];

            for (int jump = 1; jump <= maxJump; jump++) {
                int right = c + jump;
                if (right < n && mat[r][right] != 0 && canReach[r][right]) {
                    c = right;
                    path[r][c] = 1;
                    moved = true;
                    break;
                }
                int down = r + jump;
                if (down < n && mat[down][c] != 0 && canReach[down][c]) {
                    r = down;
                    path[r][c] = 1;
                    moved = true;
                    break;
                }
            }

            if (!moved) {
                return noPath();
            }
        }

        return toList(path);
    }

    private ArrayList<ArrayList<Integer>> noPath() {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> row = new ArrayList<>();
        row.add(-1);
        res.add(row);
        return res;
    }

    private ArrayList<ArrayList<Integer>> toList(int[][] path) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        for (int[] row : path) {
            ArrayList<Integer> list = new ArrayList<>();
            for (int x : row) {
                list.add(x);
            }
            result.add(list);
        }
        return result;
    }
}

Was this solution helpful?