BFS solution using a queue


  • 0
    J

    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<>();
            Queue<int[]> queue = new LinkedList<>();
            
            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";
        }
    

  • 0
    V

    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>


Log in to reply
 

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