aboutsummaryrefslogtreecommitdiffstats
path: root/algorithms/java
diff options
context:
space:
mode:
authorAndinus <andinus@nand.sh>2021-10-16 19:26:26 +0530
committerAndinus <andinus@nand.sh>2021-10-16 19:26:26 +0530
commita05fc53d8aac886e5f6f1d358030b98fcdd884d6 (patch)
tree1f08f3873a57bee30fdd5eee52e13b56a8a042e6 /algorithms/java
parent77a9a42d8b5b65a414c3f1d527bc1d9d04e7e663 (diff)
downloadfornax-a05fc53d8aac886e5f6f1d358030b98fcdd884d6.tar.gz
java/DFS: Move file to algorithms directory, cleanup
Diffstat (limited to 'algorithms/java')
-rw-r--r--algorithms/java/DFS.java71
1 files changed, 71 insertions, 0 deletions
diff --git a/algorithms/java/DFS.java b/algorithms/java/DFS.java
new file mode 100644
index 0000000..5357a7d
--- /dev/null
+++ b/algorithms/java/DFS.java
@@ -0,0 +1,71 @@
+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
+ };
+
+ static void traverse(int x, int y, char[][] maze, boolean[][] visited) {
+ int curx;
+ int cury;
+ for (int i = 0; i < 4; i++) {
+ curx = x;
+ cury = y;
+
+ curx += dir[i][0];
+ cury += dir[i][1];
+
+ if (curx < 0 || cury < 0
+ || curx > maze.length - 1 || cury > maze.length - 1)
+ continue; //optional? //for square mazes
+
+ if (maze[curx][cury] == '$') {
+ System.out.println("Path Found");
+ paths++;
+ for(int k = 0; k < maze.length; k++) {
+ for(int j = 0; j < maze.length; j++)
+ System.out.print(visited[k][j]);
+ System.out.println();
+ }
+ } else if (maze[curx][cury] == 'x' || visited[curx][cury])
+ continue;
+ else if (maze[curx][cury] == '_') {
+ visited[curx][cury] = true;
+ traverse(curx, cury, maze, visited);
+ visited[curx][cury] = false;
+ }
+ }
+ }
+
+ public static void main(String[] args) {
+ char[][] maze = {
+ {'*', '#', 'x'},
+ {'_', '_', '_'},
+ {'_', '_', '$'}
+ };
+ int[] start = {0, 0};
+
+ System.out.println("Solving for the maze: ");
+ boolean[][] visited = new boolean[maze.length][maze.length];
+
+ for (int i = 0; i<maze.length; i++){
+ for (int j = 0; j<maze[i].length; j++)
+ System.out.print(maze[i][j] + " "); // Printing maze
+ System.out.println("");
+ }
+
+ for (int i = 0; i< maze.length; i++)
+ for (int j = 0; j<maze.length; j++)
+ visited[i][j] = false;
+
+ visited[0][0] = true;
+ traverse(start[0], start[1], maze, visited);
+ if (paths == 0)
+ System.out.println("no paths found");
+ else
+ System.out.println(paths);
+ }
+}