Rook Leetcode шешіміне арналған суреттер


Күрделілік дәрежесі оңай
Жиі кіреді шаршы
Array

Проблемалық мәлімдеме

Бұл есепте бізге а-ны білдіретін 2-өлшемді матрица берілген шахмат тақтасы а бар ақ сарғыш және басқа бөліктер. 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 шешіміне арналған суреттер

жақындау

Мәселені шешу тәсілі алдымен 2-D шахмат тақтасындағы орнын табу массив содан кейін біз жоғары, сол, оң және төменгі бағыттарда қара ломбарды таба аламыз ба, жоқ па, соны қайтадан таба аламыз ('p'). Біз кез-келген бағытта бірдей түсті епископқа жетеміз немесе соқтығысамыз, сол бағытта әрі қарай тексеруді тоқтатамыз.

Алгоритм

  1. 'R' таңбасын табу және оның жолдары мен баған нөмірін сақтау үшін бүкіл матрицаны айналдырыңыз r, c тиісінше.
  2. Бастамаңыз ҰБТ ұстауға болатын ломбарлардың санын сақтау үшін
  3. Жоғарғы бағытта тексеріңіз, диапазон: мен ∈ (0, r - 1):
      • if тақта [i] [c] == 'p':
        • өсім ҰБТ, cnt ++
        • Үзіліс
      • if тақта [i] [c] == 'B':
        • Үзіліс
  4. Сол, оң және төменгі бағыттар үшін де солай жасаңыз
  5. қайтару ҰБТ

Rook Leetcode шешіміне арналған қол жетімді суреттерді енгізу

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 шешіміне арналған қол жетімді түсірілімдердің күрделілігін талдау

Уақыттың күрделілігі

O (1), өйткені біз үнемі бірнеше рет қайталаймыз.

Ғарыштың күрделілігі

O (1), өйткені біз кіріске қарамастан тұрақты жад кеңістігін ғана қолданамыз.