عکس های موجود برای Rook Leetcode Solution


سطح دشواری ساده
اغلب در مربع
صف

بیان مسأله

در این مسئله ، یک ماتریس 2-D به ما داده می شود که نشان دهنده a است شطرنج با یک صخره سفید و چند قطعه دیگر روی آن. White's Rook توسط این شخصیت نشان داده می شود 'R'. اسقف های وایت توسط "ب" و پیاده های سیاه به عنوان 'پ'. این مسئله تضمین می کند که هیچ مورد دیگری غیر از موارد ذکر شده در بالا وجود ندارد. هدف ما کشف تعداد پیاده های سیاه احتمالی است که می تواند توسط یک سفید حرکت کند (در نظر گرفتن قوانین کلی شطرنج).

مثال

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. در جهت بالا ، دامنه را بررسی کنید: من ∈ (0 ، r - 1):
      • if تخته [من] [ج] == 'p':
        • افزایش CNT, cnt ++
        • شکستن
      • if تخته [من] [ج] == '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

تجزیه و تحلیل پیچیدگی عکس های موجود برای راه حل Leetcode Rook

پیچیدگی زمان

O (1)، همانطور که تعداد دفعات ثابت را تکرار می کنیم.

پیچیدگی فضا

O (1)، همانطور که صرف نظر از ورودی فقط از فضای حافظه ثابت استفاده می کنیم.