රූක් ලීට්කෝඩ් විසඳුම සඳහා ලබා ගත හැකි අල්ලා ගැනීම්


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ වර්ග
අරා

ගැටළු ප්රකාශය

මෙම ගැටළුවේදී, අපට නිරූපණය කරන්නේ 2-D අනුකෘතියකි චෙස් පුවරුව සමග සුදු ගොරෝසු සහ තවත් කෑලි කිහිපයක්. වයිට්ස් රූක් නිරූපණය කරන්නේ චරිතයයි 'ආර්'. වයිට්ගේ බිෂොප්වරුන් නියෝජනය කරන්නේ 'බී' කළුගේ ඉත්තන් ලෙස දැක්වේ '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

පැහැදිලි කිරීම

රූක් ලීට්කෝඩ් විසඳුම සඳහා ලබා ගත හැකි අල්ලා ගැනීම්

ප්රවේශය

ගැටළුව සඳහා ප්රවේශය වන්නේ පළමුව චෙස් පුවරුවේ 2-D හි ගොරෝසු ස්ථානය සොයා ගැනීමයි අරාව ඉන්පසු අපට කළු ඉත්තෙකු ('p') සොයා ගත හැකිදැයි සොයා බැලීමට ඉහළ, වමේ, දකුණ සහ පහළ දිශාවන් නැවත නැවත පරීක්ෂා කළ හැකිය. යම් දිශාවකට අපි එකම වර්ණයෙන් යුත් බිෂොප්වරයෙකුට අවසානය කරා හෝ පහර දුන්නොත්, අපි තවදුරටත් එම දිශාවට පරීක්ෂා කිරීම නතර කරමු.

ඇල්ගොරිතම

  1. 'R' අක්ෂරයක් සොයා ගැනීම සඳහා මුළු න්‍යාසය හරහා ගමන් කර එහි පේළිය සහ තීරු අංකය සුරකින්න r, ඇ පිළිවෙලින්.
  2. ආරම්භ කරන්න cnt අල්ලා ගත හැකි උකස් ගණනක් ගබඩා කිරීමට
  3. ඉහළ දිශාව, පරාසය පරීක්ෂා කරන්න: i ∈ (0, r - 1):
      • if පුවරුව [i] [ඇ] == 'පි':
        • වර්ධක cnt, cnt ++
        • බිඳීම
      • if පුවරුව [i] [ඇ] == 'බී':
        • බිඳීම
  4. වම්, දකුණ සහ පහළ දිශාවන් සඳහා එකම දේ කරන්න
  5. ආපසු cnt

රූක් ලීට්කෝඩ් විසඳුම සඳහා පවතින ග්‍රහණයන් ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

#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

රූක් ලීට්කෝඩ් විසඳුම සඳහා ලබා ගත හැකි ග්‍රහණයන්හි සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (1), අපි නියත වාර ගණනක් පුනරාවර්තනය කරන විට.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), ආදානය නොසලකා අපි නිරන්තර මතක අවකාශයක් පමණක් භාවිතා කරන බැවින්.