aboutsummaryrefslogtreecommitdiffstats
path: root/algorithms/java
diff options
context:
space:
mode:
authorAndinus <andinus@nand.sh>2021-11-16 20:47:02 +0530
committerAndinus <andinus@nand.sh>2021-11-16 20:47:28 +0530
commit93db302eed3130c3f54676d7c4e21d091285f6c2 (patch)
treeabec5aa00718cccd46654389b73c59fc45baf5d7 /algorithms/java
parent14a411f3eea3b71831fc914eae0fb57f145c9365 (diff)
downloadfornax-93db302eed3130c3f54676d7c4e21d091285f6c2.tar.gz
java/BFS: Prettify code
Diffstat (limited to 'algorithms/java')
-rw-r--r--algorithms/java/BFS.java95
-rw-r--r--algorithms/java/BFS.txt91
2 files changed, 95 insertions, 91 deletions
diff --git a/algorithms/java/BFS.java b/algorithms/java/BFS.java
new file mode 100644
index 0000000..477461c
--- /dev/null
+++ b/algorithms/java/BFS.java
@@ -0,0 +1,95 @@
+class Coordinates {
+ // for storing coordinates as object.
+ public int x, y;
+
+ Coordinates(int x,int y) {
+ this.x = x;
+ this.y = y;
+ }
+}
+
+public class BFS {
+ // queue of coordinates.
+ static Coordinates[] queue = new Coordinates[1000];
+ private static int front = -1;
+ private static int rear = -1;
+
+ static void enqueue(Coordinates coord) {
+ if (front == -1 && rear == -1) {
+ front = 0;
+ rear = 0;
+ } else {
+ rear++;
+ }
+ queue[rear] = coord;
+ }
+
+ static void dequeue() {
+ if (front == 0 && rear == 0) {
+ front = -1;
+ rear = -1;
+ } else {
+ front++;
+ }
+ }
+
+ // traversing directions.
+ private static final int[][] dir = new int[][]{
+ {+0, +1}, // right.
+ {+1, +0}, // down.
+ {+0, -1}, // left.
+ {-1, +0}, // up.
+ };
+
+ static void bfs(char[][] maze, Coordinates start, boolean[][] visited) {
+ int curx;
+ int cury;
+ for (int i = 0; i < 4; i++) {
+ curx = start.x;
+ cury = start.y;
+
+ curx += dir[i][0];
+ cury += dir[i][1];
+
+ if (curx < 0 || cury < 0 || curx > maze.length - 1 || cury > maze.length - 1) {
+ // for square... out of maze check.
+ continue;
+ } else if (maze[curx][cury] == '$') {
+ System.out.println("Path found");
+ System.exit(0);
+ } else if (visited[curx][cury] || maze[curx][cury] == '#') {
+ continue;
+ } else if(maze[curx][cury]=='_') {
+ enqueue(new Coordinates(curx, cury));
+ visited[curx][cury] = true;
+ }
+ }
+ dequeue();
+ if (front == -1) {
+ System.out.println("path not found");
+ System.exit(0);
+ } else
+ bfs(maze, queue[front], visited);
+ }
+
+ public static void main(String[] args) {
+ char[][] maze = {
+ {'*', '#', '#'},
+ {'_', '_', '#'},
+ {'_', '#', '$'},
+ };
+
+ Coordinates start = new Coordinates(0,0);
+ boolean[][] visited = new boolean[maze.length][maze.length];
+
+ for (int i = 0; i < maze.length; i++) {
+ for (int j = 0; j < maze.length; j++) {
+ visited[i][j] = false;
+ }
+ }
+
+ visited[0][0] = true;
+ enqueue(start);
+ bfs(maze, start, visited);
+ }
+}
diff --git a/algorithms/java/BFS.txt b/algorithms/java/BFS.txt
deleted file mode 100644
index d8eb925..0000000
--- a/algorithms/java/BFS.txt
+++ /dev/null
@@ -1,91 +0,0 @@
-package com.company;
-class Coordinates{
- public int x,y; //for storing coordinates as object
- Coordinates(int x,int y){
- this.x=x;
- this.y=y;
- }
-}
-public class BFS { //BFS main class
- static Coordinates[] queue=new Coordinates[1000]; //queue of coordinates
- private static int front=-1;
- private static int rear=-1;
-
-
- static void enqueue(Coordinates coord){ //enqueue function
- if(front==-1 && rear==-1){
- front=0;
- rear=0;
- }
- else{
- rear++;
- }
- queue[rear]= coord;
- }
- static void dequeue(){ //dequeue operation
- if(front==0 && rear==0){
- front=-1;
- rear=-1;
- }
- else{
- front++;
- }
- }
-
- private static final int[][] dir=new int[][]{ //traversing directions
- {0,1}, //right
- {1,0}, //down
- {0,-1}, //left
- {-1,0} //up
- };
-
- static void bfs(char[][] maze,Coordinates start,boolean[][] visited){
- int curx;
- int cury;
- for(int i=0;i<4;i++){
- curx=start.x;
- cury=start.y;
- curx+=dir[i][0];
- cury+=dir[i][1];
- if(curx<0 || cury<0 || curx> maze.length-1 || cury>maze.length-1){
- continue; //for square... out of maze check
- }
- else if(maze[curx][cury]=='$'){
- System.out.println("Path found");
- System.exit(0);
- }
- else if(visited[curx][cury] || maze[curx][cury]=='#'){
- continue;
- }
- else if(maze[curx][cury]=='_'){
- enqueue(new Coordinates(curx,cury));
- visited[curx][cury]=true;
- }
- }
- dequeue();
- if(front==-1){
- System.out.println("path not found");
- System.exit(0);
- }
- else
- bfs(maze,queue[front],visited);
- }
- public static void main(String[] args) {
- char[][] maze = {{'*','#','#'},
- {'_','_','#'},
- {'_','#','$'},
- };
- Coordinates start=new Coordinates(0,0);
- boolean[][] visited=new boolean[maze.length][maze.length];
- for(int i=0;i< maze.length;i++){
- for(int j=0;j<maze.length;j++) {
- visited[i][j]=false;
- }
- }
- visited[0][0]=true;
- enqueue(start);
- bfs(maze,start,visited);
- }
-}
-
-