Geek in a Maze

Problem Overview

Geek may move up, down, left, or right, but only down and up are budgeted.

Intuition

Geek may move up, down, left, or right, but only down and up are budgeted. A shortest path in "number of downs" lets you recover ups from geometry: net row change is downs minus ups, so ups = downs + (startRow - row). Left and right never cost a vertical move, so they should be processed before a down. That is 0-1 BFS: free edges to the front of the deque, down edges to the back.

Algorithm

1If the start cell is blocked, return 0.
2dist[i][j] = fewest downs to (i, j), start at 0, others infinity.
30-1 BFS from (r, c). Neighbors that go down have cost 1; up, left, and right have cost 0.
4Relax a neighbor when dist[cur] + cost is strictly smaller. Push front on cost 0, back on cost 1.
5Count unblocked cells with dist != infinity, downs <= d, and downs + (r - i) <= u.

Example Walkthrough

Input: start (0, 0), u = 1, d = 1, open 2x2 grid

1. (0, 0) has downs = 0, ups = 0. Both budgets allow it.
2. Right to (0, 1) is free: downs = 0, ups = 0.
3. Down to (1, 0) costs 1: downs = 1, ups = 1 + 0 - 1 = 0.
4. If d and u are at least 1, every open cell is reachable.

Output: 4

Common Pitfalls

• Do not run a normal queue BFS. A down-first path can mark a cell with too many downs before a free path arrives.
• Up is not free in the budget even though it is free in the BFS cost. Convert with ups = downs + r - i after the search.
• Blocked cells ('#') are never counted, including the start.
• Relax only on a strictly better downs count. Equal dist should not re-enqueue.

Geek in a Maze.java

Java

// Approach: Only a down step spends a move; left, right, and up are free.
// 0-1 BFS from (r, c) stores the fewest downs to each cell. For a cell at
// row i, ups = downs + (startRow - i) by net vertical displacement. Count
// cells with downs <= d and ups <= u.
// Complexity: O(n * m) time and O(n * m) space.

import java.util.*;

class Solution {

    public int numberOfCells(int r, int c, int u, int d, char[][] mat) {
        int n = mat.length;
        int m = mat[0].length;

        if (mat[r][c] == '#') {
            return 0;
        }

        int[][] dist = new int[n][m];

        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        Deque<int[]> dq = new ArrayDeque<>();

        dist[r][c] = 0;
        dq.addFirst(new int[]{r, c});

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!dq.isEmpty()) {
            int[] cur = dq.pollFirst();
            int x = cur[0];
            int y = cur[1];

            for (int k = 0; k < 4; k++) {
                int nx = x + dr[k];
                int ny = y + dc[k];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    continue;
                }

                if (mat[nx][ny] == '#') {
                    continue;
                }

                int cost = (nx > x) ? 1 : 0;

                if (dist[x][y] + cost < dist[nx][ny]) {
                    dist[nx][ny] = dist[x][y] + cost;

                    if (cost == 0) {
                        dq.addFirst(new int[]{nx, ny});
                    } else {
                        dq.addLast(new int[]{nx, ny});
                    }
                }
            }
        }

        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == '#') {
                    continue;
                }

                if (dist[i][j] == Integer.MAX_VALUE) {
                    continue;
                }

                int downMoves = dist[i][j];
                int upMoves = downMoves + r - i;

                if (downMoves <= d && upMoves <= u) {
                    ans++;
                }
            }
        }

        return ans;
    }
}

Was this solution helpful?