From d5dbfe4ea28085f2172c12743974cd9d37291ea1 Mon Sep 17 00:00:00 2001
From: Andinus <andinus@nand.sh>
Date: Mon, 29 Nov 2021 15:26:11 +0530
Subject: Add BFS, DFS implementation in C

This does not output according to the format yet. And the code is a
direct re-implementation of Java program.
---
 algorithms/c/DFS.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 77 insertions(+)
 create mode 100644 algorithms/c/DFS.c

(limited to 'algorithms/c/DFS.c')

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);
+}
-- 
cgit 1.4.1-2-gfad0