Week 07 Lab Solution

Graph Search Algorithms and Maze Solvers

Sample Solutions

solveBfs
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#define MAX_NEIGHBOURS 4

static void fillPath(Maze m, struct cell start, struct cell exit,
                     struct cell **pred);
static bool validCell(Maze m, struct cell c);

bool solve(Maze m) {
    int height = MazeHeight(m);
    int width = MazeWidth(m);

    bool **visited = createBoolMatrix(height, width);
    struct cell **pred = createCellMatrix(height, width);
    Queue q = QueueNew();

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

    bool found = false;
    while (!found && !QueueIsEmpty(q)) {
        struct cell v = QueueDequeue(q);

        if (MazeVisit(m, v)) {
            fillPath(m, start, v, pred);
            found = true;
            break;
        }

        struct cell adj[MAX_NEIGHBOURS] = {
            { .row = v.row - 1, .col = v.col     }, // up
            { .row = v.row,     .col = v.col + 1 }, // right
            { .row = v.row + 1, .col = v.col     }, // down
            { .row = v.row,     .col = v.col - 1 }, // left
        };

        for (int i = 0; i < MAX_NEIGHBOURS; i++) {
            struct cell w = adj[i];
            if (validCell(m, w) && !MazeIsWall(m, w) && !visited[w.row][w.col]) {
                visited[w.row][w.col] = true;
                pred[w.row][w.col] = v;
                QueueEnqueue(q, w);
            }
        }
    }

    freeBoolMatrix(visited);
    freeCellMatrix(pred);
    QueueFree(q);

    return found;
}

static void fillPath(Maze m, struct cell start, struct cell exit,
                     struct cell **pred) {
    struct cell curr = exit;
    while (!(curr.col == start.col && curr.row == start.row)) {
        MazeMarkPath(m, curr);
        curr = pred[curr.row][curr.col];
    }
    MazeMarkPath(m, start);
}

static bool validCell(Maze m, struct cell c) {
    return (
        c.row >= 0 && c.row < MazeHeight(m) &&
        c.col >= 0 && c.col < MazeWidth(m)
    );
}
solveDfs
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#define MAX_NEIGHBOURS 4

static void fillPath(Maze m, struct cell start, struct cell exit,
                     struct cell **pred);
static bool validCell(Maze m, struct cell c);

bool solve(Maze m) {
    int height = MazeHeight(m);
    int width = MazeWidth(m);

    bool **visited = createBoolMatrix(height, width);
    struct cell **pred = createCellMatrix(height, width);
    Stack s = StackNew();

    struct cell start = MazeGetStart(m);
    StackPush(s, start);

    bool found = false;
    while (!found && !StackIsEmpty(s)) {
        struct cell v = StackPop(s);

        if (visited[v.row][v.col]) {
            continue;
        }

        visited[v.row][v.col] = true;
        if (MazeVisit(m, v)) {
            fillPath(m, start, v, pred);
            found = true;
            break;
        }

        struct cell adj[MAX_NEIGHBOURS] = {
            { .row = v.row - 1, .col = v.col     }, // up
            { .row = v.row,     .col = v.col + 1 }, // right
            { .row = v.row + 1, .col = v.col     }, // down
            { .row = v.row,     .col = v.col - 1 }, // left
        };

        for (int i = 0; i < MAX_NEIGHBOURS; i++) {
            struct cell w = adj[i];
            if (validCell(m, w) && !MazeIsWall(m, w) && !visited[w.row][w.col]) {
                pred[w.row][w.col] = v;
                StackPush(s, w);
            }
        }
    }

    freeBoolMatrix(visited);
    freeCellMatrix(pred);
    StackFree(s);

    return found;
}

static void fillPath(Maze m, struct cell start, struct cell exit,
                     struct cell **pred) {
    struct cell curr = exit;
    while (!(curr.col == start.col && curr.row == start.row)) {
        MazeMarkPath(m, curr);
        curr = pred[curr.row][curr.col];
    }
    MazeMarkPath(m, start);
}

static bool validCell(Maze m, struct cell c) {
    return (
        c.row >= 0 && c.row < MazeHeight(m) &&
        c.col >= 0 && c.col < MazeWidth(m)
    );
}
Complexity Analysis

Note: The correct answer will differ depending on the implementation. These answers are for the above implementations.

============
  solveBfs
============

- Worst case time complexity: O(n)

============
  solveDfs
============

- Worst case time complexity: O(n)