资讯专栏INFORMATION COLUMN

The Maze II

luffyZh / 3046人阅读

摘要:题目链接一般这种题,给一个起点,给一个终点,最后要求最短的路径,都是用来解。的图不是很大,也能。

The Maze II

题目链接:https://leetcode.com/contest/...
一般这种题,给一个起点,给一个终点,最后要求最短的路径,都是用bfs来解。

public class Solution {
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        /* minheap: check the path with smaller length first
         * path[x][y]: record path from ball to (x, y)
         * visited[x][y]: length from ball to (x, y)
         */
        
        PriorityQueue heap = new PriorityQueue<>(new Comparator() {
            public int compare(Node a, Node b) {
                return a.len - b.len;
            }
        });
        heap.offer(new Node(ball[0], ball[1], 1));
        
        col = maze[0].length;
        
        // track result
        String result = "";
        int len = Integer.MAX_VALUE;
        
        // length and path so far
        visited = new int[maze.length][maze[0].length];
        visited[ball[0]][ball[1]] = 1;
        path = new String[maze.length][maze[0].length];
        path[ball[0]][ball[1]] = "";
        
        while(!heap.isEmpty()) {
            Node cur = heap.poll();
            visited[cur.x][cur.y] = cur.len;
            // find the hole, update result
            if(cur.x == hole[0] && cur.y == hole[1]) {
                if(len > cur.len || (len == cur.len && result.compareTo(path[cur.x][cur.y]) > 0)) {
                    len = cur.len;
                    result = path[cur.x][cur.y];
                } 
                continue;
            }
            // 4 directions
            for(int i = 0; i < 4; i++) {
                int nx = cur.x, ny = cur.y;
                int depth = cur.len;
                // find the next position (reach before the wall)
                while(nx + dx[i] >= 0 && nx + dx[i] < maze.length && ny + dy[i] >= 0 && ny + dy[i] < maze[0].length) {
                    // find the path so far from ball to [nx, ny]
                    String curPath = path[cur.x][cur.y] + (nx == cur.x && ny == cur.y ? "" : dir[i]);
                    // reach the hole
                    if(nx == hole[0] && ny == hole[1]) break;
                    // meet the wall
                    if(maze[nx + dx[i]][ny + dy[i]] == 1) break;
                    // loop update
                    depth++;
                    nx += dx[i];
                    ny += dy[i];
                }
                // pruning
                if(depth > len) continue;
                String curPath = path[cur.x][cur.y] + (nx == cur.x && ny == cur.y ? "" : dir[i]);
                if(visited[nx][ny] != 0 && visited[nx][ny] < depth) continue;
                if(visited[nx][ny] != 0 && visited[nx][ny] == depth && path[nx][ny].compareTo(curPath) <= 0) continue;
                // add new path
                visited[nx][ny]  = depth;
                path[nx][ny] = curPath;
                heap.offer(new Node(nx, ny, depth));
            }
        }
        return result.length() == 0 ? "impossible" : result;
    }
    
    int[] dx = new int[] {1, 0, 0, -1};
    int[] dy = new int[] {0, -1, 1, 0};
    char[] dir = new char[] {"d", "l", "r", "u"};
    
    int[][] visited;
    String[][] path;
    int col;
    
    class Node {
        int x, y;
        int len;
        Node(int x, int y, int len) {
            this.x = x;
            this.y = y;
            this.len = len;
        }
        @Override
        public int hashCode() {
            return this.x * col + this.y;
        }
        @Override
        public boolean equals(Object a) {
            if(a instaceof Node) {
                Node b = (Node) a;
                return b.x == this.x && b.y == this.y;
            }
            return false;
        }
    }
}

test的图不是很大,dfs也能ac。

public class Solution {
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        /* use global variable: result and len 
         */
        visited = new boolean[maze.length][maze[0].length];
        dfs(maze, ball[0], ball[1], hole, 1, "");
        return result.length() == 0 ? "impossible" : result;
    }
    
    String result = "";
    int len = Integer.MAX_VALUE;
    boolean[][] visited;
    int[] dx = new int[] {1, 0, 0, -1};
    int[] dy = new int[] {0, -1, 1, 0};
    char[] dir = new char[] {"d", "l", "r", "u"};
    // dfs
    private void dfs(int[][] maze, int x, int y, int[] hole, int dep, String path) {
        if(dep > len) return;
        if(x == hole[0] && y == hole[1]) {
            if(len > dep) {
                len = dep;  result = path;
            }
            if(len == dep && path.compareTo(result) < 0) {
                len = dep;  result = path;
            } 
            return;
        }
        
        if(visited[x][y]) return;
        visited[x][y] = true;
        
        // 4 directions
        for(int i = 0; i < 4; i++) {
            int nx = x, ny = y;
            while(nx + dx[i] >= 0 && nx + dx[i] < maze.length && ny + dy[i] >= 0 && ny + dy[i] < maze[0].length) {
                // meet the wall
                if(maze[nx + dx[i]][ny + dy[i]] == 1) break;
                nx += dx[i];  ny += dy[i];
                if(visited[nx][ny]) break;
                if(nx == hole[0] && ny == hole[1]) break;
            }
            if(!visited[nx][ny]) dfs(maze, nx, ny, hole, dep + Math.abs(nx - x) + Math.abs(ny - y), path + dir[i]);
        }
        visited[x][y] = false;
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/66557.html

相关文章

  • 490. The Maze && 505. The Maze II

    摘要:题目链接和上一题不一样的是这道题要求最短的路径,普通的遍历和都是可以做的,但是求最短路径的话还是用。这里相当于每个点有至多条相连,每条的就是到墙之前的长度。 490. The Maze 题目链接:https://leetcode.com/problems... 又是图的遍历问题,就是简单的遍历,所以dfs和bfs都可以做,复杂度也是一样的。这道题要求球不能停下来,即使碰到destina...

    BoYang 评论0 收藏0
  • [LeetCode] 490. The Maze (BFS/DFS)

    Problem There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up, down, left or right, but it wont stop rolling until hitting a wall. When the ball sto...

    smartlion 评论0 收藏0
  • DeepMind 提出分层强化学习新模型 FuN,超越 LSTM

    摘要:实验蒙特祖玛的复仇蒙特祖玛的复仇是上最难的游戏之一。图蒙特祖玛的复仇的学习曲线在第一个房间中学习的子目标的可视化呈现。结论如何创建一个能够学习将其行为分解为有意义的基元,然后重新利用它们以更有效地获取新的行为,这是一个长期存在的研究问题。 论文题目:分层强化学习的 FeUdal 网络(FeUdal Networks for Hierarchical Reinforcement Learnin...

    dailybird 评论0 收藏0
  • canvas实例 --- 制作简易迷宫

    摘要:整个思路十分简单首先我们将迷宫视为一个行列的单元格组合,每一个单元格便可以表示为。用来储存我们已访问过的单元格,则记录我们的访问路径。我们通过将单元格的,,,属性设置为或来标识这个方向是否应该有边框,同时该方向是否可走。 这个系列分为两部分,第一部分为迷宫的生成及操作,第二部分为自动寻路算法。 我们先看效果:点击查看 我们直入正题,先说一说生成迷宫的思路。 整个思路十分简单: 首先...

    孙吉亮 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<