AlgoMaster Logo

Minimum Cost to Make at Least One Valid Path in a Grid

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We have a grid where every cell has an arrow pointing in one of four directions: right, left, down, or up. Starting at the top-left corner, we want to reach the bottom-right corner by following arrows. If a cell's arrow already points in the direction we want to travel, moving there is free. If we need to go in a different direction, we pay a cost of 1 to change that cell's arrow.

This is a shortest path problem, but the edge weights are not all the same. Moving to a neighbor that the arrow already points to costs 0. Moving to any other neighbor costs 1. Every edge in this implicit graph has a weight of either 0 or 1.

When edge weights are restricted to 0 and 1, a full Dijkstra with a priority queue is more than the problem needs. A faster approach called 0-1 BFS uses a deque instead.

Key Constraints:

  • 1 <= m, n <= 100 → The grid has at most 10,000 cells, small enough for both a Dijkstra-based and a BFS-based solution.
  • 1 <= grid[i][j] <= 4 → Every cell has exactly one arrow. There are no empty cells or special values to handle.
  • Edges are weighted 0 or 1 → This structural property is what enables 0-1 BFS.

Approach 1: Dijkstra's Algorithm

Intuition

Model the grid as a weighted graph and find the shortest path. Each cell is a node. From each cell, you can move to any of its four in-bounds neighbors. If the cell's arrow already points toward that neighbor, the edge weight is 0. Otherwise, the edge weight is 1.

Dijkstra's algorithm finds shortest paths in graphs with non-negative edge weights. A min-heap (priority queue) always processes the cell with the smallest known cost first, which guarantees that the first time a cell is popped, its recorded distance is final.

Algorithm

  1. Create a dist matrix of size m x n, initialized to infinity. Set dist[0][0] = 0.
  2. Push (0, 0, 0) onto a min-heap, where the first value is cost.
  3. Define direction vectors for right, left, down, and up matching grid values 1-4.
  4. While the heap is not empty, pop the cell with the smallest cost.
  5. If this cell is the bottom-right corner, return the cost.
  6. Skip if we've already found a better path to this cell.
  7. For each of the four neighbors, calculate the edge cost: 0 if the arrow points there, 1 otherwise.
  8. If the new cost is smaller than the known distance to the neighbor, update it and push to the heap.
  9. Return dist[m-1][n-1].

Visualization and Code

Loading animation...

The priority queue adds a logarithmic factor on every insert and extract. Because edge weights here are only 0 or 1, a deque removes that overhead.

Approach 2: 0-1 BFS (Optimal)

Intuition

Since every edge weight is either 0 or 1, Dijkstra's priority queue can be replaced with a deque (double-ended queue):

  • When we follow a 0-cost edge (the arrow already points to the neighbor), push the neighbor to the front of the deque.
  • When we follow a 1-cost edge (we change the arrow), push the neighbor to the back of the deque.

This processes cells in non-decreasing order of cost, the same order Dijkstra produces, but without the logarithmic overhead of a heap. This technique is 0-1 BFS, and it applies to any shortest path problem whose edge weights are restricted to 0 and 1.

Algorithm

  1. Create a dist matrix of size m x n, initialized to infinity. Set dist[0][0] = 0.
  2. Create a deque and push (0, 0) to it.
  3. Define direction vectors for right, left, down, and up matching grid values 1-4.
  4. While the deque is not empty, pop from the front.
  5. For each of the four neighbors, calculate the edge cost: 0 if the arrow points there, 1 otherwise.
  6. If the new cost is smaller than the known distance to the neighbor, update it.
  7. If the edge cost is 0, push the neighbor to the front of the deque. If it's 1, push to the back.
  8. Return dist[m-1][n-1].

Visualization and Code

Loading animation...