ხელმისაწვდომი გადაღებები Rook Leetcode Solution- ისთვის


Რთული ტური Easy
ხშირად ეკითხებიან Square
Array

პრობლემის განცხადება

ამ პრობლემის დროს, ჩვენ გვეძლევა 2-D მატრიცა, რომელიც წარმოადგენს a ჭადრაკის დაფა ერთად თეთრი როკი და მასზე კიდევ რამდენიმე ნაჭერი. White's Rook წარმოდგენილია პერსონაჟით 'R'. უაითის ეპისკოპოსები წარმოდგენილია "B" და შავი პაიკები წარმოდგენილია როგორც 'p'. პრობლემა იძლევა გარანტიას, რომ აღნიშნულის გარდა სხვა ნაჭერი არ არსებობს. ჩვენი მიზანია გავარკვიოთ შესაძლო შავი ლომბარდების რაოდენობა, რომელთა გადაღებაც შეიძლება თეთრმა როკმა ერთ ნაბიჯში (ზოგადი საჭადრაკო წესების გათვალისწინებით).

მაგალითი

board = [[".",".",".",".",".",".",".","."],
         [".",".",".","p",".",".",".","."],
         [".",".",".","R",".",".",".","p"],
         [".",".",".",".",".",".",".","."],
         [".",".",".",".",".",".",".","."],
         [".",".",".","p",".",".",".","."],
         [".",".",".",".",".",".",".","."],
         [".",".",".",".",".",".",".","."]]
3
board = [[".",".",".",".",".",".",".","."],
         [".","p","p","p","p","p",".","."],
         [".","p","p","B","p","p",".","."],
         [".","p","B","R","B","p",".","."],
         [".","p","p","B","p","p",".","."],
         [".","p","p","p","p","p",".","."],
         [".",".",".",".",".",".",".","."],
         [".",".",".",".",".",".",".","."]]
0

განმარტება

ხელმისაწვდომი გადაღებები Rook Leetcode Solution- ისთვის

მიდგომა

პრობლემისადმი მიდგომაა, პირველ რიგში, მოძებნოთ როკის პოზიცია ჭადრაკის დაფაზე 2-D მასივი და შემდეგ ჩვენ შეგვიძლია განმეორებით შევამოწმოთ ზედა, მარცხენა, მარჯვენა და ქვედა მიმართულებები იმის გასარკვევად, გვხვდება თუ არა შავი ლომბარდი ('p'). იმ შემთხვევაში, თუ ჩვენ მივაღწევთ ბოლომდე ან დავარტყამთ იმავე ფერის ეპისკოპოსს რაიმე მიმართულებით, ჩვენ აღარ ვწყვეტთ ამ მიმართულებით შემოწმებას.

ალგორითმი

  1. გაიარეთ მთელი მატრიცა, რომ იპოვოთ სიმბოლო 'R' და შეინახოთ მისი მწკრივისა და სვეტის ნომერი r, c შესაბამისად.
  2. ინიციალიზაცია cnt პაიკების რაოდენობის შესანახად, რომელთა გადაღებაც შესაძლებელია
  3. შეამოწმეთ ზედა მიმართულებით, დიაპაზონში: i ∈ (0, r - 1):
      • if დაფა [i] [c] == 'p':
        • ზრდა cnt, cnt ++
        • შესვენება
      • if დაფა [i] [c] == 'B':
        • შესვენება
  4. იგივე გააკეთე მარცხენა, მარჯვენა და ქვედა მიმართულებებისთვის
  5. დაბრუნების cnt

Rook Leetcode Solution- ის ხელმისაწვდომი გადაღებების განხორციელება

C ++ პროგრამა

#include <bits/stdc++.h>

using namespace std;

int numRookCaptures(vector<vector<char>>& board)
{
    if(board.empty())
        return 0;
    int n = board.size() , m = board[0].size() , cnt = 0 , r , c;

    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m ; j++)
        {
            if(board[i][j] == 'R')
            {
                r = i;
                c = j;
                break;
            }
        }


    for(int i = r - 1 ; i >= 0 ; i--)
    {
        if(board[i][c] == 'p')
        {
            cnt++;
            break;
        }
        if(board[i][c] == 'B')
            break;
    }
    for(int i = r + 1 ; i < n ; i++)
    {
        if(board[i][c] == 'p')
        {
            cnt++;
            break;
        }
        if(board[i][c] == 'B')
            break;
    }

    for(int j = c - 1 ; j >= 0 ; j--)
    {
        if(board[r][j] == 'p')
        {
            cnt++;
            break;
        }
        if(board[r][j] == 'B')
            break;
    }

    for(int j = c + 1 ; j < m ; j++)
    {
        if(board[r][j] == 'p')
        {
            cnt++;
            break;
        }
        if(board[r][j] == 'B')
            break;
    }
    return cnt;
}

int main() {
    vector <vector <char> > board = {{'.','.','.','.','.','.','.','.'},
                                    {'.','.','.','p','.','.','.','.'},
                                    {'.','.','.','R','.','.','.','p'},
                                    {'.','.','.','.','.','.','.','.'},
                                    {'.','.','.','.','.','.','.','.'},
                                    {'.','.','.','p','.','.','.','.'},
                                    {'.','.','.','.','.','.','.','.'},
                                    {'.','.','.','.','.','.','.','.'}};


    cout << numRookCaptures(board) << endl;
    return 0;
}

ჯავა პროგრამა

class number_of_rook_captures {

    public static void main(String args[]) {
        char[][] board = {{'.','.','.','.','.','.','.','.'},
                         {'.','.','.','p','.','.','.','.'},
                         {'.','.','.','R','.','.','.','p'},
                         {'.','.','.','.','.','.','.','.'},
                         {'.','.','.','.','.','.','.','.'},
                         {'.','.','.','p','.','.','.','.'},
                         {'.','.','.','.','.','.','.','.'},
                         {'.','.','.','.','.','.','.','.'}};

        System.out.println(numRookCaptures(board));
    }

    public static int numRookCaptures(char [][] board) {
        if(board.length == 0)
            return 0;
        int n = board.length , m = board[0].length , cnt = 0 , r = -1 , c = -1;

        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < m ; j++)
            {
                if(board[i][j] == 'R')
                {
                    r = i;
                    c = j;
                    break;
                }
            }


        for(int i = r - 1 ; i >= 0 ; i--)
        {
            if(board[i][c] == 'p')
            {
                cnt++;
                break;
            }
            if(board[i][c] == 'B')
                break;
        }
        for(int i = r + 1 ; i < n ; i++)
        {
            if(board[i][c] == 'p')
            {
                cnt++;
                break;
            }
            if(board[i][c] == 'B')
                break;
        }

        for(int j = c - 1 ; j >= 0 ; j--)
        {
            if(board[r][j] == 'p')
            {
                cnt++;
                break;
            }
            if(board[r][j] == 'B')
                break;
        }

        for(int j = c + 1 ; j < m ; j++)
        {
            if(board[r][j] == 'p')
            {
                cnt++;
                break;
            }
            if(board[r][j] == 'B')
                break;
        }
        return cnt;
    }
}
3

Rook Leetcode Solution- ის შესაძლო გადაღებების სირთულის ანალიზი

დროის სირთულე

O (1), რადგან ჩვენ მუდმივად ვიმეორებთ რამდენჯერმე.

სივრცის სირთულე

O (1), რადგან შეყვანის მიუხედავად ვიყენებთ მხოლოდ მუდმივ მეხსიერების ადგილს.