Shortest Distance In A Maze
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.graphs;
import java.util.*;
/*
* ============================================================================================
* PROBLEM: Shortest Distance in a Maze
* ============================================================================================
*
* ---------------------
* 1. Problem Description
* ---------------------
* Given an N x M maze where 0 is empty and 1 is a wall. A ball starts at B and must reach C.
* The ball rolls in a direction and DOES NOT STOP until it hits a wall or the boundary.
* Find the minimum distance (total cells traveled) to stop exactly at the destination.
*
* ---------------------
* 2. Logical Breakdown & Mathematical Formulation
* ---------------------
* This is a Shortest Path problem on a weighted graph where:
* - Nodes: Empty cells (0) where the ball can stop.
* - Edges: The rolling path from one stopping point to the next wall.
* - Weights: The distance traveled during one roll.
*
* Algorithm (Dijkstra's Algorithm):
* 1. Initialization:
* - Use a 2D array dist[N][M] initialized to Infinity.
* - Set dist[startX][startY] = 0.
* - Use a PriorityQueue to store {x, y, distance} for greedy exploration.
*
* 2. Processing:
* While PriorityQueue is not empty:
* a. Extract {currX, currY, d}.
* b. If d > dist[currX][currY], skip (stale path).
* c. For each of the 4 directions (Up, Down, Left, Right):
* - Roll the ball: keep incrementing (nextX, nextY) and count until
* a wall (1) or boundary is hit.
* - Step back one position (the cell before the wall).
* - If dist[currX][currY] + count < dist[stopX][stopY]:
* - Update dist[stopX][stopY] = dist[currX][currY] + count.
* - Push {stopX, stopY, dist[stopX][stopY]} into PriorityQueue.
*
* 3. Result:
* - Return dist[destX][destY] or -1 if unreachable.
*
* ---------------------
* 3. Complexity Analysis
* ---------------------
* Time Complexity: O(N * M * max(N, M))
* - Each cell is processed once in Dijkstra.
* - From each cell, we "roll," which takes O(N) or O(M) time.
* Space Complexity: O(N * M) to store the distance matrix.
* ============================================================================================
/
public class ShortestDistanceInAMaze {
public int solve(int A) {
// TODO: Implement solution
return 0;
}
public int solve(int[][] maze3, int[] start3, int[] dest3) {
return 1;
}
}