Can someone help me to point out why my code is wrong?


  • 0
    F

    Hi, I'm using a naive BFS based on "The Maze". I try to store a triple-element array into the queue, with the distance so far as the third element. My solution will go through every possible case and update the result once the ball reach the destination. I don't know why my solution is wrong because it passed most of the test case and failed on a very large test case with a "Wrong answer" not a "Runtime error". Please point out any ridiculous part of my code. Thanks!

    class Solution {
        public int shortestDistance(int[][] maze, int[] start, int[] destination) {
            int res = Integer.MAX_VALUE;
            int m = maze.length;
            int n = maze[0].length;
            boolean[][] visited = new boolean[m][n];
            visited[start[0]][start[1]] = true;
            Queue<int[]> points = new LinkedList<>();
            // The third element is the distance so far
            int[] begin = {start[0], start[1], 0};
            points.offer(begin);
            while (!points.isEmpty()) {
                int[] cur = points.poll();
                int x = cur[0];
                int y = cur[1];
                int d = cur[2];
                // Up direction until reach a board
                if (x - 1 >= 0 && maze[x - 1][y] == 0) {
                    int dis = 1;
                    while (x - dis >= 0 && maze[x - dis][y] == 0) {
                        dis++;
                    }
                    dis--;
                    // If current stop point is the destination, we try to update the result
                    if (x - dis == destination[0] && y == destination[1]) {
                        res = Math.min(res, d + dis);
                    } else if (!visited[x - dis][y]) {  //Otherwise, if current stop point hasn't been visited before, we put it into queue
                        visited[x - dis][y] = true;
                        int[] next = {x - dis, y, d + dis};
                        points.offer(next);
                    }
                }
                // Down direction
                if (x + 1 < maze.length && maze[x + 1][y] == 0) {
                    int dis = 1;
                    while (x + dis < maze.length && maze[x + dis][y] == 0) {
                        dis++;
                    }
                    dis--;
                    if (x + dis == destination[0] && y == destination[1]) {
                        res = Math.min(res, d + dis);
                    } else if (!visited[x + dis][y]) {
                        visited[x + dis][y] = true;
                        int[] next = {x + dis, y, d + dis};
                        points.offer(next);
                    }
                }
                // Left direction
                if (y - 1 >= 0 && maze[x][y - 1] == 0) {
                    int dis = 1;
                    while (y - dis >= 0 && maze[x][y - dis] == 0) {
                        dis++;
                    }
                    dis--;
                    if (x == destination[0] && y - dis == destination[1]) {
                        res = Math.min(res, d + dis);
                    } else if (!visited[x][y - dis]) {
                        visited[x][y - dis] = true;
                        int[] next = {x, y - dis, d + dis};
                        points.offer(next);
                    }
                }
                // Right direction
                if (y + 1 < maze[0].length && maze[x][y + 1] == 0) {
                    int dis = 1;
                    while (y + dis < maze[0].length && maze[x][y + dis] == 0) {
                        dis++;
                    }
                    dis--;
                    if (x == destination[0] && y + dis == destination[1]) {
                        res = Math.min(res, d + dis);
                    } else if (!visited[x][y + dis]) {
                        visited[x][y + dis] = true;
                        int[] next = {x, y + dis, d + dis};
                        points.offer(next);
                    }
                }
            }
            return res == Integer.MAX_VALUE ? -1 : res;
        }
    }
    

  • 0
    J

    @FelixGEEK
    I wonder which test case you got wrong? My code using BFS also seems to encounter a problem like yours. I also adapted my code from the Maze I and tried to traverse the whole graph and update the distance of every point to start point whenever a shorter path is found. Then on some test case I got distance 204 whereas the answer is 192. Don't really understand what was the problem. Have you solved it? Are we facing similar problems?


Log in to reply
 

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