about summary refs log tree commit diff stats
path: root/algorithms
diff options
context:
space:
mode:
authorAndinus <andinus@nand.sh>2021-11-03 17:13:15 +0530
committerAndinus <andinus@nand.sh>2021-11-03 17:13:15 +0530
commit5a1e12748274ffc87631124e6ae0d1a0a9f6c2e9 (patch)
tree8daf59d91a4d81002fa85f2f0f9d32100b1b7af9 /algorithms
parentdbb7b95b35a2be5af0e2068129cd8af2be827503 (diff)
downloadfornax-5a1e12748274ffc87631124e6ae0d1a0a9f6c2e9.tar.gz
java/DFS: Output in Fornax format
Diffstat (limited to 'algorithms')
-rw-r--r--algorithms/java/DFS.java91
1 files changed, 47 insertions, 44 deletions
diff --git a/algorithms/java/DFS.java b/algorithms/java/DFS.java
index 671bfa8..61b2027 100644
--- a/algorithms/java/DFS.java
+++ b/algorithms/java/DFS.java
@@ -1,50 +1,46 @@
-public class CG_pathfinder {
-    static int paths = 0;
-
-    private static final int[][] dir = new int[][]{
-        {0, 1}, //right
-        {1, 0}, //down
-        {0, -1}, //left
-        {-1, 0} //up
+public class DFS {
+    private static final int[][] directions = new int[][]{
+        {+0, +1}, // Right.
+        {+1, +0}, // Down.
+        {+0, -1}, // Left.
+        {-1, +0}, // Up.
     };
 
     static void traverse(int x, int y, char[][] maze, boolean[][] visited) {
         int curx;
         int cury;
-        for (int i = 0; i < 4; i++) {
-            // Print the maze at every iteration.
-            for(int j = 0; j < maze.length; j++)
-                for(int k = 0; k < maze[j].length; k++)
-                    if (visited[j][k])
-                        System.out.print("x");
-                    else
-                        System.out.print(maze[j][k]);
-            System.out.print(" ");
 
-            curx = x;
-            cury = y;
-
-            curx += dir[i][0];
-            cury += dir[i][1];
+        for (int i = 0; i < 4; i++) {
+            curx = x + directions[i][0];
+            cury = y + directions[i][1];
 
+            // Out of bounds check.
             if (curx < 0 || cury < 0
                 || curx > maze.length - 1 || cury > maze.length - 1)
-                continue; //optional?       //for square mazes
+                continue;
 
-            if (maze[curx][cury] == '$') {
-                paths++;
+            // Marker cells.
+            if (maze[curx][cury] == '$')
                 System.out.print("|");
-                // Print the maze at every iteration.
-                for(int j = 0; j < maze.length; j++)
-                    for(int k = 0; k < maze[j].length; k++)
-                        if (visited[j][k])
-                            System.out.print("x");
-                        else
-                            System.out.print(maze[j][k]);
-                System.out.print(" ");
-            } else if (maze[curx][cury] == 'x' || visited[curx][cury])
+            else if (maze[curx][cury] == '#')
+                System.out.print("!");
+
+            // Print the maze on every iteration.
+            for(int j = 0; j < maze.length; j++)
+                for(int k = 0; k < maze[j].length; k++)
+                    if (j == curx && k == cury)
+                        System.out.print("@");
+                    else
+                        System.out.print(visited[j][k] ? "-" : maze[j][k]);
+            System.out.println();
+
+            // Found a solution, exiting.
+            if (maze[curx][cury] == '$')
+                System.exit(0);
+
+            if (visited[curx][cury]) {
                 continue;
-            else if (maze[curx][cury] == '_') {
+            } else if (maze[curx][cury] == '.') {
                 visited[curx][cury] = true;
                 traverse(curx, cury, maze, visited);
                 visited[curx][cury] = false;
@@ -54,20 +50,27 @@ public class CG_pathfinder {
 
     public static void main(String[] args) {
         char[][] maze = {
-            {'*', '#', '_'},
-            {'_', '_', '_'},
-            {'_', '_', '$'}
+            {'.', '#', '.'},
+            {'.', '.', '.'},
+            {'.', '.', '$'}
         };
 
-        int[] start = {0, 0};
         boolean[][] visited = new boolean[maze.length][maze[0].length];
-        for (int i = 0; i< maze.length; i++)
-            for (int j = 0; j<maze.length; j++)
+
+        for (int i = 0; i < maze.length; i++)
+            for (int j = 0; j < maze[i].length; j++)
                 visited[i][j] = false;
 
-        System.out.println(String.format("%d:%d", maze.length, maze[0].length));
-        visited[0][0] = true;
-        traverse(start[0], start[1], maze, visited);
+        System.out.println(String.format("rows:%d cols:%d", maze.length, maze[0].length));
+
+        // Print the maze.
+        for(int j = 0; j < maze.length; j++)
+            for(int k = 0; k < maze[j].length; k++)
+                    System.out.print(maze[j][k]);
         System.out.println();
+
+        // Start at 0,0.
+        visited[0][0] = true;
+        traverse(0, 0, maze, visited);
     }
 }