diff options
| -rw-r--r-- | algorithms/c/BFS.c | 156 | ||||
| -rw-r--r-- | algorithms/c/DFS.c | 77 |
2 files changed, 233 insertions, 0 deletions
diff --git a/algorithms/c/BFS.c b/algorithms/c/BFS.c new file mode 100644 index 0000000..f0ab8b0 --- /dev/null +++ b/algorithms/c/BFS.c @@ -0,0 +1,156 @@ +#include <err.h> +#include <stdio.h> +#include <stdlib.h> +#include <stdbool.h> + +#define ROWS 3 +#define COLS 3 + +struct Queue { + size_t front; + size_t rear; + size_t capacity; + int *elems; +}; + +struct Queue *Q_initialize(size_t capacity) { + if (capacity == 0) + errx(1, "Capacity must be > 0"); + + struct Queue *q = calloc(1, sizeof(*q)); + q->capacity = capacity; + q->front = -1; + q->rear = -1; + q->elems = calloc(q->capacity, sizeof(*q->elems)); + return q; +} + +void Q_destroy(struct Queue *q) { + free(q->elems); + free(q); +} + +void Q_insert(struct Queue *q, int elem) { + if (q->rear == q->capacity - 1) + errx(1, "Overflow - Max Capacity"); + + if (q->front == -1UL) + q->front = 0; + + q->elems[++q->rear] = elem; +} + +int Q_delete(struct Queue *q) { + if (q->front == -1UL || q->front > q->rear) + errx(1, "Underflow - Empty Queue"); + + return q->elems[q->front++]; +} + +void +bfs(struct Queue *q_x, struct Queue *q_y, + size_t x, size_t y, char maze[ROWS][COLS], bool visited[ROWS][COLS], + size_t parent_path_x[ROWS][COLS], size_t parent_path_y[ROWS][COLS]) { + int dir[4][4] = { + {+0, +1}, // Right. + {+1, +0}, // Down. + {+0, -1}, // Left. + {-1, +0}, // Up. + }; + + for (int idx = 0; idx < 4; idx++) { + size_t cur_x = x + dir[idx][0]; + size_t cur_y = y + dir[idx][1]; + + // Out of bounds check. + if (cur_x < 0 || cur_y < 0 + || cur_x > ROWS - 1 || cur_y > COLS - 1) + continue; + + // Found a solution, exiting. + if (maze[cur_x][cur_y] == '$') { + parent_path_x[cur_x][cur_y] = x; + parent_path_y[cur_x][cur_y] = y; + + size_t loop_x = cur_x; + size_t loop_y = cur_x; + + bool cur_path[ROWS][COLS] = { false }; + + cur_path[0][0] = true; + while (loop_x != 0 || loop_y != 0) { + cur_path[loop_x][loop_y] = true; + size_t tmp = loop_x; + loop_x = parent_path_x[loop_x][loop_y]; + loop_y = parent_path_y[tmp][loop_y]; + } + + for (size_t j = 0; j < ROWS; j++) { + for (size_t k = 0; k < COLS; k++) { + if (maze[j][k] == '^' || maze[j][k] == '$') + printf("%c", maze[j][k]); + else { + if (j == cur_x && k == cur_y) + printf("@"); + else { + if (cur_path[j][k]) + printf("~"); + else if (visited[j][k]) + printf("-"); + else + printf("%c", maze[j][k]); + } + } + printf(" "); + } + printf("\n"); + } + exit(0); + } + + if (visited[cur_x][cur_y] || maze[cur_x][cur_y] == '#') + continue; + + if (maze[cur_x][cur_y] == '.' || maze[cur_x][cur_y] == '^') { + Q_insert(q_x, cur_x); + Q_insert(q_y, cur_y); + + visited[cur_x][cur_y] = true; + parent_path_x[cur_x][cur_y] = x; + parent_path_y[cur_x][cur_y] = y; + } + } + + Q_delete(q_x); + Q_delete(q_y); + if (q_x->front == -1UL) { + puts("Path not Found"); + exit(0); + } else { + bfs(q_x, q_y, q_x->elems[q_x->front], q_y->elems[q_x->front], + maze, visited, parent_path_x, parent_path_y); + } +} + +int +main() { + size_t capacity = 128; + struct Queue *q_x = Q_initialize(capacity); + struct Queue *q_y = Q_initialize(capacity); + + char maze[ROWS][COLS] = { + { '^', '.', '.' }, + { '.', '#', '.' }, + { '.', '.', '$' }, + }; + + bool visited[ROWS][COLS] = { false }; + size_t parent_path_x[ROWS][COLS] = { 0 }; + size_t parent_path_y[ROWS][COLS] = { 0 }; + + visited[0][0] = true; + bfs(q_x, q_y, 0, 0, maze, visited, parent_path_x, parent_path_y); + + Q_destroy(q_x); + Q_destroy(q_y); +} diff --git a/algorithms/c/DFS.c b/algorithms/c/DFS.c new file mode 100644 index 0000000..69cd29f --- /dev/null +++ b/algorithms/c/DFS.c @@ -0,0 +1,77 @@ +#include <stdio.h> +#include <stdlib.h> +#include <stdbool.h> + +#define ROWS 3 +#define COLS 3 + +void +dfs(size_t x, size_t y, char maze[ROWS][COLS], bool visited[ROWS][COLS], + bool cur_path[ROWS][COLS]) { + int dir[4][4] = { + {+0, +1}, // Right. + {+1, +0}, // Down. + {+0, -1}, // Left. + {-1, +0}, // Up. + }; + + for (int idx = 0; idx < 4; idx++) { + size_t cur_x = x + dir[idx][0]; + size_t cur_y = y + dir[idx][1]; + + // Outn of bounds check. + if (cur_x < 0 || cur_y < 0 + || cur_x > ROWS - 1 || cur_y > COLS - 1) + continue; + + if (visited[cur_x][cur_y]) + continue; + + // Found a solution, exiting. + if (maze[cur_x][cur_y] == '$') { + for (size_t j = 0; j < ROWS; j++) { + for (size_t k = 0; k < COLS; k++) { + if (maze[j][k] == '^' || maze[j][k] == '$') + printf("%c", maze[j][k]); + else { + if (j == cur_x && k == cur_y) + printf("@"); + else { + if (cur_path[j][k]) + printf("~"); + else if (visited[j][k]) + printf("-"); + else + printf("%c", maze[j][k]); + } + } + printf(" "); + } + printf("\n"); + } + exit(0); + } + + if (maze[cur_x][cur_y] == '.' || maze[cur_x][cur_y] == '^') { + visited[cur_x][cur_y] = cur_path[cur_x][cur_y] = true; + dfs(cur_x, cur_y, maze, visited, cur_path); + cur_path[cur_x][cur_y] = false; + } + } +} + +int +main() { + char maze[ROWS][COLS] = { + { '^', '.', '.' }, + { '.', '#', '.' }, + { '.', '.', '$' }, + }; + + bool visited[ROWS][COLS] = { false }; + bool cur_path[ROWS][COLS] = { false }; + + visited[0][0] = true; + cur_path[0][0] = true; + dfs(0, 0, maze, visited, cur_path); +} |