Maze LeetCode Həllində Girişdən Ən Yaxın Çıxış

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Facebook ÜberBaxılıb 75

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Maze-də Girişdən Ən Yaxın Çıxış LeetCode Həll – Bizə '.' kimi göstərilən boş xanaları olan mxn matrisi "labirint" (0 indeksli) verilir. və divarlar '+' kimi. Sizə həmçinin labirentin girişi verilir, burada giriş = [giriş_sətiri, giriş_sütun] ilkin olaraq dayandığınız xananın sıra və sütununu bildirir.

Bir addımda bir hüceyrəni hərəkət etdirə bilərik upaşağıZamanvə ya sağ. Biz divarlı hücrəyə girə bilmərik və labirintdən kənara çıxa bilmərik. Bizim məqsədimiz tapmaqdır ən yaxın çıxış girişdən. An çıxış kimi təyin olunur boş hüceyrə bu da sərhəd labirintdən. Giriş saymaz çıxış kimi.

Bizdən geri qayıtmağımızı xahiş edirlər bu addımların sayı girişdən ən yaxın çıxışa qədər ən qısa yolda və ya belə bir yol yoxdursa -1.

Nümunələr və izahatlar

Misal 1:

Maze LeetCode Həllində Girişdən Ən Yaxın ÇıxışPin

Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Output: 1
Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3].
Initially, you are at the entrance cell [1,2].
- You can reach [1,0] by moving 2 steps left.
- You can reach [0,2] by moving 1 step up.
It is impossible to reach [2,3] from the entrance.
Thus, the nearest exit is [0,2], which is 1 step away.

Misal 2:

Maze LeetCode Həllində Girişdən Ən Yaxın ÇıxışPin

Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
Output: 2
Explanation: There is 1 exit in this maze at [1,2].
[1,0] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell [1,0].
- You can reach [1,2] by moving 2 steps right.
Thus, the nearest exit is [1,2], which is 2 steps away.

Misal 3:

Maze LeetCode Həllində Girişdən Ən Yaxın Çıxış

Input: maze = [[".","+"]], entrance = [0,0]
Output: -1
Explanation: There are no exits in this maze.

Yanaşma

Gəlin hesab edək ki, biz labirintdə bir yerdəyik və labirentin ən kənar qatında deyilik. Matrisdən çıxmağın ən sürətli yolu, başlanğıc mövqeyimizdən mümkün olan bütün hüceyrələri gəzib ən qısa çıxışı etməkdir. İlkin vəziyyətimizin labirintdə ən kənar hüceyrədə olduğu bir kənar vəziyyətə diqqət yetirməliyik. Çıxarkən, girişin == çıxış olub olmadığını yoxlamaq lazımdır, əgər varsa, labirintdən çıxa bilmərik, əks halda cavab budur.

Biz ilkin mövqedən bütün mümkün xanaları keçmək üçün BFS-dən istifadə edəcəyik. Növbədə mövcud olan bütün elementləri eyni anda keçin, çünki bu xanalardan hər hansı birinə keçmək bərabər məsafəni alacaq. qaçacağıq a döngə zamanı sz = növbənin ölçüsü olduğu sz vaxtları üçün. Sonra keçə biləcəyimiz bütün mümkün hüceyrələri yoxlayacağıq. Bütün mümkün istiqamətlər başqa dəyişən dirdə müəyyən edilir. Köçürməyə icazə verilərsə, biz həmin hücrəyə keçib onu növbədə saxlayacağıq.

Hərəkətə icazə verilir, əgər:

  1. koordinatları x və y ≥ 0
  2. x < m & y < n
  3. xana[x][y] == '.'

Kodu

Labirentdə Girişdən Yaxın Çıxış üçün C++ kodu

#define iPair pair<int,int>
#define deb(x) cout<<#x<<" = "<<x
class Solution {
    int dir[4][2] = {{0,-1}, {-1,0}, {0,1}, {1,0}};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        int moves=1;
        queue<iPair> q;
        q.push({entrance[0], entrance[1]});
        
        while(!q.empty()) {
            int sz = q.size();
            while(sz--) {
                auto curr=q.front();
                q.pop();
                
                for(auto d: dir) {
                    
                    int x = curr.first + d[0], y = curr.second + d[1];
                    
                    if(x >= 0 && x < m && y >= 0 && y < n && maze[x][y] != '+'){
                        
                        if(x == 0 || x == m-1 || y==0 || y==n-1) {
                            if(!(x==entrance[0] && y == entrance[1]))
                                return moves;
                        }
                        
                        q.push({x, y});
                        maze[x][y] = '+';
                    }
                    
                    
                }
            }
            moves++;
            // deb(moves);
        }

        return -1;
    }
};

Labirentdə Girişdən Yaxın Çıxış üçün Java kodu

class Solution {
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    public int nearestExit(char[][] maze, int[] entrance) {
        int rows = maze.length, cols = maze[0].length;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[rows][cols];
        int[] curr;
        
        int x, y, moves = 0;
        
        q.offer(entrance);
        visited[entrance[0]][entrance[1]] = true;
        
        while (!q.isEmpty()) {
            int sz = q.size();
            moves++;
            
            for (int i=0; i<sz; i++) {
                curr = q.poll();
                
                for (int[] dir: dirs) {
                    x = dir[0]+curr[0];                    
                    y = dir[1]+curr[1];
                    
                    if (x<0||x>=rows||y<0||y>=cols) continue;
                    
                    if (visited[x][y] || maze[x][y] == '+') continue;
                    
          
                    if (x==0||x==rows-1||y==0||y==cols-1) return moves;
                    
                    q.offer(new int[]{x, y});
                    visited[x][y] = true;
                }
            }
        }
        
        return -1;
    }
}

Maze LeetCode Həllində Girişdən Ən Yaxın Çıxış üçün Mürəkkəblik Təhlili

  • Zaman mürəkkəbliyi: O(m*n)
    • Ən pis halda, birinci hüceyrədən sonuncu hüceyrəyə keçmək lazımdır
    • Matrisin ölçüsü mxn-dir, buna görə də ümumi vaxt O(m*n)-dir.
  • Kosmik mürəkkəblik: O(m*n)
    • Ziyarət edilən 2D matris mxn yer tutur
Crack Sistemi Dizayn Müsahibələri
Translate »