Adventure in a Maze

Problem Overview

From each cell you may move right (value 1), down (value 2), or either (value 3).

Intuition

From each cell you may move right (value 1), down (value 2), or either (value 3). Work backward from the exit: paths and best adventure for a cell depend only on the allowed neighbors that already know how to reach the destination. Rolling one previous row keeps O(n) memory while still filling every cell in O(n^2).

Algorithm

1paths[j] / best[j] mean ways and max path-sum from the cell below (then from the current row) to the exit.
2Seed the bottom-right: paths = 1, best = grid[n-1][n-1]. Fill the bottom row right-to-left using only right moves when allowed and the neighbor is reachable.
3For each row i from n-2 down to 0, build nextPaths / nextBest right-to-left.
4If value is 1 or 3 and the right cell has paths > 0: take its ways and add g to its best sum.
5If value is 2 or 3 and the down cell (old paths[j]) has paths > 0: add those ways (mod 1e9+7) and take max with g + down best.
6Swap to the new row arrays. Answer is [paths[0] % MOD, best[0]] from the start cell.

Example Walkthrough

Input: grid = [[3, 2], [3, 1]]

1. Exit (1,1) has 1 way and sum 1.
2. Cell (1,0)=3 can go right: 1 way, sum 3+1=4. Cell (0,1)=2 can go down: 1 way, sum 2+1=3.
3. Start (0,0)=3: right gives sum 3+3=6; down gives sum 3+4=7. Two ways, max adventure 7.

Output: [2, 7]

Common Pitfalls

• A neighbor with 0 paths is unreachable - do not add its sum even if the move type allows it.
• Path count must use modulo 1e9+7; the adventure sum is not modded.
• Process right-to-left within a row so the right neighbor already holds the new-row values.
• Bottom-right is always reachable from itself (1 way) even if its value would not allow a further move.

Adventure in a Maze.java

Java

// Approach: From each cell, 1 = right only, 2 = down only, 3 = both. DP from
// the destination: paths[j] / best[j] hold ways and max path sum for the row
// below (then the current row). Process bottom-up, right-to-left so "right"
// neighbors are already in the new row and "down" neighbors stay in the old
// row - O(n) extra memory instead of full n x n tables.
// Complexity: O(n^2) time and O(n) space.

import java.util.*;

class Solution {

    static final int MOD = 1_000_000_007;

    public ArrayList<Integer> findWays(int[][] grid) {
        int n = grid.length;
        long[] paths = new long[n];
        int[] best = new int[n];

        // Bottom row: can only move right toward the exit.
        paths[n - 1] = 1;
        best[n - 1] = grid[n - 1][n - 1];
        for (int j = n - 2; j >= 0; j--) {
            int g = grid[n - 1][j];
            if ((g == 1 || g == 3) && paths[j + 1] > 0) {
                paths[j] = paths[j + 1];
                best[j] = g + best[j + 1];
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            long[] nextPaths = new long[n];
            int[] nextBest = new int[n];

            for (int j = n - 1; j >= 0; j--) {
                int g = grid[i][j];
                long cnt = 0;
                int mx = -1;

                if ((g == 1 || g == 3) && j + 1 < n && nextPaths[j + 1] > 0) {
                    cnt = nextPaths[j + 1];
                    mx = g + nextBest[j + 1];
                }
                if ((g == 2 || g == 3) && paths[j] > 0) {
                    cnt = (cnt + paths[j]) % MOD;
                    mx = Math.max(mx, g + best[j]);
                }

                nextPaths[j] = cnt;
                if (mx != -1) {
                    nextBest[j] = mx;
                }
            }

            paths = nextPaths;
            best = nextBest;
        }

        ArrayList<Integer> ans = new ArrayList<>(2);
        ans.add((int) (paths[0] % MOD));
        ans.add(best[0]);
        return ans;
    }
}

Was this solution helpful?