Take me 4 hours... Thanks for my insistence...


  • 0
    F

    My awkward BFS solution... Really struggling and want to abandon several times...Thanks for my insistence...
    Write it without looking others solution. Don't know whether it's worth or not...
    At first, I just want to solve this problem. But after 3 or 4 hours, I just want to know why my code is wrong and I must need to find the wrong place...
    So happy I solve it. And found all the wrong places of my previous wrong solutions.
    The solution is not beautiful, I just want to post my inner thoughts...

    class Solution {
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{ball[0], ball[1]});
            int m = maze.length, n = maze[0].length;
            int[][] dir = new int[][]{{1, -1, 0, 0}, {0, 0, 1, -1}};
            String[] pa = new String[]{"d", "u", "r", "l"};
            int[][] dp = new int[m][n];
            String[][] dpPath = new String[m][n];
            for (int[] d: dp) {
                Arrays.fill(d, Integer.MAX_VALUE);
            }
            for (String[] d: dpPath) {
                Arrays.fill(d, "z");
            }
            dp[ball[0]][ball[1]] = 0;
            dpPath[ball[0]][ball[1]] = "";
            String res = "z";
            while (!queue.isEmpty()) {
                int[] cur = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int row = cur[0];
                    int col = cur[1];
                    String path = dpPath[row][col];
                    int dist = dp[row][col];
                    path += pa[i];
                    while (row >= 0 && row < m && col >= 0 && col < n && maze[row][col] != 1) {
                        if (row == hole[0] && col == hole[1]) {
                            break;
                        }
                        row += dir[0][i];
                        col += dir[1][i];
                        dist++;
                    }
                    if (row == hole[0] && col == hole[1]) {
                            if (dist <= dp[hole[0]][hole[1]]) {
                                if (dist < dp[hole[0]][hole[1]]) {
                                    dp[hole[0]][hole[1]] = dist;
                                    res = path;
                                }
                                else if (path.compareTo(res) < 0) {
                                    res = path;
                                }
                            }
                            continue;
                    }
                    row -= dir[0][i];
                    col -= dir[1][i];
                    dist--;
                    if (row == cur[0] && col == cur[1]) {
                        continue;
                    }
                    if (dist <= dp[row][col]) { 
                        if (dist < dp[row][col]) {
                            dp[row][col] = dist;
                            dpPath[row][col] = path;
                        } else if (path.compareTo(dpPath[row][col]) < 0) {
                            dpPath[row][col] = path;
                        }
                        queue.offer(new int[]{row, col});
                    }
                }
            }
            return res.equals("z")? "impossible": res;
        }
    }
    

Log in to reply
 

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