Rook Leetcode Solution- ի մատչելի նկարներ


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են քառակուսի
Դասավորություն

Խնդիրի հայտարարություն

Այս խնդրում մեզ տրվում է 2-D մատրից, որը ներկայացնում է ա շախմատի տախտակ հետ սպիտակ ալիք և դրա վրա մի քանի այլ կտորներ: White's Rook- ը ներկայացված է հերոսով «Ռ», Ուայթի եպիսկոպոսները ներկայացված են «Բ» իսկ սեւ լոմբարդները ներկայացված են որպես «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. initialize 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;
}

Java ծրագիր

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 լուծույթի մատչելի գրավիչների բարդության վերլուծություն

Timeամանակի բարդություն

Ո (1), քանի որ մենք անընդհատ կրկնում ենք մի քանի անգամ:

Տիեզերական բարդություն

Ո (1), քանի որ մենք օգտագործում ենք միայն անընդհատ հիշողության տարածություն ՝ անկախ մուտքից: