diff options
| author | Andinus <andinus@nand.sh> | 2021-11-16 20:47:02 +0530 |
|---|---|---|
| committer | Andinus <andinus@nand.sh> | 2021-11-16 20:47:28 +0530 |
| commit | 93db302eed3130c3f54676d7c4e21d091285f6c2 (patch) | |
| tree | abec5aa00718cccd46654389b73c59fc45baf5d7 /algorithms/java | |
| parent | 14a411f3eea3b71831fc914eae0fb57f145c9365 (diff) | |
| download | fornax-93db302eed3130c3f54676d7c4e21d091285f6c2.tar.gz | |
java/BFS: Prettify code
Diffstat (limited to 'algorithms/java')
| -rw-r--r-- | algorithms/java/BFS.java | 95 | ||||
| -rw-r--r-- | algorithms/java/BFS.txt | 91 |
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);
- }
-}
-
-
|