The Maze II

码林棱镜
• 阅读 2400

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<Node> heap = new PriorityQueue<>(new Comparator<Node>() {
            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;
    }
}
点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
3年前
FLV文件格式
1.        FLV文件对齐方式FLV文件以大端对齐方式存放多字节整型。如存放数字无符号16位的数字300(0x012C),那么在FLV文件中存放的顺序是:|0x01|0x2C|。如果是无符号32位数字300(0x0000012C),那么在FLV文件中的存放顺序是:|0x00|0x00|0x00|0x01|0x2C。2.  
Stella981 Stella981
3年前
LeetCode——295. Find Median from Data Stream
一.题目链接:  https://leetcode.com/problems/findmedianfromdatastream(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fleetcode.com%2Fproblems%2Ffindmedianfromdatast
Stella981 Stella981
3年前
SpringBoot整合Redis乱码原因及解决方案
问题描述:springboot使用springdataredis存储数据时乱码rediskey/value出现\\xAC\\xED\\x00\\x05t\\x00\\x05问题分析:查看RedisTemplate类!(https://oscimg.oschina.net/oscnet/0a85565fa
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
3年前
LeetCode 1253. 重构 2 行二进制矩阵
题目链接:https://leetcodecn.com/contest/weeklycontest162/problems/reconstructa2rowbinarymatrix/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fleetcodecn.com%2Fco
Wesley13 Wesley13
3年前
PHP创建多级树型结构
<!lang:php<?php$areaarray(array('id'1,'pid'0,'name''中国'),array('id'5,'pid'0,'name''美国'),array('id'2,'pid'1,'name''吉林'),array('id'4,'pid'2,'n
Easter79 Easter79
3年前
SpringBoot整合Redis乱码原因及解决方案
问题描述:springboot使用springdataredis存储数据时乱码rediskey/value出现\\xAC\\xED\\x00\\x05t\\x00\\x05问题分析:查看RedisTemplate类!(https://oscimg.oschina.net/oscnet/0a85565fa
Stella981 Stella981
3年前
851. Loud and Rich —— weekly contest 87
851\.LoudandRich题目链接:https://leetcode.com/problems/loudandrich/description/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fleetcode.com%2Fpr
Stella981 Stella981
3年前
925. Long Pressed Name
题目链接:https://leetcode.com/problems/longpressedname/description/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fleetcode.com%2Fproblems%2Flongpressedname%2Fdescript
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
美凌格栋栋酱 美凌格栋栋酱
4个月前
Oracle 分组与拼接字符串同时使用
SELECTT.,ROWNUMIDFROM(SELECTT.EMPLID,T.NAME,T.BU,T.REALDEPART,T.FORMATDATE,SUM(T.S0)S0,MAX(UPDATETIME)CREATETIME,LISTAGG(TOCHAR(