Maze III LeetCode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur google microsoftBaxılıb 23

Problem bəyanat

Maze III LeetCode Həlli - Bir top var maze boş yerlərlə (kimi təmsil olunur 0) və divarlar (kimi təmsil olunur 1). Top yuvarlanaraq boş yerlərdən keçə bilər yuxarı, aşağı, sola və ya sağa, lakin divara dəyənə qədər yuvarlanmağı dayandırmayacaq. Top dayandıqda, növbəti istiqaməti seçə bilər. Bu labirintdə bir dəlik də var. Top çuxura yuvarlanırsa, çuxura düşəcək.

Verilmişdir m x n maze, topun mövqeyi ball və çuxurun mövqeyi hole, Harada ball = [ballsıra, ballilə] və hole = [holesıra, holeilə], qayıt bir simli instructions top ilə deşik düşmək üçün əməl etməlidir ki, bütün təlimatlar ən qısa məsafə mümkün. Bir neçə etibarlı təlimat varsa, geri qaytarın leksikoqrafik cəhətdən minimumdur bir. Top çuxura düşə bilmirsə, geri qayıdın "impossible".

Topun çuxura düşməsi üçün bir yol varsa, cavab instructions simvolları ehtiva etməlidir 'u' (yəni, yuxarı), 'd' (yəni, aşağı), 'l' (yəni, sol) və 'r' (yəni sağ).

The məsafə sayıdır boş yerlər topla başlanğıc mövqeyindən (xaric) təyinat yerinə (daxildir) qədər səyahət etdi.

Bunu güman edə bilərsiniz labirentin sərhədləri bütün divarlardır (nümunələrə baxın).

Maze III LeetCode HəlliPin

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"
Explanation: There are two shortest ways for the ball to drop into the hole.
The first way is left -> up -> left, represented by "lul".
The second way is up -> left, represented by 'ul'.
Both ways have shortest distance 6, but the first way is lexicographically smaller because 'l' < 'u'. So the output is "lul".

Izahat

Hər dəfə, əvvəlcə yola istiqamət əlavə edin, sonra isə yol boyu dəliklərin olub olmadığını yoxlayaraq həmin istiqamətlə gedin. Divara dəyərkən, dönməyə çalışın və yeni istiqamətə gedin. Başlanğıc nöqtəsi üçün "getməyin", birbaşa "dönüş" hissəsinə keçin.

Ən qısa məsafədən keçən yolu tapmağı hədəfləyirik. Belə ki, obyektlər BFS növbə PathElements, yəni labirintdəki hüceyrələr olmalıdır.
Yekun cavabın leksikoqrafik cəhətdən ən kiçik olmasını təmin etmək üçün inisializasiya zamanı istiqamətlərin sırasını məhdudlaşdırırıq.
Hər bir hüceyrə üçün 4 orientasiya olduğu üçün ən çoxu 4 dəfə ziyarət edilə bilər. Beləliklə, ziyarət edilən boolean[][][] üçölçülüdür.
Başlanğıc PathElement xana etibarlıdırsa, topun ətrafındakı 4 xanadan hər hansı biri olmalıdır. Beləliklə, əvvəlcə 4 başlanğıc PathElements əlavə edirik.
BFS zamanı biz orijinal oriyentasiyaya əməl etməyə davam edirik. Əgər daha irəli gedə bilmiriksə (yəni, kənar və ya divarla qarşılaşırıq), biz digər 3 istiqamətə yönəlirik. Biz oriyentasiya və yolu tez bir zamanda izləyirik, hər dəfə dəliyə rast gələndə cari yolu qaytarırıq, buna görə də oriyentasiya atributlarını təyin edirik və PathElement sinfinə keçirik.

Kodu

The Maze III üçün C++ kodu

class Solution {
public:
    string roll(vector<vector<int>>& maze, int rowBall, int colBall, const vector<int>& hole, 
    int d_row, int d_col, int steps, const string& path, pair<string, int>& res)
{
    if (steps < res.second) {
        if (d_row != 0 || d_col != 0) { // both are zero for the initial ball position.
            while ((rowBall + d_row) >= 0 && (colBall + d_col) >= 0 && (rowBall + d_row) <  maze.size() 
                && (colBall + d_col) < maze[0].size() && maze[rowBall + d_row][colBall + d_col] != 1) 
            {
                rowBall += d_row;
                colBall += d_col;
                ++steps;
                if (rowBall == hole[0] && colBall == hole[1] && steps < res.second) res = {path, steps};
            }
        }
        if (maze[rowBall][colBall] == 0 || steps + 2 < maze[rowBall][colBall]) {
            maze[rowBall][colBall] = steps + 2; // '1' is for the walls.
            if (d_row == 0) roll(maze, rowBall, colBall, hole, 1, 0, steps, path + "d", res);
            if (d_col == 0) roll(maze, rowBall, colBall, hole, 0, -1, steps, path + "l", res);
            if (d_col == 0) roll(maze, rowBall, colBall, hole, 0, 1, steps, path + "r", res);
            if (d_row == 0) roll(maze, rowBall, colBall, hole, -1, 0, steps, path + "u", res);
        }
    }
    return res.first;
}
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) 
{
    return roll(maze, ball[0], ball[1], hole, 0, 0, 0, "", pair<string, int>() = {"impossible", INT_MAX});
}
};

The Maze III üçün Java Kodu

public class Solution {
    int min; //min distance to hole
    String minS; //min distance's path string
    int[] hole;
    int[][] maze; 
    int[][] map; //shortest distant traveling from ball to this point
    int[][] dirs = {{0,1},{-1,0},{1,0},{0,-1}}; //r, u, d, l
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        this.min = Integer.MAX_VALUE; 
        this.minS = null;
        this.hole = hole; 
        this.maze = maze; 
        this.map = new int[maze.length][maze[0].length];
        for(int i = 0; i<map.length; i++) Arrays.fill(map[i], Integer.MAX_VALUE); 
        
        move(ball[0], ball[1], 0, "", -1);
        return (minS==null) ? "impossible" : minS;
    }
    
    private void move(int r, int c, int cnt, String path, int dir){//dir is a index of dirs 
        if(cnt > min || cnt > map[r][c]) return; //not a shortest route for sure 
        if(dir!=-1){//if not from start point 
            //add path 
            if(dir==0) path+='r';
            else if(dir==1) path+='u';
            else if(dir==2) path+='d';
            else path+='l';
    
            //roll along dir 
            while(r>=0 && r<maze.length && c>=0 && c<maze[0].length && maze[r][c]==0){
                map[r][c] = Math.min(map[r][c], cnt); 
                if(r==hole[0] && c==hole[1]){//check hole
                    if(cnt==min && path.compareTo(minS)<0){
                        minS=path;
                    }else if(cnt<min){
                        min = cnt; 
                        minS = path; 
                    }
                    return; 
                }
                r += dirs[dir][0];
                c += dirs[dir][1];
                cnt++;
            }
            r -= dirs[dir][0];//[r,c] is wall, need to walk back 1 step
            c -= dirs[dir][1];
            cnt--;
        }
        
        //hit wall (or start) -> try to turn
        for(int i = 0; i<dirs.length; i++){
            if(dir == i) continue;//dont keep going
            if(dir == (3-i)) continue;//dont go back
            int newR = r + dirs[i][0];
            int newC = c + dirs[i][1];
            if(newR>=0 && newR<maze.length && newC>=0 && newC<maze[0].length && maze[newR][newC]==0){//can go
                move(r, c, cnt, path, i);
            }
        }
    }
}

The Maze III üçün Python Kodu

class Solution:
    def findShortestWay(self, maze, ball, hole):
        m, n, q, stopped = len(maze), len(maze[0]), [(0, "", ball[0], ball[1])], {(ball[0], ball[1]): [0, ""]}
        while q:
            dist, pattern, x, y = heapq.heappop(q)
            if [x, y] == hole:
                return pattern
            for i, j, p in ((-1, 0, "u"), (1, 0, "d"), (0, -1, "l"), (0, 1, "r")):
                newX, newY, d = x, y, 0
                while 0 <= newX + i < m and 0 <= newY + j < n and maze[newX + i][newY + j] != 1:
                    newX += i
                    newY += j
                    d += 1
                    if [newX, newY] == hole:
                        break
                if (newX, newY) not in stopped or [dist + d, pattern + p] < stopped[(newX, newY)]:
                    stopped[(newX, newY)] = [dist + d, pattern + p]
                    heapq.heappush(q, (dist + d, pattern + p, newX, newY))
        return "impossible"

Maze III LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O(V+E)

Kosmik Mürəkkəblik

O (V)

Translate »