BFS: When You Need to Visit a Cell More Than Once

Breadth-First Search (BFS) is an algorithm for finding the shortest path in an unweighted graph or a 2D grid. One of its core principles is simple:

Once a cell is visited, we mark it as visited and never return to it.

This is typically enforced using a boolean visited matrix or a Set, ensuring efficiency and preventing cycles.

But what if your position alone isn’t enough to describe your progress? What if the state of your journey matters just as much as where you are?

This is where standard BFS starts to break down.

I encountered a problem like this in an interview. At first, it seemed like a straightforward BFS. However, after walking through a small example, it became clear that the usual “visit once” rule didn’t hold. The same cell sometimes needed to be revisited under different conditions.

Afterward, I explored this idea further and discovered a useful variation: BFS with state (often referred to as BFS with bitmasking, or BFS that allows revisiting cells under different states).

These notes are a summary of that concept.

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

const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
var shortestPath = function (grid, k) {
    const m = grid.length;
    const n = grid[0].length;
    const visited = Array.from({ length: m }, () => Array.from({ length: n }, () => Array(k + 1).fill(false)));
    const q = []; // DO NOT USE ARRAY, USE ACTUAL QUEUE
    q.push([0, 0, k]) // r, c, obs;
    let level = 0;
    while (q.length) {
        let size = q.length;
        while (size--) {
            const [r, c, obs] = q.shift();
            if (r == m - 1 && c == n - 1) return level;
            for (const [dx, dy] of directions) {
                const x = r + dx;
                const y = c + dy;
                if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y][obs]) continue;

                if (grid[x][y] == 0) {
                    q.push([x, y, obs])
                    visited[x][y][obs] = true;
                } else if (grid[x][y] == 1 && obs > 0 && !visited[x][y][obs - 1]) {
                    q.push([x, y, obs - 1]);
                    visited[x][y][obs - 1] = true;
                }
            }
        }

        level++;
    }
    return -1;
};