aboutsummaryrefslogtreecommitdiffstats
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);
}
}