# Easy-understanding Java bfs solution.

• A standart bfs solution.

``````public class Solution {
class Point {
int x,y;
public Point(int _x, int _y) {x=_x;y=_y;}
}
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int m=maze.length, n=maze[0].length;
if (start[0]==destination[0] && start[1]==destination[1]) return true;
int[][] dir=new int[][] {{-1,0},{0,1},{1,0},{0,-1}};
boolean[][] visited=new boolean[m][n];
visited[start[0]][start[1]]=true;
list.offer(new Point(start[0], start[1]));
while (!list.isEmpty()) {
Point p=list.poll();
int x=p.x, y=p.y;
for (int i=0;i<4;i++) {
int xx=x, yy=y;
while (xx>=0 && xx<m && yy>=0 && yy<n && maze[xx][yy]==0) {
xx+=dir[i][0];
yy+=dir[i][1];
}
xx-=dir[i][0];
yy-=dir[i][1];
if (visited[xx][yy]) continue;
visited[xx][yy]=true;
if (xx==destination[0] && yy==destination[1]) return true;
list.offer(new Point(xx, yy));
}
}
return false;

}
}
``````

• Hi,
May I know why visited update is not inside while loop function when rolling in same direction?

• @mingzhou1987 There may be a `cross`, so we cannot update while rolling.

``````    --->---
|       |
^       v
|       |
^       v
|       |
---<---+--<--- o
v
|
``````

• This post is deleted!

• "Both the ball and the destination exist on an empty space, and they will not be at the same position initially."

``if (start[0]==destination[0] && start[1]==destination[1]) return true;``

• There is no need to have a class Point.
'''
public class Solution {

``````public boolean hasPath(int[][] maze, int[] start, int[] destination) {
if (start[0] == destination[0] && start[1] == destination[1]) return true;
queue.offer(start);
int m = maze.length;
int n = maze[0].length;
boolean[][] visited = new boolean[m][n];
visited[start[0]][start[1]] = true;
int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int k = 0; k < dir.length; k++) {
int x = cur[0];
int y = cur[1];
while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
x += dir[k][0];
y += dir[k][1];
}
x -= dir[k][0];
y -= dir[k][1];
if (visited[x][y]) continue;
visited[x][y] = true;
if (x == destination[0] && y == destination[1]) return true;
queue.offer(new int[] {x, y});
}
}
``````

'''

``````    return false;
}
``````

}

• great solution!

• @ckcz123
xx-=dir[i][0];
yy-=dir[i][1];
Why back one step ?

Thanks

• @mgzaki2406 Because `(xx, yy)` is an invalid point.

• ``````            while (xx>=0 && xx<m && yy>=0 && yy<n && maze[xx][yy]==0) {
xx+=dir[i][0];
yy+=dir[i][1];
}
``````

This is very smart move.

• Similar Approach.

``````public boolean hasPath(int[][] maze, int[] start, int[] destination) {
boolean[][][] map = new boolean [maze.length][maze [0].length][4];
return roll (map, maze, start, destination);
}

private int [] rowdir = { 0, 1,  0, -1 };
private int [] coldir = { 1, 0, -1,  0 };

private boolean roll (boolean[][][] map, int[][] maze, int[] start, int[] destination) {
for (int idx = 0; idx < 4; idx ++) {
if (!map [start [0]][start [1]][idx]) {
map [start [0]][start [1]][idx] = true;
if (maze [start [0]][start [1]] == 1) continue;
int [] next = new int [] { start [0], start [1] };

while (next [0] >= 0 && next [0] < maze.length && next [1] >= 0 && next [1] < maze[0].length && maze [next [0]][next [1]] == 0)  {
next [0] += rowdir [idx]; next [1] += coldir [idx];
}
next [0] -= rowdir [idx]; next [1] -= coldir [idx];

if ((next [0] == destination [0] && next [1] == destination [1]) || (roll (map, maze, next, destination))) return true;
}
}
return false;
}
``````

• I use hashset to mark visited stop position:

``````    public boolean hasPath(int[][] maze, int[] start, int[] destination)
{
if (maze == null || maze.length == 0 || maze[0].length == 0) { return false; }

int row = maze.length;
int col = maze[0].length;

// visited stop cell, convert int[]  coordinate into integer
Set<Integer> stops = new HashSet<>();

que.offer(start);

int[][] dir = {{-1, 0},{1, 0},{0, -1},{0, 1}};
while (!que.isEmpty())
{
int[] pos = que.poll();

for (int i = 0; i < dir.length; i++)
{
int r = pos[0];
int c = pos[1];

// keep going until meet wall
while (r >= 0 && r < row && c >= 0 && c < col && maze[r][c] != 1)
{
r += dir[i][0];
c += dir[i][1];
}

// find stop position
r -= dir[i][0];
c -= dir[i][1];

int stop = r * col + c;
if (!stops.contains(stop))
{
if (r == destination[0] && c == destination[1]) { return true; }

que.offer(new int[]{r, c});
}
}
}
return false;
}
``````

• hey guys, can anyone tell me the time complexity is what/

• @renjiandreamore I think both the time and space complexity are O(mn). Correct me if I am wrong...The worst case the ball will completely traversal the maze.

• @FF_Ti

I don't understand why the time complexity is O(mn).

0 0 0 0
s 0 0 0
0 0 d 0
0 0 0 0

Consider this board and let's track the ball's traversal.
Let's say I am moving ball to right, left, up and down.

``````        int[][] dir=new int[][] {{0,1},{0,-1},{-1,0},{1,0}};

0 0 0 0
s---->b // ball moves right
0 0 d 0
0 0 0 0

then it moves back left

0 0 0 0
s <---b // ball moves back left from right
0 0 d 0
0 0 0 0

As we can see each cell is not visited just once.
Another example ..
0 <-- b // ball moves to left
s 0 0 0
0 0 d 0
0 0 0 0

b --> 0
s 0 0 0
0 0 d 0
0 0 0 0

ball moves to right from (0,0) and it stops when it reaches (0,3).
But row 0 is visited twice when ball travels from (0,3) to (0,0) and from (0,0) to (0,3)
So how is time complexity is O(mn)? Ball keeps traveling the reverse direction twice.``````

• More concise one. You don't have to check visited and if match twice.

``````public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze[0].length;
boolean[][] visited = new boolean[m][n];
queue.offer(start);
while (!queue.isEmpty()) {
int[] cur = queue.poll();
if (cur[0] == destination[0] && cur[1] == destination[1]) {
return true;
}
if (visited[cur[0]][cur[1]])
continue;
visited[cur[0]][cur[1]] = true;
int[][] move = new int[][] {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
for (int[] mo : move) {
int x = cur[0], y = cur[1];
while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
x += mo[0];
y += mo[1];
}
// Back to validate point.
x -= mo[0];
y -= mo[1];
queue.offer(new int[] {x, y});
}
}
return false;
}
``````

• More concise one. You don't have to check visited and if match twice.

``````public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze[0].length;
boolean[][] visited = new boolean[m][n];
queue.offer(start);
while (!queue.isEmpty()) {
int[] cur = queue.poll();
if (cur[0] == destination[0] && cur[1] == destination[1]) {
return true;
}
if (visited[cur[0]][cur[1]])
continue;
visited[cur[0]][cur[1]] = true;
int[][] move = new int[][] {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
for (int[] mo : move) {
int x = cur[0], y = cur[1];
while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
x += mo[0];
y += mo[1];
}
// Back to validate point.
x -= mo[0];
y -= mo[1];