Test case 61 -- Help!


  • 0
    A

    For the test case 61,

    [[0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0],[0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0],[0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1],[0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1],[0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0],[1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0],[0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1],[0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0],[1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0],[0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1]]
    [29,18]
    [14,22]

    The expected output is,
    "ururulululululurul"

    while my solution outputs,
    "urululurdrulululul"

    They both takes 43 steps to reach the hole. It looks to me the expected output is not the lowest (in alphabet order) movement string.

    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        int m = maze.length, n = maze[0].length;
        int[][] min_dist = new int[m][n];
        String[][] min_path = new String[m][n];
        min_path[hole[0]][hole[1]] = "";
        boolean[][] visited  = new boolean[m][n];
        
        char[] dirs = {'d', 'l', 'r', 'u'};
        HashMap<Character, int[]> dir_map = new HashMap<Character, int[]> ();
        dir_map.put('d', new int[] {1, 0});
        dir_map.put('l', new int[] {0, -1});
        dir_map.put('r', new int[] {0, 1});
        dir_map.put('u', new int[] {-1, 0});
        
        visited[ball[0]][ball[1]] = true;
        dfs(maze, ball, hole, min_dist, min_path, visited, dirs, dir_map);
        return min_dist[ball[0]][ball[1]] == Integer.MAX_VALUE ? "impossible" : min_path[ball[0]][ball[1]];
    }
    
    
    private int dfs(int[][] maze, int[] ball, int[] hole, int[][] min_dist, String[][] min_path, boolean[][] visited, char[] dirs, HashMap<Character, int[]> dir_map) {
        int i = ball[0], j = ball[1];
        if (min_dist[i][j] != 0) {
            return min_dist[i][j];
        }
        min_dist[i][j] = Integer.MAX_VALUE;
        
        for (char dir_c : dirs) {
            int[] dir = dir_map.get(dir_c);
            int cur_to_next_dist = 0;
            
            int x = ball[0] + dir[0], y = ball[1] + dir[1];
            while (x != - 1 && x != maze.length && y != -1 && y != maze[0].length && maze[x][y] == 0) {
                cur_to_next_dist++;
                if (x == hole[0] && y == hole[1]) {
                    min_dist[i][j] = cur_to_next_dist;
                    min_path[i][j] = String.valueOf(dir_c);
                    return cur_to_next_dist; 
                }
                x += dir[0];
                y += dir[1];
            }
            x -= dir[0];
            y -= dir[1];
            
            if (!visited[x][y]) {
                visited[x][y] = true;
                int next_to_hole_dist = dfs(maze, new int[]{x, y}, hole, min_dist, min_path, visited, dirs, dir_map);
                if (next_to_hole_dist != Integer.MAX_VALUE && cur_to_next_dist + next_to_hole_dist < min_dist[i][j]) {
                     min_dist[i][j] = cur_to_next_dist + next_to_hole_dist;
                     min_path[i][j] = String.valueOf(dir_c) + min_path[x][y];
                }
                visited[x][y] = false;
            }
        }
        return min_dist[i][j];
    }

Log in to reply
 

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