From e3a8dffc4d9c32d933c6d0369f3a6128736f25e1 Mon Sep 17 00:00:00 2001
From: Vam-c <89634382+Vam-c@users.noreply.github.com>
Date: Fri, 5 Nov 2021 11:27:21 +0530
Subject: BFS code for maze traversal

errors (null) for start object.
---
 algorithms/java/BFS.txt | 91 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 91 insertions(+)
 create mode 100644 algorithms/java/BFS.txt

diff --git a/algorithms/java/BFS.txt b/algorithms/java/BFS.txt
new file mode 100644
index 0000000..d8eb925
--- /dev/null
+++ b/algorithms/java/BFS.txt
@@ -0,0 +1,91 @@
+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);
+    }
+}
+
+
-- 
cgit 1.4.1-2-gfad0