Snakes və Ladders LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Cisco google microsoft Über
Capitalone Goldmann SachsBaxılıb 33

Problem bəyanat

İlanlar və Nərdivanlar LeetCode Həlli - Sizə verilir n x n tam matris board hüceyrələrin haradan etiketləndiyi 1 üçün n2 bir Boustrofedon üslubu lövhənin aşağı sol hissəsindən başlayaraq (yəni board[n - 1][0]) və hər cərgədə alternativ istiqamətlər.

Meydandan başlayırsınız 1 şuranın. Kvadratdan başlayaraq hər bir hərəkətdə curr, aşağıdakıları edin:

  • Təyinat kvadratını seçin next diapazonda bir etiket ilə [curr + 1, min(curr + 6, n2)].
    • Bu seçim standartın nəticəsini simulyasiya edir 6 tərəfli kalıp rulonu: yəni, lövhənin ölçüsündən asılı olmayaraq həmişə ən çoxu 6 istiqamət var.
  • If next bir ilan və ya nərdivan var, siz gərək o ilanın və ya nərdivanın təyinat yerinə keçin. Əks halda, siz hərəkət edin next.
  • Meydana çatdığınız zaman oyun başa çatır n2.

Sırada bir taxta kvadrat r və sütun c ilan və ya nərdivan varsa board[r][c] != -1. Həmin ilanın və ya nərdivanın təyinatı budur board[r][c]. Kvadratlar 1 və n2 ilan və ya nərdivan yoxdur.

Nəzərə alın ki, hər hərəkətdə ən çox bir dəfə ilan və ya nərdivan götürürsünüz. Əgər təyinat bir ilan və ya nərdivan başqa bir ilanın və ya nərdivanın başlanğıcıdır yox sonrakı ilan və ya nərdivanı izləyin.

  • Məsələn, fərz edək ki, lövhədir [[-1,4],[-1,3]], və ilk hərəkətdə təyinat kvadratınızdır 2. Siz nərdivanla kvadrata doğru gedirsiniz 3, amma et yox üçün sonrakı nərdivanı izləyin 4.

Qayıtmaq kvadrata çatmaq üçün lazım olan ən az hərəkət sayı n2. Meydana çatmaq mümkün deyilsə, geri qayıdın -1.

Snakes və Ladders LeetCode HəlliPin

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4
Explanation: 
In the beginning, you start at square 1 (at row 5, column 0).
You decide to move to square 2 and must take the ladder to square 15.
You then decide to move to square 17 and must take the snake to square 13.
You then decide to move to square 14 and must take the ladder to square 35.
You then decide to move to square 36, ending the game.
This is the lowest possible number of moves to reach the last square, so return 4.

Izahat

Intuisiya:
Hər bir addım üçün aşağıdakıları edirik:

  1. zarları yuvarlayın (və bütün 6 mümkün dəyəri yoxlayın, hər birini ziyarət edilmiş kimi qeyd edin)
  2. nərdivana enib onu götürüb-qoşmadığımızı yoxlayın (onu keçmək imkanı yoxdur, biz onu götürməliyik)
  3. növbəti dəfə harada davam edəcəyinizi xatırlayın (növbəyə yeni mövqe əlavə edin)

İndi isə ssenarilərə nəzər salaq:

  1. Sadəcə 1-nın ən yaxşı olduğu zar ilə 6-ci kvadratdan başlayaraq addımlayın 🙂

Kodu

İlanlar və Nərdivanlar üçün C++ Kodu

typedef pair<int,int> Pi;
class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int rows=board.size(), cols = board[0].size(), target=rows*cols, r, c, p;
        vector<int> visited(rows*cols + 1); // cells on board start from 1

        // queue contains <priority, square> sorted ascending by priority
        // prio = #steps * 1000 + (500 - square);
        // number of steps is critical and adds 1000; 500 is selected as it is higher than the max cell (20*20=400)
        priority_queue<Pi, vector<Pi>, greater<Pi>> q;
        q.push(make_pair(0,1)); // 0 steps to position 1
        visited[1] = true;

        while(q.size())
        {
            auto step_pos = q.top(); q.pop();
            int s = step_pos.first/1000 + 1;
            
            for(int i=1; i<=6; i++)
            {
                auto p = step_pos.second+i;
                if(visited[p]) continue;
                visited[p] = true;
                
                r = rows - (p-1) / cols - 1;
                c = (p-1) % cols;
                if((rows-r-1)%2) c = cols - c - 1; // change direction for odd lines
                int ladder = board[r][c];
                if(ladder>0 && ladder<=target)
                    p = ladder; // no update for steps. allow to come here again with a dice
                    
                if(p == target) return s;
                q.push(make_pair(s*1000+500-p, p));
            }
        }
        return -1;
    }
};

İlanlar və Nərdivanlar üçün Python Kodu

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        def label_to_position(label):
            r, c = divmod(label-1, n)
            if r % 2 == 0:
                return n-1-r, c
            else:
                return n-1-r, n-1-c
            
        seen = set()
        queue = collections.deque()
        queue.append((1, 0))
        while queue:
            label, step = queue.popleft()
            r, c = label_to_position(label)
            if board[r][c] != -1:
                label = board[r][c]
            if label == n*n:
                return step
            for x in range(1, 7):
                new_label = label + x
                if new_label <= n*n and new_label not in seen:
                    seen.add(new_label)
                    queue.append((new_label, step+1))
        return -1

İlanlar və Nərdivanlar üçün Mürəkkəblik Təhlili LeetCode Həlli

Zamanın mürəkkəbliyi

O (n ^ 2)

Kosmik Mürəkkəblik

O (n ^ 2)

Translate »