1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
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);
}
}
|