A girl and a robot thinking together

Think together · Start with a little story

At a maze junction there is a path to the left and one to the right. The robot explores the left path all the way, finds a dead end, then returns to try the right.

Lay out the process

Follow the steps, then explain them in your own words
  1. Mark the current cellPrevent revisiting in a loop
  2. Try one directionEnter an open cell
  3. Hit a dead endReturn to the previous cell
  4. Try another wayUntil you find the exit or run out of options

DFS models a maze as a graph of positions and the connections you can travel along.

Move only to a valid cell that is allowed to be explored. After returning, try another direction. Check walls and boundaries first.

01How do you turn a maze into a search problem?

Treat each open cell as a state.

State

Current position (row, col).

Start

The entrance.

Goal

The exit.

Transitions

Move one step up, down, left, or right.

02How does DFS explore?

Choose an open direction→Keep going deeper→Backtrack at a dead end

03A simplified code structure

bool dfs(int r, int c) {
    if (r == targetR && c == targetC) {
        return true;
    }

        return true;
    }

    visited[r][c] = true;

    for (each of the four directions) {
        int nr = ...;
        int nc = ...;

        if (inside the map && open && !visited[nr][nc]) {
            if (dfs(nr, nc)) {
                return true;
            }
        }
    }

    return false;
}

04Why must you check the boundaries?

After a move, the new position might be outside the maze.

So first confirm:

0 ≤ nr < rows, and 0 ≤ nc < cols

05Why is visited necessary?

If two cells let you travel back and forth, failing to record visited positions may lead to infinite recursion.

A↔B↔A

06How do you record the actual path?

To output a path, record a position when entering it and undo that record on a failed backtrack, or record each parent and reconstruct the route backward from the destination.

The method depends on whether you need one path or every path.

07Does DFS find the shortest path?

There is no guarantee.

What have you learned?

  • A maze can be treated as a search problem made of cell states.
  • DFS follows one path deeply and backtracks when it fails.
  • Boundary checks and visited records are both important.
  • DFS can check reachability and find a path.
  • DFS does not guarantee a shortest path in an unweighted maze.

Next: BFS: Expand Outward One Layer at a Time

Your turn to try

The left path takes 10 steps, while the right path takes only 3. Will DFS guarantee that it finds the right path first?

Ready? Open to see the explanation

No. DFS explores the chosen branch deeply first; it does not explore paths in order of their total length.