COMP2521 Week 7 - Maze Solving (BFS & DFS)

📊 Mazes as Graphs 📊 迷宫即图

A maze can be represented as a graph where each cell is a vertex and adjacent cells (non-wall) are connected by edges. 迷宫可以表示为图，每个格子是顶点，相邻的非墙格子通过边连接。

Grid Representation:网格表示：

Vertex = each cell in the grid (identified by row, col)顶点 = 网格中的每个格子（由 row, col 标识）
Edge = connection between adjacent non-wall cells (up/down/left/right)边 = 相邻非墙格子之间的连接（上/下/左/右）
Wall cells are NOT vertices — they block movement墙格子不是顶点 — 它们阻挡移动

Key Data Structures 关键数据结构

struct cell {
    int row;  // vertical position (0 = top)
    int col;  // horizontal position (0 = left)
};

// Maze ADT provides:
MazeHeight(m)     → total rows
MazeWidth(m)      → total columns
MazeGetStart(m)   → starting cell
MazeIsWall(m, c)  → is this cell a wall?
MazeVisit(m, c)   → visit cell; returns true if it's the exit
MazeMarkPath(m, c)→ mark cell as part of solution path

Neighbour Calculation:邻居计算：

There are no MazeGetNorth/South/East/West functions! Calculate neighbours manually:没有 MazeGetNorth/South/East/West 函数！需要手动计算邻居：

struct cell neighbours[4] = {
    {v.row - 1, v.col},  // North (up)
    {v.row + 1, v.col},  // South (down)
    {v.row, v.col + 1},  // East  (right)
    {v.row, v.col - 1}   // West  (left)
};

⚠️ Boundary Check Required:必须进行边界检查：

Always check w.row >= 0 && w.row < height && w.col >= 0 && w.col < width before accessing a neighbour!在访问邻居前务必检查 w.row >= 0 && w.row < height && w.col >= 0 && w.col < width！

Helper Matrices (matrix.h) 辅助矩阵（matrix.h）

// Track visited cells
bool **visited = createBoolMatrix(height, width);
freeBoolMatrix(visited);

// Track predecessors (for path reconstruction)
struct cell **predecessor = createCellMatrix(height, width);
freeCellMatrix(predecessor);

🔍 Task 1: BFS Maze Solver 🔍 任务 1：BFS 迷宫求解

Breadth-First Search explores cells layer by layer, starting from the start cell. It guarantees finding the shortest path. 广度优先搜索逐层探索格子，从起点开始。保证找到最短路径。

TASK 1 Algorithm Overview 算法概述

BFS Pattern:BFS 模式：

Create visited[][] and predecessor[][] matrices创建 visited[][] 和 predecessor[][] 矩阵
Create Queue, enqueue start cell, mark start as visited创建队列，起点入队，标记起点为已访问
While queue not empty: dequeue cell, MazeVisit it, check neighbours队列非空时：出队格子，MazeVisit 访问，检查邻居
When MazeVisit returns true → found exit! Trace back using predecessor当 MazeVisit 返回 true → 找到出口！沿 predecessor 回溯路径
Free all allocated memory释放所有分配的内存

Complete BFS Code 完整 BFS 代码

bool solve(Maze m) {
    int height = MazeHeight(m);
    int width = MazeWidth(m);
    bool **visited = createBoolMatrix(height, width);
    struct cell **predecessor = createCellMatrix(height, width);

    Queue q = QueueNew();
    struct cell start = MazeGetStart(m);
    QueueEnqueue(q, start);
    visited[start.row][start.col] = true;

    struct cell found = {-1, -1};

    while (!QueueIsEmpty(q)) {
        struct cell v = QueueDequeue(q);

        if (MazeVisit(m, v)) {
            found = v;
            break;
        }

        struct cell neighbours[4] = {
            {v.row - 1, v.col},  // N
            {v.row + 1, v.col},  // S
            {v.row, v.col + 1},  // E
            {v.row, v.col - 1}   // W
        };

        for (int i = 0; i < 4; i++) {
            struct cell w = neighbours[i];
            if (w.row >= 0 && w.row < height &&
                w.col >= 0 && w.col < width &&
                !MazeIsWall(m, w) && !visited[w.row][w.col]) {
                visited[w.row][w.col] = true;
                predecessor[w.row][w.col] = v;
                QueueEnqueue(q, w);
            }
        }
    }

    bool result = false;
    if (found.row != -1) {
        struct cell curr = found;
        while (curr.row != start.row || curr.col != start.col) {
            MazeMarkPath(m, curr);
            curr = predecessor[curr.row][curr.col];
        }
        MazeMarkPath(m, start);
        result = true;
    }

    freeBoolMatrix(visited);
    freeCellMatrix(predecessor);
    QueueFree(q);
    return result;
}

Key Insight: Mark visited WHEN ENQUEUING关键洞察：入队时标记已访问

In BFS, we mark visited when adding to the queue, NOT when dequeueing. This prevents the same cell from being added to the queue multiple times.在 BFS 中，我们在入队时标记 visited，而不是出队时。这防止同一个格子被多次加入队列。

Path Reconstruction:路径重建：

The predecessor matrix acts as "breadcrumbs". From the exit, follow predecessor[curr.row][curr.col] back to the start, calling MazeMarkPath on each cell.predecessor 矩阵像"面包屑"。从终点沿 predecessor[curr.row][curr.col] 走回起点，对每个格子调用 MazeMarkPath。

🔍 Task 2: DFS Maze Solver 🔍 任务 2：DFS 迷宫求解

Depth-First Search goes as deep as possible along one path before backtracking. Uses a Stack instead of a Queue. 深度优先搜索沿着一条路径尽可能深入，然后回溯。使用栈代替队列。

TASK 2 DFS vs BFS: Critical Differences DFS vs BFS：关键区别

BFS (Breadth-First) BFS（广度优先）

Uses Queue (FIFO)使用队列（先进先出）
Marks visited when enqueuing入队时标记已访问
Explores layer by layer逐层探索
Finds shortest path找到最短路径

DFS (Depth-First) DFS（深度优先）

Uses Stack (LIFO)使用栈（后进先出）
Marks visited when popping弹出时标记已访问
Explores one path deeply深入一条路径探索
Does NOT guarantee shortest path不保证最短路径

Complete DFS Code 完整 DFS 代码

bool solve(Maze m) {
    int height = MazeHeight(m);
    int width = MazeWidth(m);
    bool **visited = createBoolMatrix(height, width);
    struct cell **predecessor = createCellMatrix(height, width);

    Stack s = StackNew();
    struct cell start = MazeGetStart(m);
    StackPush(s, start);
    // Note: start is NOT marked visited yet!

    struct cell found = {-1, -1};

    while (!StackIsEmpty(s)) {
        struct cell v = StackPop(s);

        // KEY DIFFERENCE: Check visited AFTER popping
        if (visited[v.row][v.col]) {
            continue;
        }
        visited[v.row][v.col] = true;

        if (MazeVisit(m, v)) {
            found = v;
            break;
        }

        struct cell neighbours[4] = {
            {v.row - 1, v.col},
            {v.row + 1, v.col},
            {v.row, v.col + 1},
            {v.row, v.col - 1}
        };

        for (int i = 0; i < 4; i++) {
            struct cell w = neighbours[i];
            if (w.row >= 0 && w.row < height &&
                w.col >= 0 && w.col < width &&
                !MazeIsWall(m, w) && !visited[w.row][w.col]) {
                predecessor[w.row][w.col] = v;
                StackPush(s, w);
                // Note: NOT marking visited here!
            }
        }
    }

    // Path reconstruction (same as BFS)
    bool result = false;
    if (found.row != -1) {
        struct cell curr = found;
        while (curr.row != start.row || curr.col != start.col) {
            MazeMarkPath(m, curr);
            curr = predecessor[curr.row][curr.col];
        }
        MazeMarkPath(m, start);
        result = true;
    }

    freeBoolMatrix(visited);
    freeCellMatrix(predecessor);
    StackFree(s);
    return result;
}

⚠️ Why DFS checks visited AFTER popping:为什么 DFS 在弹出后检查 visited：

The same cell can be pushed onto the stack multiple times (by different neighbours). We only check visited when we pop, so we can skip cells that were already processed. If we marked visited when pushing, we'd lose the "deepest first" behaviour.同一个格子可能被不同的邻居多次压入栈。我们只在弹出时检查 visited，这样可以跳过已经处理过的格子。如果在压入时标记 visited，就会失去"深度优先"的行为。

⏱️ Task 3: Time Complexity Analysis ⏱️ 任务 3：时间复杂度分析

Given a maze with n cells total (n = width x height): 给定一个共有 n 个格子的迷宫（n = width x height）：

Algorithm算法	Worst Case最坏情况	Explanation解释
BFS	O(n)	Each cell visited once (O(n)). Each cell has ≤ 4 neighbours checked (O(4n)). Total: O(n) + O(4n) = O(n).每个格子最多访问一次 (O(n))。每个格子检查 ≤ 4 个邻居 (O(4n))。总计：O(n) + O(4n) = O(n)。
DFS	O(n)	Each cell pushed ≤ 4 times (once per neighbour), but visited only once. Total stack ops ≤ 4n, each O(1). Overall O(n).每个格子最多被压入 4 次（每个邻居一次），但只访问一次。总栈操作 ≤ 4n，每次 O(1)。总体 O(n)。

Why Both Are O(n)?为什么两者都是 O(n)？

Both algorithms visit each cell at most once两种算法每个格子最多访问一次
For each cell, we check ≤ 4 edges (constant factor)对每个格子，检查 ≤ 4 条边（常数因子）
The ORDER of visiting differs, but the TOTAL WORK is the same访问的顺序不同，但总工作量相同
Ignore the maze-displaying code in complexity analysis在复杂度分析中忽略迷宫显示代码

💡 Common Mistakes & Tips 💡 常见错误与技巧

⚠️ BFS Mistakes:BFS 错误：

Forgetting to mark start cell as visited before the loop忘记在循环前标记起点为已访问
Marking visited when dequeueing instead of when enqueuing (causes duplicates)出队时而不是入队时标记 visited（导致重复）
Not checking MazeVisit's return value to detect the exit不检查 MazeVisit 的返回值来检测出口
Forgetting to mark the start cell with MazeMarkPath忘记用 MazeMarkPath 标记起点

⚠️ DFS Mistakes:DFS 错误：

Marking visited when pushing (breaks DFS behaviour!)压入时标记 visited（破坏 DFS 行为！）
Missing the if (visited) continue; check after popping弹出后缺少 if (visited) continue; 检查
Not doing boundary checks before accessing neighbour cells访问邻居格子前不做边界检查
Function name typos: Stackpush → StackPush, StaclFree → StackFree函数名拼写错误：Stackpush → StackPush，StaclFree → StackFree

Memory Management Checklist:内存管理清单：

freeBoolMatrix(visited) — free visited arrayfreeBoolMatrix(visited) — 释放 visited 数组
freeCellMatrix(predecessor) — free predecessor arrayfreeCellMatrix(predecessor) — 释放 predecessor 数组
QueueFree(q) or StackFree(s) — free data structureQueueFree(q) 或 StackFree(s) — 释放数据结构