BFS: Visiting a Single Cell Multiple Times

Breadth-First Search (BFS) is an algorithm used to find the shortest path in an unweighted graph or a 2D grid. One of its fundamental rules is:

Once a cell is visited, we mark it as visited and never visit it again.

We usually enforce this using a boolean visited matrix or a Set.

But what happens when the state of your journey matters just as much as your physical position? Let’s explore a scenario where standard BFS falls short.

The Problem: Shortest Path in a Grid with Obstacles Elimination

Consider LeetCode Problem 1293. Shortest Path in a Grid with Obstacles Elimination.

Imagine an m x n grid where each cell is either empty (0) or contains an obstacle (1). You can move up, down, left, or right. Normally, hitting an obstacle means hitting a dead end. However, in this problem, you have a power: you can eliminate at most k obstacles anywhere along your path.

Goal: Find the minimum number of steps to walk from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1). Return -1 if no such path exists.

Why Simple BFS Will Not Work

In standard BFS, the state is simply our coordinates: (row, col). Once we process a cell, we mark:

visited[row][col] = true

Let’s see why this fails.

Suppose we have the following grid and k = 1:

Assume we are at cell (1,2) — the destination. There are different ways to reach this cell:

Path 1 (No obstacle removed)

(0,0) → (0,1) → (0,2) → (1,2)

• Steps = 3
• Remaining k = 1

Path 2 (One obstacle removed)

(0,0) → (0,1) → (1,1) → (1,2)

• Steps = 3
• Remaining k = 0 (we eliminated one obstacle)

Both paths reach the same cell, but the state is different:

• In the first case, we still have the ability to remove an obstacle later.
• In the second case, we do not.

If we apply standard BFS, we would mark grid[1][2] as visited when we reach it the first time. Because of this, we would ignore the second path, which might lead to a valid or even required solution in larger grids. This can lead to incorrect results.

The Trick

The problem is that our BFS state is incomplete. We are only tracking position (row, col), but we also need to track how many obstacles we have eliminated so far.

So the BFS state should actually be:

(row, col, obstaclesUsed)

This means we are not just visiting a cell — we are visiting a state.

Reaching (2,3) with 0 obstacles used is different from reaching (2,3) with 1 obstacle used.

Modifying the Visited Set

Instead of using a 2D visited array, we need something like:

visited[row][col][obstaclesUsed]

Or in JavaScript, a Set:

visited.add(`${row},${col},${obstaclesUsed}`)

This allows us to visit the same cell multiple times, but only if the number of obstacles used is different.

Running the Example Again

Now when we run BFS on the same grid:

[
  [0,0,0],
  [1,1,0]
]

We will treat these as different states:

(1,2,0)  → reached without removing obstacle
(1,2,1)  → reached after removing obstacle

So even though the cell is the same, BFS will continue exploring because the state is different.

This is the idea behind many BFS problems where:

• You have fuel
• You have health
• You can break walls
• You can eliminate obstacles
• You have keys
• You have remaining moves

To Remember

When solving grid BFS problems, always ask:

“Is reaching this cell with different resources/states considered different?”

If yes, then you must include that state in your visited structure.

State BFS > Normal BFS

(row, col)                 ← Normal BFS
(row, col, extraState)     ← State BFS

The goal of the question is to return the minimum steps which is taken care by using BFS, we are just modifying it so we can revisit a cell multiple times depending on the elimination state