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 | |
| parent | 1ef8b03bad506a5f5872341c9d90cd7c96e3ea26 (diff) | |
| download | fornax-e3a8dffc4d9c32d933c6d0369f3a6128736f25e1.tar.gz | |
BFS code for maze traversal
errors (null) for start object.
| -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); + } +} + + |