about summary refs log tree commit diff stats
path: root/algorithms
diff options
context:
space:
mode:
authorAndinus <andinus@nand.sh>2021-11-16 22:43:46 +0530
committerAndinus <andinus@nand.sh>2021-11-16 22:43:46 +0530
commit7858dba48b41417f951031d36e7fbf66da8d14e2 (patch)
tree63d4b0b360181658749cf61224744784250d6938 /algorithms
parentd945c6743848890761af2758e7bcec46514746da (diff)
downloadfornax-7858dba48b41417f951031d36e7fbf66da8d14e2.tar.gz
java/DFS: Update to latest fornax format, fix DFS
Now it prints the starting point and all visited path according to the
format.

Earlier we marked paths as unvisited right after we backtrack out of
it. This is not really necessary for us to get the solution because if
we're not able to find a path through that block then we won't find it
with another way of reaching that block either.

Explanation:
AB
X.

If we can't find a path to destination from AX... then we won't find
it form ABX... either. Earlier we were trying ABX... too. I had this
idea in mind because before this I wrote a word search program that
walked in DFS manner, in that case this was required because ABX...
could form a word that AX... couldn't.

The solution was easy, just had to keep it marked as visited and not
revert it. To keep track of current path we created `path'. This is
marked false right after traversal because it keeps track of current
path.
Diffstat (limited to 'algorithms')
-rw-r--r--algorithms/java/DFS.java66
1 files changed, 48 insertions, 18 deletions
diff --git a/algorithms/java/DFS.java b/algorithms/java/DFS.java
index e0da681..d8fe7d1 100644
--- a/algorithms/java/DFS.java
+++ b/algorithms/java/DFS.java
@@ -10,7 +10,7 @@ public class DFS {
         {-1, +0}, // Up.
     };
 
-    static void traverse(int x, int y, char[][] maze, boolean[][] visited) {
+    static void traverse(int x, int y, char[][] maze, boolean[][] visited, boolean[][] path) {
         // Move in random direction.
         List<Integer> l = Arrays.asList(new Integer[]{0, 1, 2, 3});
         Collections.shuffle(l);
@@ -35,41 +35,70 @@ public class DFS {
 
             // 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]);
+                for(int k = 0; k < maze[j].length; k++) {
+                    if (maze[j][k] == '^' || maze[j][k] == '$')
+                        System.out.print(maze[j][k]);
+                    else {
+                        if (j == curx && k == cury)
+                            System.out.print("@");
+                        else {
+                            if (path[j][k])
+                                System.out.print("~");
+                            else if (visited[j][k])
+                                System.out.print("-");
+                            else
+                                System.out.print(maze[j][k]);
+                        }
+                    }
+                }
             System.out.println();
 
             // Found a solution, exiting.
             if (maze[curx][cury] == '$')
                 System.exit(0);
 
-            if (maze[curx][cury] == '.') {
+            if (maze[curx][cury] == '.' || maze[curx][cury] == '^') {
                 visited[curx][cury] = true;
-                traverse(curx, cury, maze, visited);
-                visited[curx][cury] = false;
+                path[curx][cury] = true;
+                traverse(curx, cury, maze, visited, path);
+                path[curx][cury] = false;
             }
         }
     }
 
     public static void main(String[] args) {
         char[][] maze = {
-            {'.', '#', '.', '#', '.', '.', '#', '.'},
-            {'.', '.', '.', '.', '.', '.', '.', '.'},
-            {'.', '#', '.', '.', '#', '.', '.', '$'},
-            {'.', '.', '.', '#', '.', '#', '.', '.'},
-            {'.', '.', '.', '.', '.', '.', '.', '#'},
-            {'.', '#', '#', '.', '.', '.', '#', '.'},
-            {'.', '.', '.', '.', '.', '.', '.', '.'},
+            { '^', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', },
+            { '.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '.', '.', },
+            { '.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '.', '.', },
+            { '.', '.', '.', '.', '#', '#', '#', '.', '.', '.', '.', '.', '.', },
+            { '.', '.', '#', '#', '.', '#', '.', '.', '.', '.', '.', '.', '.', },
+            { '.', '.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '.', },
+            { '.', '.', '.', '.', '.', '#', '.', '#', '#', '.', '#', '#', '#', },
+            { '.', '.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.', '.', },
+            { '.', '.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '$', '.', },
+            { '.', '.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.', '.', },
+            { '.', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.', '.', },
+            { '.', '.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '.', },
+
+            // {'.', '#', '.', '#', '.', '.', '#', '.'},
+            // {'.', '.', '.', '.', '.', '.', '.', '.'},
+            // {'.', '#', '.', '.', '#', '.', '.', '$'},
+            // {'.', '.', '.', '#', '.', '#', '.', '.'},
+            // {'.', '.', '.', '.', '.', '.', '.', '#'},
+            // {'.', '#', '#', '.', '.', '.', '#', '.'},
+            // {'.', '.', '.', '.', '.', '.', '.', '.'},
         };
 
         boolean[][] visited = new boolean[maze.length][maze[0].length];
+        boolean[][] path = new boolean[maze.length][maze[0].length];
 
         for (int i = 0; i < maze.length; i++)
-            for (int j = 0; j < maze[i].length; j++)
+            for (int j = 0; j < maze[i].length; j++) {
                 visited[i][j] = false;
+                path[i][j] = false;
+            }
+
 
         System.out.println(String.format("rows:%d cols:%d", maze.length, maze[0].length));
 
@@ -81,6 +110,7 @@ public class DFS {
 
         // Start at 0,0.
         visited[0][0] = true;
-        traverse(0, 0, maze, visited);
+        path[0][0] = true;
+        traverse(0, 0, maze, visited, path);
     }
 }