# Easy BFS(21ms)/ DFS(45ms)in Java

• This is the BFS solution:

``````public class Solution {
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
int m = maze.length, n = maze[0].length;
int[][] length = new int[m][n];

String[][] path = new String[m][n];
for(String[] items : path)
Arrays.fill(items, new String());

int[] dx = {1, 0, 0, -1};
int[] dy = {0, -1, 1, 0};
char[] step = {'d', 'l', 'r', 'u'};

q.offer(ball);

while(!q.isEmpty()) {
int[] cur = q.poll();

if(Arrays.equals(cur, hole)) continue;

for(int k = 0; k < 4; k++) {

int i = cur[0], j = cur[1];
int count = 0;
while((i != hole[0] || j != hole[1]) && i + dx[k] >= 0 && i + dx[k] < m &&
j + dy[k] >= 0 && j + dy[k] < n &&
maze[i + dx[k]][j + dy[k]] == 0) {
count++; i += dx[k]; j += dy[k];
}

if((i != ball[0] || j != ball[1]) &&
(length[i][j] == 0 || length[i][j] > length[cur[0]][cur[1]] + count ||
(length[i][j] == length[cur[0]][cur[1]] + count &&
path[i][j].compareTo(path[cur[0]][cur[1]] + step[k]) > 0))) {

path[i][j] = path[cur[0]][cur[1]] + step[k];
length[i][j] = length[cur[0]][cur[1]] + count;

q.offer(new int[] {i, j});
}
}
}

return path[hole[0]][hole[1]].length() == 0 ? "impossible" : path[hole[0]][hole[1]];
}
}
``````

DFS solution which is similar to backtrace solution:

``````public class Solution {
public String res = new String();
public int[][] delta = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
public char[] step = {'d', 'l', 'r', 'u'};

public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
int[][] path = new int[maze.length][maze[0].length];
helper(maze, path, ball, new StringBuffer(), hole, ball);
return res.length() == 0 ? "impossible" : res;
}

public void helper(int[][] maze, int[][] path, int[] s, StringBuffer sb, int[] hole, int[] ball) {
if(Arrays.equals(s, hole)) {
res = sb.toString();
return;
}

for(int k = 0; k < 4; k++) {
int i = s[0], j = s[1],  count = 0;

while((i != hole[0] || j != hole[1]) &&
i + delta[k][0] >= 0 && i + delta[k][0] < maze.length &&
j + delta[k][1] >= 0 && j + delta[k][1] < maze[0].length &&
maze[i + delta[k][0]][j + delta[k][1]] == 0) {
i += delta[k][0]; j += delta[k][1]; count++;
}

if((i != ball[0] || j != ball[1]) &&
(path[i][j] == 0 || path[i][j] > path[s[0]][s[1]] + count)) {
path[i][j] = path[s[0]][s[1]] + count;
sb.append(step[k]);
helper(maze, path, new int[] {i, j}, sb, hole, ball);
sb.deleteCharAt(sb.length() - 1);
}
}
}

}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.