റൂക്ക് ലീറ്റ്കോഡ് പരിഹാരത്തിനായി ലഭ്യമായ ക്യാപ്‌ചറുകൾ


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു സമചതുരം
അറേ

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ, a പ്രതിനിധീകരിക്കുന്ന 2-D മാട്രിക്സ് ഞങ്ങൾക്ക് നൽകിയിരിക്കുന്നു ചതുരംഗ പലക ഒരു കൂടെ വെളുത്ത പാറ അതിൽ മറ്റു ചില കഷണങ്ങളും. വൈറ്റിന്റെ റൂക്കിനെ പ്രതീകമാണ് പ്രതിനിധീകരിക്കുന്നത് '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

വിശദീകരണം

റൂക്ക് ലീറ്റ്കോഡ് പരിഹാരത്തിനായി ലഭ്യമായ ക്യാപ്‌ചറുകൾ

സമീപനം

ചെസ്സ്ബോർഡ് 2-ഡിയിലെ റൂക്കിന്റെ സ്ഥാനം ആദ്യം കണ്ടെത്തുക എന്നതാണ് പ്രശ്നത്തിനുള്ള സമീപനം ശ്രേണി അതിനുശേഷം നമുക്ക് ഒരു കറുത്ത പണയം ('p') കണ്ടെത്താൻ കഴിയുമോ എന്ന് കണ്ടെത്താൻ മുകളിൽ, ഇടത്, വലത്, താഴെയുള്ള ദിശകളിൽ വീണ്ടും പരിശോധിക്കാം. ഏതെങ്കിലും ദിശയിൽ ഒരേ നിറമുള്ള ഒരു ബിഷപ്പിനെ ഞങ്ങൾ അവസാനിപ്പിക്കുകയോ അടിക്കുകയോ ചെയ്താൽ, ആ ദിശയിൽ പരിശോധിക്കുന്നത് ഞങ്ങൾ നിർത്തുന്നു.

അൽഗോരിതം

  1. 'R' എന്ന പ്രതീകം കണ്ടെത്തുന്നതിന് മുഴുവൻ മാട്രിക്സിലും സഞ്ചരിച്ച് അതിന്റെ വരിയും നിര നമ്പറും സംരക്ഷിക്കുക r, സി യഥാക്രമം.
  2. ആരംഭിക്കുക കറ്റലോണിയയിലെ പിടിച്ചെടുക്കാവുന്ന പണയങ്ങളുടെ എണ്ണം സംഭരിക്കുന്നതിന്
  3. മുകളിലെ ദിശ പരിശോധിക്കുക, ശ്രേണി: i ∈ (0, r - 1):
      • if ബോർഡ് [i] [സി] == 'പി':
        • ഇൻക്രിമെന്റും കറ്റലോണിയയിലെ, cnt ++
        • ഇടവേള
      • if ബോർഡ് [i] [സി] == 'ബി':
        • ഇടവേള
  4. ഇടത്, വലത്, ചുവടെയുള്ള ദിശകൾക്കായി ഇത് ചെയ്യുക
  5. മടങ്ങുക കറ്റലോണിയയിലെ

റൂക്ക് ലീറ്റ്കോഡ് പരിഹാരത്തിനായി ലഭ്യമായ ക്യാപ്‌ചറുകൾ നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം

#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

റൂക്ക് ലീറ്റ്കോഡ് പരിഹാരത്തിനായി ലഭ്യമായ ക്യാപ്‌ചറുകളുടെ സങ്കീർണ്ണ വിശകലനം

സമയ സങ്കീർണ്ണത

O (1), ഞങ്ങൾ നിരന്തരമായ തവണ ആവർത്തിക്കുമ്പോൾ.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1), ഇൻപുട്ട് പരിഗണിക്കാതെ ഞങ്ങൾ സ്ഥിരമായ മെമ്മറി ഇടം മാത്രമേ ഉപയോഗിക്കുന്നുള്ളൂ.