clear bfs java solution based on Maze II


  • 0
    C

    '''
    public class Solution {

    class Tuple implements Comparable<Tuple> {
        int x;
        int y;
        int len;
        String path;
        
        public Tuple(int x, int y, int len, String path) {
            this.x = x;
            this.y = y;
            this.len = len;
            this.path = path;
        }
        
        @Override
        public int compareTo(Tuple other) {
            if (this.len == other.len) {
                return this.path.compareTo(other.path);
            }
            return this.len - other.len;
        }
    }
    
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        int row = maze.length;
        int col = maze[0].length;
        int[][] dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        char[] dirs = new char[]{'r', 'l', 'd', 'u'};
        int[][] distance = new int[row][col];
        List<Tuple> result = new LinkedList<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                distance[i][j] = Integer.MAX_VALUE;
            }
        }
        PriorityQueue<Tuple> queue = new PriorityQueue<>();
        queue.offer(new Tuple(ball[0], ball[1], 0, ""));
        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();
            if (tuple.len >= distance[tuple.x][tuple.y]) {
                continue;
            }
            distance[tuple.x][tuple.y] = tuple.len;
            for (int i = 0; i < 4; i++) {
                int x = tuple.x;
                int y = tuple.y;
                int len = tuple.len;
                while (x >= 0 && x < row && y >= 0 && y < col && maze[x][y] == 0) {
                    if (x == hole[0] && y == hole[1]) {
                        Tuple next = new Tuple(x, y, len, tuple.path);
                        next.path += dirs[i];
                        result.add(next);
                    }
                    x += dir[i][0];
                    y += dir[i][1];
                    len++;
                }
                x -= dir[i][0];
                y -= dir[i][1];
                len--;
                Tuple next = new Tuple(x, y, len, tuple.path);
                next.path += dirs[i];
                queue.offer(next);
            }
        }
        Collections.sort(result);
        return result.isEmpty() ? "impossible" : result.get(0).path;
    }
    

    }
    '''


Log in to reply
 

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