COMP2521 21T1 - Week 07 Lab Solution PDF

Preview

Summary

COMP2521 21T1 - Week 07 Lab Solution...

Description

solveBfs

1

#define MAX_NEIGHBOURS 4

2 3

static void fillPath(Maze m, Cell start, Cell exit, Cell **pred);

4 5

static bool validCell(Maze m, Cell c);

6

bool solve(Maze m) {

7

int height = MazeHeight(m);

8 9

int width = MazeWidth(m);

10

bool **visited = createBoolMatrix(height, width);

11

Cell **pred = createCellMatrix(height, width);

12 13

Queue q = QueueNew();

14 15

Cell start = MazeGetStart(m);

16 17

QueueEnqueue(q, start);

18

bool found = false;

19

while (!found && !QueueIsEmpty(q)) {

20 21

Cell v = QueueDequeue(q);

22

if (visited[v.row][v.col]) {

23

continue;

24 25

}

26

visited[v.row][v.col] = true;

27

if (MazeVisit(m, v)) {

28 29

fillPath(m, start, v, pred); found = true;

30

break;

31

}

32 33

Cell adj[MAX_NEIGHBOURS] = {

34

{ .row = v.row - 1, .col = v.col

35

{ .row = v.row,

36 37

{ .row = v.row + 1, .col = v.col }, // down { .row = v.row, .col = v.col - 1 }, // left

38

}, // up

.col = v.col + 1 }, // right

};

39 40 41

for (int i = 0; i < MAX_NEIGHBOURS; i++) { Cell w = adj[i];

42

if (validCell(m, w) && !MazeIsWall(m, w) && !visited[w.row][w.col]) {

43

QueueEnqueue(q, w);

44 45

pred[w.row][w.col] = v; }

46

}

47

}

48 49

QueueFree(q);

50 51

freeBoolMatrix(visited);

solveDfs solveBfs

1

#define MAX_NEIGHBOURS 4

2 3

static void fillPath(Maze m, Cell start, Cell exit, Cell **pred);

4 5

static bool validCell(Maze m, Cell c);

6

bool solve(Maze m) {

7

int height = MazeHeight(m);

8 9

int width = MazeWidth(m);

10

bool **visited = createBoolMatrix(height, width);

11

Cell **pred = createCellMatrix(height, width);

12 13

Stack s = StackNew();

14 15

Cell start = MazeGetStart(m);

16 17

StackPush(s, start);

18

bool found = false;

19

while (!found && !StackIsEmpty(s)) {

20 21

Cell v = StackPop(s);

22

if (visited[v.row][v.col]) {

23

continue;

24 25

}

26

visited[v.row][v.col] = true;

27

if (MazeVisit(m, v)) {

28 29

fillPath(m, start, v, pred); found = true;

30

break;

31

}

32 33

Cell adj[MAX_NEIGHBOURS] = {

34

{ .row = v.row - 1, .col = v.col

35

{ .row = v.row,

36 37

{ .row = v.row + 1, .col = v.col }, // down { .row = v.row, .col = v.col - 1 }, // left

}, // up

.col = v.col + 1 }, // right

};

38 39

for (int i = 0; i < MAX_NEIGHBOURS; i++) { Cell w = adj[i];

40 41

if (validCell(m, w) && !MazeIsWall(m, w) && !visited[w.row][w.col]) {

42 43

StackPush(s, w);

44 45

pred[w.row][w.col] = v; } }

46 47

}

48 49

StackFree(s);

50 51

freeBoolMatrix(visited);

============ solveBfs ============ - Worst case time complexity: O(n) - Explanation: Each cell has at most four neighbours, so when we visit a cell, we add queue. Since we visit each cell at most once, at most 4n cells will be added to the qu have at most 4n iterations. All operations in the loop, including the queue operations time, so the time complexity is O(n). ============ solveDfs ============ - Worst case time complexity: O(n) - Explanation: Each cell has at most four neighbours, so when we visit a cell, we add stack. Since we visit each cell at most once, at most 4n cells will be added to the st have at most 4n iterations. All operations in the loop, including the stack operations time, so the time complexity is O(n)....