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;
        }
    }
    

Log in to reply
 

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