Build a Maze Solver with BFS and DFS

Implement BFS and DFS in C++ to solve mazes and prove BFS finds the shortest path.

Introduction

30 Second Summary

Every time your GPS finds the fastest route or a video game character navigates around obstacles, a graph traversal algorithm is doing the heavy lifting behind the scenes. Some approaches find any path quickly, while others guarantee the shortest one.

In this project, you will build a command-line maze solver in C++ that solves the same maze two different ways and prints both solutions visually so you can see exactly why one algorithm outperforms the other.

What You'll Build

A C++ program that solves mazes using Depth-First Search (DFS) and Breadth-First Search (BFS), then displays both solutions side-by-side with a comparison of path lengths.

By the end of this project, you'll have:

  • A working maze solver that represents mazes as 2D character grids and solves them with both DFS (recursive backtracking) and BFS (queue-based exploration).
  • Visual console output showing both solutions with path markers, so you can compare exactly how many steps each algorithm takes.
  • A concrete understanding of why BFS guarantees the shortest path while DFS does not, demonstrated by your own code producing different path lengths on the same maze.
  • Secret Mission: Add A* search with Manhattan distance heuristic and compare its efficiency against BFS.

Are there any prerequisites?

You should be comfortable with basic C++ syntax: variables, functions, loops, and vectors. Familiarity with recursion is helpful but not required. This project will walk you through every recursive call step by step.

Before We Start

Before you can build a maze solver, you need a working C++ development environment. That means a compiler that turns your code into a runnable program, and an editor that helps you write it.

In this step, you will verify that the g++ compiler is accessible, install a helpful VS Code extension, and confirm everything works by compiling a simple test program.

In this step, get ready to:
  • Verify g++ is accessible from your terminal.
  • Install the C/C++ extension in VS Code.
  • Create a project folder and compile a Hello World program.
Verify g++ is accessible from your terminal

The g++ compiler translates your C++ source code into an executable program. You need it available in your terminal for the rest of this project.

  • Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
  • Type VS Code and press Enter to open it.
  • Open the integrated terminal by pressing Ctrl+` (backtick key, top-left of your keyboard).
  • Check if g++ is available by running this command:
g++ --version

✔️ I see a version number

Your compiler is ready. Move on to the next substep.

ⓧ Command not found or not recognized

You need to install a C++ compiler. Follow the instructions for your operating system below.

Windows

You will install g++ through MSYS2, which provides a Unix-like toolchain for Windows.

  • Download and run the MSYS2 installer from msys2.org.
  • After installation, open the MSYS2 UCRT64 terminal from your Start menu.
  • Install the C++ toolchain by running this command:
pacman -S --needed base-devel mingw-w64-ucrt-x86_64-toolchain
What does this command do?

This installs the MinGW-w64 compiler collection, which includes g++, linker tools, and standard C++ libraries.

  • When prompted to select packages, press Enter to accept all defaults.
  • After installation completes, add the compiler to your system PATH.
  • Press the Windows key and search for Edit environment variables for your account.
  • Select Path in the top list, then click Edit.
  • Click New and paste this path:
C:\msys64\ucrt64\bin
  • Click OK on all open dialogs to save.
  • Close and reopen VS Code completely, then open a new terminal and run g++ --version again to confirm it works.

macOS

On macOS, g++ is included with Xcode Command Line Tools.

  • Install the command line tools by running:
xcode-select --install
  • A dialog will appear asking you to confirm the installation. Click Install and wait for it to complete.
  • Once finished, run g++ --version again in your VS Code terminal to confirm it works.
Install the C/C++ extension in VS Code

The Microsoft C/C++ extension adds syntax highlighting, error detection, and IntelliSense autocomplete for your C++ code.

  • Open the Extensions panel by pressing Cmd+Shift+X (macOS) or Ctrl+Shift+X (Windows).
  • Type C++ in the search bar.
  • Find the extension named C/C++ by Microsoft (it should be the first result).
  • Click Install.

How to tell it installed

After installation, the Install button changes to a Disable button. You may also see a notification suggesting you reload the window.

Create the project folder and test your setup

Now you will create a dedicated folder for your maze solver project and confirm the full compile-and-run cycle works.

  • Move to your Desktop by running this command in the VS Code terminal:
cd ~/Desktop
  • Create your project folder and move into it by running these commands:
mkdir maze-solver
cd maze-solver
  • Open this folder in VS Code by clicking File in the menu bar.
  • Click Open Folder.
  • Navigate to your Desktop, select the maze-solver folder, and click Open.

Why open the folder this way?

Opening a folder (not just a file) tells VS Code to treat it as your workspace. This enables the C/C++ extension to find your files and offer autocomplete.

  • If VS Code asks whether you trust the authors of this folder, click Yes, I trust the authors.
  • Open a new integrated terminal by pressing Ctrl+`.
  • Create a new file by clicking the New File icon in the Explorer sidebar (the left panel).
  • Name the file main.cpp and press Enter.
  • Paste the following Hello World program into main.cpp:
#include <iostream>
using namespace std;
int main() {
    cout << "Hello World" << endl;
    return 0;
}

What does this code do?

  • #include <iostream> brings in the input/output library so you can print text to the terminal.
  • using namespace std; lets you write cout instead of the longer std::cout.
  • cout << "Hello World" << endl; prints the text followed by a newline.
  • return 0; signals that the program finished successfully.
  • Save the file by pressing Cmd+S (macOS) or Ctrl+S (Windows).
  • Compile your program by running this command in the terminal:
g++ -std=c++17 -o maze_solver.exe main.cpp

What does this command do?

  • g++ invokes the C++ compiler.
  • -std=c++17 tells the compiler to use the C++17 standard.
  • -o maze_solver.exe names the output executable file.
  • main.cpp is the source file to compile.

If the command runs with no output, that means compilation succeeded.

  • Run your compiled program:

macOS

./maze_solver.exe

Windows

.\maze_solver.exe

You should see Hello World printed in your terminal.

Not seeing Hello World?

  • If you see a "file not found" error, make sure your terminal is inside the maze-solver folder. Run ls (macOS) or dir (Windows) to check that main.cpp and maze_solver.exe are listed.
  • If the compile step gave an error about iostream not found, your compiler installation may be incomplete. Revisit the g++ installation instructions above.
  • If you see a syntax error, double-check that the code in main.cpp matches the snippet above exactly (especially the quotes and semicolons).

Still stuck? Help me figure out why my Hello World program won't compile or run.

✔️ Awesome, I've got everything!

Great. Double check you have saved main.cpp and move on to the next step.

ⓧ I'd like to double check the full code

Here is what main.cpp should look like at this point:

#include <iostream>
using namespace std;
int main() {
    cout << "Hello World" << endl;
    return 0;
}

Your development environment is ready to go. Next up, you will build the maze itself and write helper functions that both search algorithms will use.

Build the Maze Representation

Your environment is set up and you have confirmed that C++ compiles and runs. Now you need a way to represent a maze in code so that algorithms can traverse it.

In this step, you will define a maze as a 2D character grid and write helper functions that display the maze, validate movement, and mark solution paths. These helpers form the foundation that both DFS and BFS will use in later steps.

In this step, get ready to:
  • Define a hardcoded maze and a function that prints it to the console.
  • Create helper functions for movement validation and path marking.
  • Compile and run to verify the maze displays correctly.
Define the maze and display function

A maze can be represented as a grid of characters where each character encodes what occupies that cell. You will use # for walls, . for open paths, S for the start, and E for the end.

  • Replace all the code in main.cpp with the following includes and printMaze function:
#include <iostream>
#include <vector>
#include <string>

using namespace std;

void printMaze(const vector<string>& maze, const string& title) {
    // Display the maze with a header
    cout << "\n=== " << title << " ===" << endl;
    for (int i = 0; i < (int)maze.size(); i++) {
        cout << maze[i] << endl;
    }
    cout << endl;
}

What does this code do?

The three #include lines bring in the libraries you need: iostream for console output, vector for dynamic arrays, and string for text manipulation.

The printMaze function takes a vector<string> (where each string is one row of the maze) and prints every row to the console with a title header. The (int) cast prevents a compiler warning when comparing signed and unsigned integers.

You won't see a change yet because there is no main() function. The next chunk adds it.

  • Below the printMaze function, add this main() function that defines the maze, locates the start and end positions, and prints it:
int main() {
    // Define the maze as a 2D character grid
    vector<string> maze = {
        "############",
        "#S........E#",
        "#.########.#",
        "#..........#",
        "############"
    };

    // Scan the grid to find start (S) and end (E) positions
    int startX = -1, startY = -1, endX = -1, endY = -1;
    for (int i = 0; i < (int)maze.size(); i++) {
        for (int j = 0; j < (int)maze[i].size(); j++) {
            if (maze[i][j] == 'S') { startX = i; startY = j; }
            if (maze[i][j] == 'E') { endX = i; endY = j; }
        }
    }

    cout << "Maze Solver: BFS vs DFS Comparison" << endl;
    cout << "S = Start, E = End, # = Wall, . = Open, * = Path" << endl;
    printMaze(maze, "Original Maze");

    return 0;
}

What does this code do?

The maze variable is a vector<string> where each string is a row. The nested for loops scan every cell to find the coordinates of S and E.

Storing the start and end as (startX, startY) and (endX, endY) lets your algorithms know where to begin searching and when they have reached the goal.

  • Save main.cpp.
  • Compile and run by entering these commands in your terminal:
g++ -std=c++17 -o maze_solver.exe main.cpp
.\maze_solver.exe

You should see the maze grid printed to the console with S and E visible inside the bordered grid.

Don't see the maze printed?

  • Check that main.cpp is saved. Unsaved changes will not be picked up by the compiler.
  • Make sure you deleted all the old Hello World code before pasting the new code. Duplicate main() functions cause a compiler error.
  • Verify the maze strings each have the same number of characters (12 characters per row). A missing or extra # breaks the grid shape.

Help me debug my maze printing issue

Create the movement and path helpers

Your algorithms will need to check whether a cell is safe to move into and mark cells that belong to the solution path. You will create these reusable helpers now so both DFS and BFS can share them.

  • In main.cpp, find the blank line between using namespace std; and void printMaze. Add these direction arrays:
// Direction arrays: up, down, left, right
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
  • Now find the closing brace } of your printMaze function. Below it, add the isValid helper function:
bool isValid(const vector<string>& maze, const vector<vector<bool>>& visited, int x, int y) {
    // Check bounds, walls, and visited status
    int rows = maze.size();
    int cols = maze[0].size();
    return (x >= 0 && x < rows && y >= 0 && y < cols
            && maze[x][y] != '#' && !visited[x][y]);
}

What do these pieces do?

The dx[] and dy[] arrays encode four directions (up, down, left, right). Adding dx[i] to a row and dy[i] to a column gives you the neighboring cell in direction i.

The isValid function answers: can I step into cell (x, y)? It returns true only when the cell is inside the grid, is not a wall (#), and has not already been visited.

  • Below isValid, add the markPath function that stamps * characters onto the maze for each cell in a solution path:
void markPath(vector<string>& maze, const vector<pair<int,int>>& path) {
    // Stamp '*' on path cells (skip start and end markers)
    for (int i = 0; i < (int)path.size(); i++) {
        int x = path[i].first;
        int y = path[i].second;
        if (maze[x][y] != 'S' && maze[x][y] != 'E') {
            maze[x][y] = '*';
        }
    }
}

What does markPath do?

It loops through a vector of (x, y) coordinates representing the solution path. For each coordinate, it replaces the . character with * so you can see the path visually.

It skips cells that contain S or E to keep those markers readable in the output.

You won't see a change in the program output yet because no algorithm is calling these helpers. They will be used starting in the next step when you implement DFS.

Compile and verify the output

Even though the output has not changed, recompiling confirms that the new helper functions have no syntax errors.

  • Save main.cpp and recompile by running:
g++ -std=c++17 -o maze_solver.exe main.cpp
.\maze_solver.exe

You should see the same maze grid printed with S and E visible, confirming that your helpers compile cleanly alongside the rest of the program.

Seeing a compiler error?

  • Make sure isValid and markPath are placed above int main(). In C++, functions must be declared before they are used.
  • Check that the direction arrays (dx[] and dy[]) are placed above printMaze, outside any function.
  • Look for mismatched curly braces or missing semicolons. The error message will include a line number to help you locate the issue.

Help me fix my compiler error in the maze solver

✔️ Awesome, I've got everything!

Great. Double check you have saved main.cpp and the program compiles without errors.

ⓧ I'd like to double check the full code

Here is the complete main.cpp at the end of this step:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Direction arrays: up, down, left, right
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

void printMaze(const vector<string>& maze, const string& title) {
    cout << "\n=== " << title << " ===" << endl;
    for (int i = 0; i < (int)maze.size(); i++) {
        cout << maze[i] << endl;
    }
    cout << endl;
}

bool isValid(const vector<string>& maze, const vector<vector<bool>>& visited, int x, int y) {
    int rows = maze.size();
    int cols = maze[0].size();
    return (x >= 0 && x < rows && y >= 0 && y < cols
            && maze[x][y] != '#' && !visited[x][y]);
}

void markPath(vector<string>& maze, const vector<pair<int,int>>& path) {
    for (int i = 0; i < (int)path.size(); i++) {
        int x = path[i].first;
        int y = path[i].second;
        if (maze[x][y] != 'S' && maze[x][y] != 'E') {
            maze[x][y] = '*';
        }
    }
}

int main() {
    vector<string> maze = {
        "############",
        "#S........E#",
        "#.########.#",
        "#..........#",
        "############"
    };

    int startX = -1, startY = -1, endX = -1, endY = -1;
    for (int i = 0; i < (int)maze.size(); i++) {
        for (int j = 0; j < (int)maze[i].size(); j++) {
            if (maze[i][j] == 'S') { startX = i; startY = j; }
            if (maze[i][j] == 'E') { endX = i; endY = j; }
        }
    }

    cout << "Maze Solver: BFS vs DFS Comparison" << endl;
    cout << "S = Start, E = End, # = Wall, . = Open, * = Path" << endl;
    printMaze(maze, "Original Maze");

    return 0;
}

Your maze is defined and all the helper functions are in place. Next up, you will implement DFS to find a path through this maze using recursive backtracking.

Implement DFS

Your maze is on screen and your helper functions are ready to go. Now it is time to teach your program how to actually solve the maze.

Depth-First Search works the way you might solve a maze by hand. Pick a direction, walk as far as you can, and when you hit a dead end, backtrack to the last intersection and try a different direction. This strategy finds a path, but not necessarily the shortest one.

In this step, get ready to:
  • Write the recursive DFS function with backtracking.
  • Write a wrapper function and call it from main.
  • Compile, run, and observe the DFS solution path.
Write the recursive dfs function

Recursion lets a function call itself to explore deeper and deeper into the maze. If every direction from the current cell leads to a dead end, the function removes the current cell from the path and returns false. This undo-and-retry pattern is called backtracking.

  • In main.cpp, find the isValid function's closing brace.
  • Add the following dfs function below it:
bool dfs(const vector<string>& maze, vector<vector<bool>>& visited,
         int x, int y, int endX, int endY, vector<pair<int,int>>& path) {

    // Base case: we reached the end
    if (x == endX && y == endY) {
        path.push_back(make_pair(x, y));
        return true;
    }

    // Mark current cell as visited and add to path
    visited[x][y] = true;
    path.push_back(make_pair(x, y));

    // Try all 4 directions
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (isValid(maze, visited, nx, ny)) {
            // Recurse into neighbor - if it finds the end, propagate success
            if (dfs(maze, visited, nx, ny, endX, endY, path)) {
                return true;
            }
        }
    }

    // All directions failed - backtrack
    path.pop_back();
    return false;
}

What does this code do?

The dfs function explores the maze one cell at a time using recursion.

  • The base case checks if the current cell (x, y) is the end position. If so, it adds the cell to the path and returns true.
  • Otherwise, it marks the cell as visited, adds it to the path, and tries all 4 directions using the dx[] and dy[] arrays.
  • If a recursive call returns true, the path is found and success propagates up through every frame.
  • If all directions fail, path.pop_back() removes the current cell from the path. This is the backtracking step.

You will not see a change yet. The next chunk connects this function to main so you can run it.

Write the solveDFS wrapper and update main

The wrapper function hides the setup details (creating the visited grid, initializing the path) so that main only needs to call one clean function.

  • Directly below the dfs function you just added, paste the solveDFS wrapper:
vector<pair<int,int>> solveDFS(const vector<string>& maze, int startX, int startY, int endX, int endY) {
    int rows = maze.size();
    int cols = maze[0].size();
    // Create a grid to track which cells have been visited
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    vector<pair<int,int>> path;

    // Kick off the recursive search from the start position
    dfs(maze, visited, startX, startY, endX, endY, path);
    return path;
}

What does this code do?

The solveDFS function creates a 2D visited grid (all false initially) and an empty path vector. It then calls dfs to fill the path and returns whatever path was found.

Now update main() to call the solver and display the result.

  • In main(), find the line printMaze(maze, "Original Maze");.
  • Replace return 0; with the following code, then add a new return 0; at the end:
    // Solve with DFS
    vector<pair<int,int>> dfsPath = solveDFS(maze, startX, startY, endX, endY);
    if (!dfsPath.empty()) {
        // Create a copy of the maze so we don't modify the original
        vector<string> dfsMaze = maze;
        markPath(dfsMaze, dfsPath);
        printMaze(dfsMaze, "DFS Solution (finds A path)");
        cout << "DFS path length: " << dfsPath.size() - 1 << " steps" << endl;
    } else {
        cout << "DFS: No path found!" << endl;
    }

    return 0;

What does this code do?

  • It calls solveDFS to get the DFS path as a vector of coordinates.
  • It copies the original maze into dfsMaze so the original stays unmodified for later use with BFS.
  • It calls markPath to stamp * characters onto the solution copy.
  • Path length is size() - 1 because the vector includes both start and end cells, while "steps" counts the moves between cells.
  • Save main.cpp.

Seeing red squiggles in VS Code?

Make sure solveDFS is placed between the dfs function and the markPath function. In C++, functions must be defined before they are called. If solveDFS appears after main(), the compiler will not recognize it.

help me fix function ordering errors in my maze solver

✔️ Awesome, I've got everything!

Great. Double check you have saved main.cpp before compiling.

ⓧ I'd like to double check the full code

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Direction arrays: up, down, left, right
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

void printMaze(const vector<string>& maze, const string& title) {
    cout << "\n=== " << title << " ===" << endl;
    for (int i = 0; i < (int)maze.size(); i++) {
        cout << maze[i] << endl;
    }
    cout << endl;
}

bool isValid(const vector<string>& maze, const vector<vector<bool>>& visited, int x, int y) {
    int rows = maze.size();
    int cols = maze[0].size();
    return (x >= 0 && x < rows && y >= 0 && y < cols
            && maze[x][y] != '#' && !visited[x][y]);
}

bool dfs(const vector<string>& maze, vector<vector<bool>>& visited,
         int x, int y, int endX, int endY, vector<pair<int,int>>& path) {

    if (x == endX && y == endY) {
        path.push_back(make_pair(x, y));
        return true;
    }

    visited[x][y] = true;
    path.push_back(make_pair(x, y));

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (isValid(maze, visited, nx, ny)) {
            if (dfs(maze, visited, nx, ny, endX, endY, path)) {
                return true;
            }
        }
    }

    path.pop_back();
    return false;
}

vector<pair<int,int>> solveDFS(const vector<string>& maze, int startX, int startY, int endX, int endY) {
    int rows = maze.size();
    int cols = maze[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    vector<pair<int,int>> path;

    dfs(maze, visited, startX, startY, endX, endY, path);
    return path;
}

void markPath(vector<string>& maze, const vector<pair<int,int>>& path) {
    for (int i = 0; i < (int)path.size(); i++) {
        int x = path[i].first;
        int y = path[i].second;
        if (maze[x][y] != 'S' && maze[x][y] != 'E') {
            maze[x][y] = '*';
        }
    }
}

int main() {
    vector<string> maze = {
        "############",
        "#S........E#",
        "#.########.#",
        "#..........#",
        "############"
    };

    int startX = -1, startY = -1, endX = -1, endY = -1;
    for (int i = 0; i < (int)maze.size(); i++) {
        for (int j = 0; j < (int)maze[i].size(); j++) {
            if (maze[i][j] == 'S') { startX = i; startY = j; }
            if (maze[i][j] == 'E') { endX = i; endY = j; }
        }
    }

    cout << "Maze Solver: BFS vs DFS Comparison" << endl;
    cout << "S = Start, E = End, # = Wall, . = Open, * = Path" << endl;
    printMaze(maze, "Original Maze");

    // Solve with DFS
    vector<pair<int,int>> dfsPath = solveDFS(maze, startX, startY, endX, endY);
    if (!dfsPath.empty()) {
        vector<string> dfsMaze = maze;
        markPath(dfsMaze, dfsPath);
        printMaze(dfsMaze, "DFS Solution (finds A path)");
        cout << "DFS path length: " << dfsPath.size() - 1 << " steps" << endl;
    } else {
        cout << "DFS: No path found!" << endl;
    }

    return 0;
}
Compile, run, and observe the DFS solution

Time to see DFS in action. The direction arrays try up first, then down, left, and right. This means DFS dives downward before exploring sideways, producing a longer winding path rather than the direct route across row 1.

  • Compile your program by running this command in the integrated terminal:
g++ -std=c++17 -o maze_solver.exe main.cpp
  • Run the program:
.\maze_solver.exe

You should see the original maze followed by the DFS solution. The path is marked with * characters winding from S to E, and the final line prints the path length in steps.

Why is the DFS path so long?

Because the direction arrays try "up" (row -1) first and "down" (row +1) second, DFS immediately moves from row 1 down to row 3. From there it walks the entire bottom corridor before climbing back up to reach E.

DFS does not know a shorter path exists. It commits to the first viable direction and only backtracks when it hits a dead end. In the next step, BFS will find the direct 9-step path that DFS missed.

Compile errors or no output?

  • If you see "was not declared in this scope", check that dfs appears before solveDFS, and both appear before main().
  • If the maze prints but no DFS solution appears, make sure you removed the old return 0; that was immediately after printMaze(maze, "Original Maze");.
  • If you see "DFS: No path found!", check that your maze string has S and E characters with open . cells connecting them.

help me debug my DFS maze solver compile or runtime errors

Your maze solver can now find a path using DFS. Notice how DFS committed to the downward direction first and produced a winding 13-step path. Next up, you will implement BFS and see it find the direct 9-step route that DFS missed entirely.

Implement BFS

Your DFS solver finds a path through the maze, but it dives deep into one direction before trying others. This means the path it finds depends entirely on which direction it tries first.

Now you will implement Breadth-First Search (BFS), which explores all cells at distance 1, then all cells at distance 2, and so on. This level-by-level expansion guarantees it finds the shortest path every time.

In this step, get ready to:
  • Write the BFS exploration loop using a queue and parent-tracking array.
  • Reconstruct the shortest path by backtracking through the parent array.
  • Compare BFS and DFS solutions side by side.
Write the BFS exploration loop

BFS uses a queue instead of recursion. You add the start cell to the queue, then repeatedly pull the front cell off, check if it is the goal, and push all its unvisited neighbors onto the back. Because the queue is first-in-first-out, cells at distance N are always processed before cells at distance N+1.

BFS also needs a parent-tracking array. When you visit a neighbor, you record which cell you reached it from. This lets you trace back from the end to reconstruct the path later.

  • In main.cpp, find your includes at the top of the file:
#include <iostream>
#include <vector>
#include <string>
  • Replace those three includes with the following five (adding <queue> and <algorithm>):
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>

Why two new includes?

The <queue> header gives you std::queue for the BFS frontier. The <algorithm> header gives you std::reverse, which you will use to flip the reconstructed path from end-to-start into start-to-end order.

  • Now scroll down to the solveDFS function. Add this comment directly above the dfs function to label it clearly:
// --- DFS: Finds A path (not necessarily the shortest) ---
  • Now find the markPath function (directly below solveDFS). Add the first half of the solveBFS function above markPath by copying this code:
// --- BFS: Finds the SHORTEST path ---
vector<pair<int,int>> solveBFS(const vector<string>& maze, int startX, int startY, int endX, int endY) {
    int rows = maze.size();
    int cols = maze[0].size();
    // Track which cells have been visited
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    // Store where each cell was reached from (for path reconstruction)
    vector<vector<pair<int,int>>> parent(rows, vector<pair<int,int>>(cols, make_pair(-1, -1)));

    // BFS frontier queue
    queue<pair<int,int>> q;
    q.push(make_pair(startX, startY));
    visited[startX][startY] = true;

    bool found = false;

    while (!q.empty()) {
        // Pull the front cell off the queue
        pair<int,int> current = q.front();
        q.pop();
        int x = current.first;
        int y = current.second;

        // Check if we reached the end
        if (x == endX && y == endY) {
            found = true;
            break;
        }

        // Explore all 4 neighbors
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (isValid(maze, visited, nx, ny)) {
                visited[nx][ny] = true;
                parent[nx][ny] = make_pair(x, y);
                q.push(make_pair(nx, ny));
            }
        }
    }

What does this code do?

  • The parent array stores where each cell was reached from. When you visit cell (3,5) from cell (3,4), you record parent[3][5] = (3,4).
  • The queue ensures first-in-first-out processing. Cells discovered earlier (closer to start) are always explored before cells discovered later (farther from start).
  • Marking a neighbor as visited immediately (before processing it) prevents duplicate entries in the queue.

Why BFS guarantees the shortest path

Because the queue is first-in-first-out, BFS processes all cells at distance 1 from the start before any cell at distance 2. It processes all cells at distance 2 before any at distance 3. This level-by-level expansion means the first time BFS reaches the end, it arrived via the fewest possible steps.

Reconstruct the shortest path

The BFS loop tells you whether a path exists. But unlike DFS (which builds the path as it recurses), BFS only records parent pointers. You need to walk backwards from the end through the parent array to reconstruct the actual path.

  • Directly below the BFS while loop's closing brace (still inside the solveBFS function), add the path reconstruction code:
    // Reconstruct path by backtracking through parent array
    vector<pair<int,int>> path;
    if (found) {
        int cx = endX, cy = endY;
        // Walk backwards from end to start
        while (cx != startX || cy != startY) {
            path.push_back(make_pair(cx, cy));
            int px = parent[cx][cy].first;
            int py = parent[cx][cy].second;
            cx = px;
            cy = py;
        }
        path.push_back(make_pair(startX, startY));
        // Reverse to get start-to-end order
        reverse(path.begin(), path.end());
    }
    return path;
}

What does the path reconstruction do?

  • Starting at the end cell, the code looks up its parent, then looks up that cell's parent, and so on until it reaches the start. This produces a path in reverse order (end to start).
  • The reverse(path.begin(), path.end()) call flips it into the correct start-to-end order so it can be printed with markPath.
  • Save main.cpp.

Seeing a compile error about reverse?

Make sure you added #include <algorithm> at the top of the file. The reverse function lives in that header.

Also check that the closing brace of solveBFS appears before markPath. If your braces are mismatched, the compiler will report errors in unrelated places.

Help me fix my BFS compile errors

Call BFS and compare results in main

With solveBFS complete, you can now call it from main() and print a side-by-side comparison showing why BFS produces a shorter path.

  • In main(), find the DFS block that ends with:
    } else {
        cout << "DFS: No path found!" << endl;
    }
  • Add the following code below that block, replacing the existing return 0; line with this entire section:
    // Solve with BFS
    vector<pair<int,int>> bfsPath = solveBFS(maze, startX, startY, endX, endY);
    if (!bfsPath.empty()) {
        vector<string> bfsMaze = maze;
        markPath(bfsMaze, bfsPath);
        printMaze(bfsMaze, "BFS Solution (finds SHORTEST path)");
        cout << "BFS path length: " << bfsPath.size() - 1 << " steps" << endl;
    } else {
        cout << "BFS: No path found!" << endl;
    }

    // Compare
    if (!dfsPath.empty() && !bfsPath.empty()) {
        cout << "\n=== Comparison ===" << endl;
        cout << "DFS path: " << dfsPath.size() - 1 << " steps" << endl;
        cout << "BFS path: " << bfsPath.size() - 1 << " steps" << endl;
        if (dfsPath.size() > bfsPath.size()) {
            cout << "BFS found a path " << (dfsPath.size() - bfsPath.size())
                 << " steps shorter than DFS!" << endl;
            cout << "\nWhy? BFS explores ALL cells at distance N before N+1," << endl;
            cout << "guaranteeing the shortest path. DFS dives deep first." << endl;
        } else {
            cout << "Both found the same length path." << endl;
        }
    }

    return 0;
}

What does the comparison section do?

  • It prints both path lengths so you can see the numerical difference.
  • When BFS finds a shorter path (which it will on this maze), the program explains why: BFS explores all cells at distance N before moving to N+1, guaranteeing the shortest path.
  • Save main.cpp.
  • Compile and run the program by running these commands in the terminal:
g++ -std=c++17 -o maze_solver.exe main.cpp
.\maze_solver.exe

You should see the original maze, the DFS solution, the BFS solution, and a comparison section. The DFS path should be 13 steps and the BFS path should be 9 steps.

BFS path is the same length as DFS?

Check that your solveBFS function marks neighbors as visited immediately when they are enqueued, not when they are dequeued. Marking on dequeue allows duplicates in the queue and can corrupt the parent pointers.

Also verify that your path reconstruction starts at endX, endY and walks backwards to startX, startY, then reverses. Walking the wrong direction produces incorrect paths.

Help me debug my BFS implementation

✔️ Awesome, I've got everything!

Great. Double check you have saved your file.

ⓧ I'd like to double check the full code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;

// Direction arrays: up, down, left, right
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

void printMaze(const vector<string>& maze, const string& title) {
    cout << "\n=== " << title << " ===" << endl;
    for (int i = 0; i < (int)maze.size(); i++) {
        cout << maze[i] << endl;
    }
    cout << endl;
}

bool isValid(const vector<string>& maze, const vector<vector<bool>>& visited, int x, int y) {
    int rows = maze.size();
    int cols = maze[0].size();
    return (x >= 0 && x < rows && y >= 0 && y < cols
            && maze[x][y] != '#' && !visited[x][y]);
}

// --- DFS: Finds A path (not necessarily the shortest) ---
bool dfs(const vector<string>& maze, vector<vector<bool>>& visited,
         int x, int y, int endX, int endY, vector<pair<int,int>>& path) {

    if (x == endX && y == endY) {
        path.push_back(make_pair(x, y));
        return true;
    }

    visited[x][y] = true;
    path.push_back(make_pair(x, y));

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (isValid(maze, visited, nx, ny)) {
            if (dfs(maze, visited, nx, ny, endX, endY, path)) {
                return true;
            }
        }
    }

    path.pop_back();
    return false;
}

vector<pair<int,int>> solveDFS(const vector<string>& maze, int startX, int startY, int endX, int endY) {
    int rows = maze.size();
    int cols = maze[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    vector<pair<int,int>> path;

    dfs(maze, visited, startX, startY, endX, endY, path);
    return path;
}

// --- BFS: Finds the SHORTEST path ---
vector<pair<int,int>> solveBFS(const vector<string>& maze, int startX, int startY, int endX, int endY) {
    int rows = maze.size();
    int cols = maze[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    vector<vector<pair<int,int>>> parent(rows, vector<pair<int,int>>(cols, make_pair(-1, -1)));

    queue<pair<int,int>> q;
    q.push(make_pair(startX, startY));
    visited[startX][startY] = true;

    bool found = false;

    while (!q.empty()) {
        pair<int,int> current = q.front();
        q.pop();
        int x = current.first;
        int y = current.second;

        if (x == endX && y == endY) {
            found = true;
            break;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (isValid(maze, visited, nx, ny)) {
                visited[nx][ny] = true;
                parent[nx][ny] = make_pair(x, y);
                q.push(make_pair(nx, ny));
            }
        }
    }

    vector<pair<int,int>> path;
    if (found) {
        int cx = endX, cy = endY;
        while (cx != startX || cy != startY) {
            path.push_back(make_pair(cx, cy));
            int px = parent[cx][cy].first;
            int py = parent[cx][cy].second;
            cx = px;
            cy = py;
        }
        path.push_back(make_pair(startX, startY));
        reverse(path.begin(), path.end());
    }
    return path;
}

void markPath(vector<string>& maze, const vector<pair<int,int>>& path) {
    for (int i = 0; i < (int)path.size(); i++) {
        int x = path[i].first;
        int y = path[i].second;
        if (maze[x][y] != 'S' && maze[x][y] != 'E') {
            maze[x][y] = '*';
        }
    }
}

int main() {
    vector<string> maze = {
        "############",
        "#S........E#",
        "#.########.#",
        "#..........#",
        "############"
    };

    int startX = -1, startY = -1, endX = -1, endY = -1;
    for (int i = 0; i < (int)maze.size(); i++) {
        for (int j = 0; j < (int)maze[i].size(); j++) {
            if (maze[i][j] == 'S') { startX = i; startY = j; }
            if (maze[i][j] == 'E') { endX = i; endY = j; }
        }
    }

    cout << "Maze Solver: BFS vs DFS Comparison" << endl;
    cout << "S = Start, E = End, # = Wall, . = Open, * = Path" << endl;
    printMaze(maze, "Original Maze");

    // Solve with DFS
    vector<pair<int,int>> dfsPath = solveDFS(maze, startX, startY, endX, endY);
    if (!dfsPath.empty()) {
        vector<string> dfsMaze = maze;
        markPath(dfsMaze, dfsPath);
        printMaze(dfsMaze, "DFS Solution (finds A path)");
        cout << "DFS path length: " << dfsPath.size() - 1 << " steps" << endl;
    } else {
        cout << "DFS: No path found!" << endl;
    }

    // Solve with BFS
    vector<pair<int,int>> bfsPath = solveBFS(maze, startX, startY, endX, endY);
    if (!bfsPath.empty()) {
        vector<string> bfsMaze = maze;
        markPath(bfsMaze, bfsPath);
        printMaze(bfsMaze, "BFS Solution (finds SHORTEST path)");
        cout << "BFS path length: " << bfsPath.size() - 1 << " steps" << endl;
    } else {
        cout << "BFS: No path found!" << endl;
    }

    // Compare
    if (!dfsPath.empty() && !bfsPath.empty()) {
        cout << "\n=== Comparison ===" << endl;
        cout << "DFS path: " << dfsPath.size() - 1 << " steps" << endl;
        cout << "BFS path: " << bfsPath.size() - 1 << " steps" << endl;
        if (dfsPath.size() > bfsPath.size()) {
            cout << "BFS found a path " << (dfsPath.size() - bfsPath.size())
                 << " steps shorter than DFS!" << endl;
            cout << "\nWhy? BFS explores ALL cells at distance N before N+1," << endl;
            cout << "guaranteeing the shortest path. DFS dives deep first." << endl;
        } else {
            cout << "Both found the same length path." << endl;
        }
    }

    return 0;
}

You now have both algorithms solving the same maze. The visual difference in the output makes it clear that BFS always finds the optimal route. Next, you will experiment with different mazes and direction orders to deepen your understanding of how these algorithms behave.

Analyze and Experiment

You have two working solvers that produce different paths on the same maze. The theory is clear: BFS guarantees shortest paths, DFS does not. But how do these algorithms actually behave under different conditions?

In this step, you'll stress-test both algorithms by changing the maze, changing the exploration order, and measuring how much work each algorithm does. This builds the intuition that separates knowing an algorithm from truly understanding it.

In this step, get ready to:
  • Test both algorithms on a second, larger maze.
  • Change DFS direction priority and observe how it affects the path.
  • Add node exploration counters to measure how much work each algorithm performs.
Add a second maze to test both algorithms

Your current maze is small and simple. A larger maze with more branching paths makes the difference between DFS and BFS more dramatic.

  • In main.cpp, find your main() function.
  • Add this second maze right after the comparison section (before return 0;) by copying the following code:
    // --- Test with a larger maze ---
    vector<string> maze2 = {
        "################",
        "#S.#...........#",
        "#..#.#########.#",
        "#..#.#.........#",
        "#..#.#.#########",
        "#....#........E#",
        "################"
    };

    int startX2 = -1, startY2 = -1, endX2 = -1, endY2 = -1;
    for (int i = 0; i < (int)maze2.size(); i++) {
        for (int j = 0; j < (int)maze2[i].size(); j++) {
            if (maze2[i][j] == 'S') { startX2 = i; startY2 = j; }
            if (maze2[i][j] == 'E') { endX2 = i; endY2 = j; }
        }
    }

    cout << "\n\n--- MAZE 2 (larger) ---" << endl;
    printMaze(maze2, "Original Maze 2");

    vector<pair<int,int>> dfsPath2 = solveDFS(maze2, startX2, startY2, endX2, endY2);
    if (!dfsPath2.empty()) {
        vector<string> dfsMaze2 = maze2;
        markPath(dfsMaze2, dfsPath2);
        printMaze(dfsMaze2, "DFS Solution - Maze 2");
        cout << "DFS path length: " << dfsPath2.size() - 1 << " steps" << endl;
    }

    vector<pair<int,int>> bfsPath2 = solveBFS(maze2, startX2, startY2, endX2, endY2);
    if (!bfsPath2.empty()) {
        vector<string> bfsMaze2 = maze2;
        markPath(bfsMaze2, bfsPath2);
        printMaze(bfsMaze2, "BFS Solution - Maze 2");
        cout << "BFS path length: " << bfsPath2.size() - 1 << " steps" << endl;
    }

What does this code do?

This defines a 7x16 maze with more walls and dead ends. The start is in the top-left corner and the end is in the bottom-right, forcing both algorithms to navigate a longer, more complex path.

The code reuses your existing solveDFS and solveBFS functions on this new maze, then prints both solutions for comparison.

  • Save main.cpp.
  • Compile and run the program by running these commands in your terminal:
g++ -std=c++17 -o maze_solver.exe main.cpp
.\maze_solver.exe
  • Observe the path lengths for both algorithms on the second maze. The gap between DFS and BFS path lengths grows as the maze gets more complex.

Why does complexity matter?

In a simple maze with few branching paths, DFS might stumble onto the shortest path by luck. In a complex maze with many dead ends, DFS dives deep into wrong turns before backtracking. BFS ignores complexity because it always explores level by level.

  • Now remove the second maze code you just added (everything from the // --- Test with a larger maze --- comment down to the closing brace of the second BFS if block). You will keep the file focused on the original maze for the remaining experiments.
Change the DFS direction priority and observe the effect

DFS explores directions in the order they appear in your dx[] and dy[] arrays. Changing that order changes which path DFS finds first. BFS, by contrast, always finds the same shortest path regardless of direction order.

  • In main.cpp, find these lines near the top of the file:
// Direction arrays: up, down, left, right
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
  • Temporarily change the direction order to try right first instead of up first. Replace those three lines with:
// Direction arrays: right, down, left, up
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
  • Save main.cpp, compile, and run:
g++ -std=c++17 -o maze_solver.exe main.cpp
.\maze_solver.exe

Compare the DFS output to what you saw before. The DFS path is different now because it tries going right first instead of up. The BFS path is exactly the same length and shape as before.

Why does direction order affect DFS but not BFS?

DFS commits to the first valid direction it finds and dives deep before trying alternatives. Whichever direction is listed first in the array gets priority. BFS adds ALL valid neighbors to the queue at the same level, so the order they're added doesn't change which cell gets discovered at the shortest distance.

  • Now revert the direction arrays back to their original order. Replace the direction lines with:
// Direction arrays: up, down, left, right
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
  • Save main.cpp before moving on to the next experiment.
Add node exploration counters to both algorithms

Path length tells you the quality of the result. But how much work did the algorithm do to find that result? Counting explored nodes reveals the computational cost of each approach.

  • In main.cpp, find your dfs function. Replace the entire function with this updated version that accepts and increments a counter:
// --- DFS: Finds A path (not necessarily the shortest) ---
bool dfs(const vector<string>& maze, vector<vector<bool>>& visited,
         int x, int y, int endX, int endY, vector<pair<int,int>>& path, int& nodesExplored) {

    nodesExplored++;

    if (x == endX && y == endY) {
        path.push_back(make_pair(x, y));
        return true;
    }

    visited[x][y] = true;
    path.push_back(make_pair(x, y));

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (isValid(maze, visited, nx, ny)) {
            if (dfs(maze, visited, nx, ny, endX, endY, path, nodesExplored)) {
                return true;
            }
        }
    }

    path.pop_back();
    return false;
}

What changed?

The function now takes an int& nodesExplored parameter passed by reference. Every time dfs is called (including recursive calls), it increments this counter. This counts every cell the algorithm visits, including dead ends it backtracks from.

  • Now find the solveDFS wrapper function directly below dfs. Replace it with this updated version:
vector<pair<int,int>> solveDFS(const vector<string>& maze, int startX, int startY, int endX, int endY, int& nodesExplored) {
    int rows = maze.size();
    int cols = maze[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    vector<pair<int,int>> path;
    nodesExplored = 0;
    dfs(maze, visited, startX, startY, endX, endY, path, nodesExplored);
    return path;
}

What does this code do?

The wrapper initializes nodesExplored to 0 before the search begins, then passes it into dfs. After solveDFS returns, the caller can read the total count through the reference.

  • Next, find the solveBFS function. Replace it with this updated version that also counts explored nodes:
// --- BFS: Finds the SHORTEST path ---
vector<pair<int,int>> solveBFS(const vector<string>& maze, int startX, int startY, int endX, int endY, int& nodesExplored) {
    int rows = maze.size();
    int cols = maze[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    vector<vector<pair<int,int>>> parent(rows, vector<pair<int,int>>(cols, make_pair(-1, -1)));

    queue<pair<int,int>> q;
    q.push(make_pair(startX, startY));
    visited[startX][startY] = true;
    nodesExplored = 0;

    bool found = false;

    while (!q.empty()) {
        pair<int,int> current = q.front();
        q.pop();
        int x = current.first;
        int y = current.second;
        nodesExplored++;

        if (x == endX && y == endY) {
            found = true;
            break;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (isValid(maze, visited, nx, ny)) {
                visited[nx][ny] = true;
                parent[nx][ny] = make_pair(x, y);
                q.push(make_pair(nx, ny));
            }
        }
    }

    vector<pair<int,int>> path;
    if (found) {
        int cx = endX, cy = endY;
        while (cx != startX || cy != startY) {
            path.push_back(make_pair(cx, cy));
            int px = parent[cx][cy].first;
            int py = parent[cx][cy].second;
            cx = px;
            cy = py;
        }
        path.push_back(make_pair(startX, startY));
        reverse(path.begin(), path.end());
    }
    return path;
}

Where does the counter increment in BFS?

The counter increments each time a cell is popped from the queue and processed. This counts every cell BFS examines, including the final cell where it finds the end. BFS typically explores more cells than DFS because it spreads outward in all directions simultaneously.

  • Finally, update main() to declare counter variables and pass them to the solver functions. Find the DFS section in main() that starts with:
    // Solve with DFS
    vector<pair<int,int>> dfsPath = solveDFS(maze, startX, startY, endX, endY);
  • Replace the entire DFS section (from the // Solve with DFS comment through the closing brace of its else block) with this updated version:
    // Solve with DFS
    int dfsNodes = 0;
    vector<pair<int,int>> dfsPath = solveDFS(maze, startX, startY, endX, endY, dfsNodes);
    if (!dfsPath.empty()) {
        vector<string> dfsMaze = maze;
        markPath(dfsMaze, dfsPath);
        printMaze(dfsMaze, "DFS Solution (finds A path)");
        cout << "DFS path length: " << dfsPath.size() - 1 << " steps" << endl;
        cout << "DFS nodes explored: " << dfsNodes << endl;
    } else {
        cout << "DFS: No path found!" << endl;
    }
  • Now find the BFS section that starts with:
    // Solve with BFS
    vector<pair<int,int>> bfsPath = solveBFS(maze, startX, startY, endX, endY);
  • Replace the entire BFS section (from the // Solve with BFS comment through the closing brace of its else block) with this updated version:
    // Solve with BFS
    int bfsNodes = 0;
    vector<pair<int,int>> bfsPath = solveBFS(maze, startX, startY, endX, endY, bfsNodes);
    if (!bfsPath.empty()) {
        vector<string> bfsMaze = maze;
        markPath(bfsMaze, bfsPath);
        printMaze(bfsMaze, "BFS Solution (finds SHORTEST path)");
        cout << "BFS path length: " << bfsPath.size() - 1 << " steps" << endl;
        cout << "BFS nodes explored: " << bfsNodes << endl;
    } else {
        cout << "BFS: No path found!" << endl;
    }

What do the node counts tell you?

DFS may explore fewer nodes because it commits to one direction and gets lucky. BFS explores more broadly because it checks every cell at distance N before moving to N+1. The tradeoff is clear: BFS does more work but guarantees the optimal result.

  • Save main.cpp.
  • Compile and run your program:
g++ -std=c++17 -o maze_solver.exe main.cpp
.\maze_solver.exe
  • You should see the DFS and BFS solutions printed as before, but now each includes a "nodes explored" count below the path length.

Seeing a compilation error?

  • If you see an error about "too few arguments", make sure you updated both the function definitions AND the calls in main() to pass the counter variable.
  • If you see an error about "no matching function", check that solveDFS and solveBFS both have int& nodesExplored as their last parameter.
  • Make sure the internal dfs call inside solveDFS also passes nodesExplored as the last argument.

Help me fix a compilation error in my maze solver after adding nodesExplored counters.

✔️ Awesome, I've got everything!

Great. Double check you've saved your file.

ⓧ I'd like to double check the full code

Here is the complete main.cpp file at this point:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;

// Direction arrays: up, down, left, right
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

void printMaze(const vector<string>& maze, const string& title) {
    cout << "\n=== " << title << " ===" << endl;
    for (int i = 0; i < (int)maze.size(); i++) {
        cout << maze[i] << endl;
    }
    cout << endl;
}

bool isValid(const vector<string>& maze, const vector<vector<bool>>& visited, int x, int y) {
    int rows = maze.size();
    int cols = maze[0].size();
    return (x >= 0 && x < rows && y >= 0 && y < cols
            && maze[x][y] != '#' && !visited[x][y]);
}

// --- DFS: Finds A path (not necessarily the shortest) ---
bool dfs(const vector<string>& maze, vector<vector<bool>>& visited,
         int x, int y, int endX, int endY, vector<pair<int,int>>& path, int& nodesExplored) {

    nodesExplored++;

    if (x == endX && y == endY) {
        path.push_back(make_pair(x, y));
        return true;
    }

    visited[x][y] = true;
    path.push_back(make_pair(x, y));

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (isValid(maze, visited, nx, ny)) {
            if (dfs(maze, visited, nx, ny, endX, endY, path, nodesExplored)) {
                return true;
            }
        }
    }

    path.pop_back();
    return false;
}

vector<pair<int,int>> solveDFS(const vector<string>& maze, int startX, int startY, int endX, int endY, int& nodesExplored) {
    int rows = maze.size();
    int cols = maze[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    vector<pair<int,int>> path;
    nodesExplored = 0;
    dfs(maze, visited, startX, startY, endX, endY, path, nodesExplored);
    return path;
}

// --- BFS: Finds the SHORTEST path ---
vector<pair<int,int>> solveBFS(const vector<string>& maze, int startX, int startY, int endX, int endY, int& nodesExplored) {
    int rows = maze.size();
    int cols = maze[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    vector<vector<pair<int,int>>> parent(rows, vector<pair<int,int>>(cols, make_pair(-1, -1)));

    queue<pair<int,int>> q;
    q.push(make_pair(startX, startY));
    visited[startX][startY] = true;
    nodesExplored = 0;

    bool found = false;

    while (!q.empty()) {
        pair<int,int> current = q.front();
        q.pop();
        int x = current.first;
        int y = current.second;
        nodesExplored++;

        if (x == endX && y == endY) {
            found = true;
            break;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (isValid(maze, visited, nx, ny)) {
                visited[nx][ny] = true;
                parent[nx][ny] = make_pair(x, y);
                q.push(make_pair(nx, ny));
            }
        }
    }

    vector<pair<int,int>> path;
    if (found) {
        int cx = endX, cy = endY;
        while (cx != startX || cy != startY) {
            path.push_back(make_pair(cx, cy));
            int px = parent[cx][cy].first;
            int py = parent[cx][cy].second;
            cx = px;
            cy = py;
        }
        path.push_back(make_pair(startX, startY));
        reverse(path.begin(), path.end());
    }
    return path;
}

void markPath(vector<string>& maze, const vector<pair<int,int>>& path) {
    for (int i = 0; i < (int)path.size(); i++) {
        int x = path[i].first;
        int y = path[i].second;
        if (maze[x][y] != 'S' && maze[x][y] != 'E') {
            maze[x][y] = '*';
        }
    }
}

int main() {
    vector<string> maze = {
        "############",
        "#S........E#",
        "#.########.#",
        "#..........#",
        "############"
    };

    int startX = -1, startY = -1, endX = -1, endY = -1;
    for (int i = 0; i < (int)maze.size(); i++) {
        for (int j = 0; j < (int)maze[i].size(); j++) {
            if (maze[i][j] == 'S') { startX = i; startY = j; }
            if (maze[i][j] == 'E') { endX = i; endY = j; }
        }
    }

    cout << "Maze Solver: BFS vs DFS Comparison" << endl;
    cout << "S = Start, E = End, # = Wall, . = Open, * = Path" << endl;
    printMaze(maze, "Original Maze");

    // Solve with DFS
    int dfsNodes = 0;
    vector<pair<int,int>> dfsPath = solveDFS(maze, startX, startY, endX, endY, dfsNodes);
    if (!dfsPath.empty()) {
        vector<string> dfsMaze = maze;
        markPath(dfsMaze, dfsPath);
        printMaze(dfsMaze, "DFS Solution (finds A path)");
        cout << "DFS path length: " << dfsPath.size() - 1 << " steps" << endl;
        cout << "DFS nodes explored: " << dfsNodes << endl;
    } else {
        cout << "DFS: No path found!" << endl;
    }

    // Solve with BFS
    int bfsNodes = 0;
    vector<pair<int,int>> bfsPath = solveBFS(maze, startX, startY, endX, endY, bfsNodes);
    if (!bfsPath.empty()) {
        vector<string> bfsMaze = maze;
        markPath(bfsMaze, bfsPath);
        printMaze(bfsMaze, "BFS Solution (finds SHORTEST path)");
        cout << "BFS path length: " << bfsPath.size() - 1 << " steps" << endl;
        cout << "BFS nodes explored: " << bfsNodes << endl;
    } else {
        cout << "BFS: No path found!" << endl;
    }

    // Compare
    if (!dfsPath.empty() && !bfsPath.empty()) {
        cout << "\n=== Comparison ===" << endl;
        cout << "DFS path: " << dfsPath.size() - 1 << " steps" << endl;
        cout << "BFS path: " << bfsPath.size() - 1 << " steps" << endl;
        if (dfsPath.size() > bfsPath.size()) {
            cout << "BFS found a path " << (dfsPath.size() - bfsPath.size())
                 << " steps shorter than DFS!" << endl;
            cout << "\nWhy? BFS explores ALL cells at distance N before N+1," << endl;
            cout << "guaranteeing the shortest path. DFS dives deep first." << endl;
        } else {
            cout << "Both found the same length path." << endl;
        }
    }

    return 0;
}

Secret mission

Add A* Search

You've seen that BFS guarantees the shortest path but explores cells broadly. What if there was a way to find the shortest path while exploring fewer cells? A* search uses a heuristic to guide the search toward the goal, combining the best of BFS (optimality) with smarter exploration. Add A* to your maze solver and compare its efficiency against BFS.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your resources running, pause them to come back later, or delete them entirely.

Resources you used:

  • The maze-solver project folder on your Desktop.
  • The Microsoft C/C++ extension in VS Code.
  • MSYS2/MinGW-w64 (if you installed it during Step 1).

Keep everything running

No action needed. Choose this if you plan to keep experimenting with the maze solver or want to use g++ for other C++ projects.

  • Your maze-solver folder stays on your Desktop.
  • The C/C++ extension continues providing IntelliSense and syntax highlighting for any C++ work.
  • MSYS2/MinGW-w64 remains available for compiling future C++ programs.

Pause - I'll come back to this later

Since this is a local project with no running processes, there is nothing to pause. Your files will be waiting for you when you return.

  • No background services are running from this project.
  • Your main.cpp file and compiled executable stay on disk until you delete them.

Delete - I don't want to use this again

Remove all project resources and start fresh. Follow the steps below for each resource you want to remove.

  • Delete the project folder. Open your terminal and run the command for your operating system.

macOS

rm -rf ~/Desktop/maze-solver

Windows

rmdir /s /q %USERPROFILE%\Desktop\maze-solver
  • Uninstall the C/C++ extension. In VS Code, open the Extensions panel (Ctrl+Shift+X). Find the Microsoft C/C++ extension, click the gear icon next to it, and select Uninstall.
  • Uninstall MSYS2/MinGW-w64 (Windows only, if you installed it during this project). Open Settings, then Apps, then Installed apps. Search for MSYS2, click the three-dot menu, and select Uninstall.

Nice Work!

Nice Work!

You just built a command-line maze solver in C++ that visually proves why BFS finds the shortest path while DFS does not.

You've learned how to:

  • Built a maze solver that represents mazes as 2D grids and visually displays solutions with path markers in the console.
  • Implemented recursive DFS with backtracking and queue-based BFS with parent-tracking path reconstruction, two core graph traversal patterns that appear in coding interviews.
  • Compared algorithm behavior by experimenting with direction priority, multiple mazes, and node-exploration counters to understand when each approach is the right choice.
  • Secret Mission: Implemented A* search with a Manhattan distance heuristic and demonstrated how informed search finds optimal paths while exploring fewer nodes than BFS.

Ready to quiz yourself?