# BFS solution using a queue

• With a matrix(steps[i][j]) for current min steps to point (i,j) and a map for shortest way string.

``````    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {

int n = maze.length, m = maze[0].length;

int[][] steps = new int[n][m];
for (int i=0; i<n; ++i)
Arrays.fill(steps[i],Integer.MAX_VALUE);

Map<String,String> map = new HashMap<>();

steps[ball[0]][ball[1]] = 0;
map.put(ball[0]+","+ball[1],"");
queue.offer(ball);

int[][] d = new int[][]{{1,0},{0,-1},{0,1},{-1,0}};
String[] s = new String[]{"d","l","r","u"};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
String curS = cur[0]+","+cur[1];
for (int i=0; i<4; ++i) {
int x = cur[0];
int y = cur[1];
int xx = x+d[i][0];
int yy = y+d[i][1];
int count = 0;
boolean found = false;
while (xx>=0 && xx<n && yy>=0 && yy<m && maze[xx][yy]==0 && !found) {
x = xx;
y = yy;
xx += d[i][0];
yy += d[i][1];
++count;
if (x==hole[0] && y==hole[1])
found = true;
}
String endS = x+","+y;
if (steps[x][y]<Integer.MAX_VALUE) {
if (count+steps[cur[0]][cur[1]]<steps[x][y]) {
steps[x][y] = count+steps[cur[0]][cur[1]];
map.put(endS,map.get(curS)+s[i]);
if (x!=hole[0] || y!=hole[1])
queue.offer(new int[]{x,y});
} else if (count+steps[cur[0]][cur[1]]==steps[x][y]
&& (map.get(curS)+s[i]).compareTo(map.get(endS))<0) {
map.put(endS, map.get(curS)+s[i]);
if (x!=hole[0] || y!=hole[1])
queue.offer(new int[]{x,y});
}
} else {
steps[x][y] = count+steps[cur[0]][cur[1]];
map.put(endS,map.get(curS)+s[i]);
if (x!=hole[0] || y!=hole[1])
queue.offer(new int[]{x,y});
}
}
}

String holeS = hole[0]+","+hole[1];
return map.containsKey(holeS)?map.get(holeS):"impossible";
}
``````

• Hii
Your solution really helped me to build the intuition and I have modified your solution just a little and executed. But I am unable to figure why my program is failing just one test case. It will be very grateful of you if you can help figure what my mistake is??
``` public class Solution { public String findShortestWay(int[][] ar, int[] st, int[] end) { int r,c,i,j,k,x,y; boolean found; r = ar.length; c = ar[0].length; int[][] visited = new int[r][c]; int[][] dis = new int[r][c]; int[][] dir = {{1,0},{0,-1},{0,1},{-1,0}}; String[] s = {"d","l","r","u"}; Map<String,String> map = new HashMap<String,String>(); Queue<int[]> q = new LinkedList<int[]>(); q.add(st); map.put(st[0]+","+st[1],""); dis[st[0]][st[1]] = 0; visited[st[0]][st[1]] = 1; int[] tem,temp; String tems,temps; int distance; while(!q.isEmpty()) { //System.out.println(map); temp = q.remove(); temps = temp[0]+","+temp[1]; i = temp[0]; j = temp[1]; for(k=0;k<4;k++) { x = i + dir[k][0]; y = j + dir[k][1]; found = false; while(x>=0 && y>=0 && x<r && y<c && ar[x][y]==0) { if(x==end[0] && y==end[1]) { x = x + dir[k][0]; y = y + dir[k][1]; found = true; break; } x = x + dir[k][0]; y = y + dir[k][1]; } x = x - dir[k][0]; y = y - dir[k][1]; tems = x + ","+ y; distance = Math.abs(x-i) + Math.abs(y-j); if(found!=true) { if(visited[x][y]==0) { visited[x][y] = 1; q.add(new int[]{x,y}); } } if(map.get(x+","+y)==null) { map.put(x+","+y,map.get(temps)+s[k]); dis[x][y] = dis[temp[0]][temp[1]] + distance; } else if(dis[x][y]== dis[temp[0]][temp[1]] + distance && map.get(tems).compareTo(map.get(temps)+s[k])>0) { map.put(x+","+y,map.get(temps)+s[k]); dis[x][y] = dis[temp[0]][temp[1]] + distance; } else if(dis[x][y]>dis[temp[0]][temp[1]] + distance) { dis[x][y]=dis[temp[0]][temp[1]] + distance; map.put(x+","+y,map.get(temps)+s[k]); }```

``` } } if(map.get(end[0]+","+end[1])==null) return "impossible"; return map.get(end[0]+","+end[1]); } } </code class> ```

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