diff options
| author | Vam-c <89634382+Vam-c@users.noreply.github.com> | 2021-11-05 11:27:21 +0530 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-11-05 11:27:21 +0530 |
| commit | e3a8dffc4d9c32d933c6d0369f3a6128736f25e1 (patch) | |
| tree | 7d0a51f7dea2baee445e5457b7aac47d2cb0da62 /algorithms | |
| parent | 1ef8b03bad506a5f5872341c9d90cd7c96e3ea26 (diff) | |
| download | fornax-e3a8dffc4d9c32d933c6d0369f3a6128736f25e1.tar.gz | |
BFS code for maze traversal
errors (null) for start object.
Diffstat (limited to 'algorithms')
| -rw-r--r-- | algorithms/java/BFS.txt | 91 |
1 files changed, 91 insertions, 0 deletions
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);
+ }
+}
+
+
|