Minesweeper LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg Kruiz avtomatlaşdırılması DocuSign Facebook google microsoft Pinterest kvadrat Über Zillow
LiveRamp ToptalBaxılıb 76

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

Minesweeper LeetCode Solution – Gəlin mina tarama gəmisi oyununu oynayaq (Vikipediyaonline oyun)!

Sizə verilir m x n simvol matrisi board oyun lövhəsini təmsil edir, burada:

  • 'M' aşkar edilməmiş bir minanı təmsil edir,
  • 'E' açılmamış boş kvadratı təmsil edir,
  • 'B' bitişik minaları olmayan aşkar edilmiş boş kvadratı təmsil edir (yəni, yuxarıda, aşağıda, solda, sağda və bütün 4 diaqonal),
  • rəqəm ('1' üçün '8') aşkar edilən bu kvadrata nə qədər minanın bitişik olduğunu göstərir və
  • 'X' aşkar edilmiş minanı təmsil edir.

Sizə tam ədəd massivi də verilir click hara click = [clickr, clickc] bütün açılmamış kvadratlar arasında növbəti klik mövqeyini təmsil edir ('M' or 'E').

Qayıtmaq aşağıdakı qaydalara uyğun olaraq bu mövqeyi açıqladıqdan sonra şura:

  1. Əgər mina 'M' aşkar edilir, sonra oyun başa çatır. Siz onu dəyişdirməlisiniz 'X'.
  2. Boş kvadrat varsa 'E' heç bir bitişik mina aşkar edilmədikdə, onu aşkar edilmiş boşluğa dəyişdirin 'B' və onun bütün bitişik açılmamış kvadratları rekursiv şəkildə aşkar edilməlidir.
  3. Boş kvadrat varsa 'E' ən azı bir qonşu mina aşkar edildikdə, onu rəqəmə dəyişdirin ('1' üçün '8') bitişik minaların sayını təmsil edir.
  4. Heç bir kvadrat aşkarlanmadıqda lövhəni geri qaytarın.

misal

Test işi 1:

Input:

lövhə = [[“E”,”E”,”E”,”E”,”E”],[“E”,”E”,”M”,”E”,”E”],[“E” ”,”E”,”E”,”E”,”E”],[“E”,”E”,”E”,”E”,”E”]]

klik = [3,0]

Çıxış:

[[“B”,”1″,”E”,”1″,”B”],[“B”,”1″,”X”,”1″,”B”],[“B”,”1″,”1″,”1″,”B”],[“B”,”B”,”B”,”B”,”B”]]

Minesweeper LeetCode HəlliPin

Yanaşma:

Bu tipik bir haldır Search problem, ya istifadə etməklə DFS or BFS. Axtarış qaydaları:

  1. Əgər minaya klik etsəniz ('M'), kimi qeyd edinX', daha da dayan axtarış.
  2. Boş xanaya klikləsəniz ('E'), ətrafdakı minaların sayından asılıdır:
    2.1 Ətrafdakı mina(lar) var, onu ətrafdakı mina(lar)ın sayı ilə qeyd edin və sonrakı axtarışları dayandırın.
    2.2 Ətrafda mina yoxdur, onu ' olaraq qeyd edinB', onun axtarışına davam edin 8 qonşular.

fikir sualda müəyyən edilmiş qaydalara riayət etməkdir.

  1. mənimkini kliklədiyiniz zaman ('M')—-> onu 'X' olaraq dəyişin
  2. 'E' düyməsini kliklədiyiniz zaman -> oradan dfs axtarışı edin
    a. bitişik minalar üçün hesablayın.
    əgər mina yoxdursa, onları ziyarət edib "B" edə bilərsiniz.
    əks halda minalar varsa, siz onlara baş çəkə bilməzsiniz və bununla da dfs axtarışını dayandırırsınız.(minaların sayını bura təyin edin və geri qayıdın)

Minesweeper üçün kod

C ++ Proqramı

class Solution {
int rows,cols;
    int X[8] = {0,-1,-1,-1,0,1,1,1};
    int Y[8] = {1,1,0,-1,-1,-1,0,1};
    int countMines(vector<vector<char>>& board,int x,int y){
        int count = 0;
        for(int i=0;i<8;i++){
            int dx = x + X[i], dy = y + Y[i];
            if(dx>=0 && dy>=0 && dx<rows && dy<cols && board[dx][dy]=='M')
                count++;
        }
        return count;
    }
    void dfs(vector<vector<char>>& board,int x, int y){
        
        int mines = countMines(board,x,y);
        if(mines == 0)
            board[x][y] = 'B';
        else{
            board[x][y] = char(mines+'0');
            return;
        }
        for(int i=0;i<8;i++){
            int dx = x + X[i], dy = y + Y[i];
            if(dx>=0 && dy>=0 && dx<rows && dy<cols && board[dx][dy]=='E')
                dfs(board,dx,dy);
        }
    }
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        if(board.size()==0 || board[0].size()==0)
            return board;
        rows = board.size(); cols = board[0].size();
        int x = click[0], y = click[1];
        if(board[x][y] == 'M')
            board[x][y] = 'X';
        else if(board[x][y] == 'E')
            dfs(board,x,y);
        return board;
    }
};

Java Proqramı

class Solution {
   public char[][] updateBoard(char[][] board, int[] click) {
        int m = board.length, n = board[0].length;
        int row = click[0], col = click[1];
        
        if (board[row][col] == 'M') { // Mine
            board[row][col] = 'X';
        }
        else { // Empty
            // Get number of mines first.
            int count = 0;
            for (int i = -1; i < 2; i++) {
                for (int j = -1; j < 2; j++) {
                    if (i == 0 && j == 0) continue;
                    int r = row + i, c = col + j;
                    if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
                    if (board[r][c] == 'M' || board[r][c] == 'X') count++;
                }
            }
            
            if (count > 0) { // If it is not a 'B', stop further DFS.
                board[row][col] = (char)(count + '0');
            }
            else { // Continue DFS to adjacent cells.
                board[row][col] = 'B';
                for (int i = -1; i < 2; i++) {
                    for (int j = -1; j < 2; j++) {
                        if (i == 0 && j == 0) continue;
                        int r = row + i, c = col + j;
                        if (r < 0 || r >= m || c < 0 || c < 0 || c >= n) continue;
                        if (board[r][c] == 'E') updateBoard(board, new int[] {r, c});
                    }
                }
            }
        }
        
        return board;
    }
}

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

Zamanın mürəkkəbliyi: O(8 * M * N) = O (M * N).

Kosmik Mürəkkəblik: O(M + N) –> Son səviyyə 2M+2N hüceyrələrini ehtiva edir. Beləliklə, * maksimum 2M+2N-ə qədər böyüyə bilər.

Crack Sistemi Dizayn Müsahibələri
Translate »