रुक लेटकोड समाधानको लागि उपलब्ध क्याप्चरहरू


कठिनाई तह सजिलो
बारम्बार सोधिन्छ स्क्वायर
एरे

समस्या वक्तव्य

यस समस्यामा, हामीलाई २-D म्याट्रिक्स दिइन्छ जुन a लाई प्रतिनिधित्व गर्दछ चेसबोर्ड एउटा सेतो कोल र यसमा केहि अन्य टुक्राहरू। सेतो रूक चरित्र द्वारा प्रतिनिधित्व गर्दछ '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

स्पष्टीकरण

रुक लेटकोड समाधानको लागि उपलब्ध क्याप्चरहरू

दृष्टिकोण

समस्याको लागि दृष्टिकोण पहिलो शसबोर्ड २-डीमा हलुका स्थिति पत्ता लगाउनु हो array र त्यसपछि हामी पुनरावृत्ति माथि, बाँया, दायाँ र तल दिशा निर्देशनहरू जाँच गर्न सक्छौं यदि हामी कालो प्यादा ('p') पाउन सक्छौं भने। यदि मामलामा, हामी अन्त्यमा पुग्छौं वा कुनै दिशामा उही रंगको बिशपलाई प्रहार गर्छौं, हामी त्यो दिशामा कुनै पनि अगाडि जाँच गर्न रोक्दछौं।

अल्गोरिदम

  1. क्यारेक्टर 'R' फेला पार्न सम्पूर्ण म्याट्रिक्सलाई ट्रान्स गर्नुहोस् र यसमा प row्क्ति र स्तम्भ संख्या सुरक्षित गर्नुहोस् r, c क्रमशः।
  2. आरम्भ गर्नुहोस् CNT प्यादहरूको संख्या राख्न कि क्याप्चर गर्न सकिन्छ
  3. शीर्ष दिशामा जाँच गर्नुहोस्, दायरा: i ∈ (०, r - १):
      • if बोर्ड [i] [c] == 'पी':
        • वृद्धि CNT, cnt ++
        • ब्रेक
      • if बोर्ड [i] [c] == 'B':
        • ब्रेक
  4. बाँया, दाँया र तल दिशाहरूको लागि पनि यही गर्नुहोस्
  5. फिर्ती CNT

रूक लेटकोड समाधानको लागि उपलब्ध क्याप्चरको कार्यान्वयन

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

रूक लेटकोड समाधानको लागि उपलब्ध क्याप्चरहरूको जटिलता विश्लेषण

समय जटिलता

O (१), हामी बारम्बार स्थिर संख्याहरूमा पुनरावृत्तिको रूपमा।

ठाउँ जटिलता

O (१), हामी इनपुटको बावजुद मात्र स्थिर मेमोरी स्पेस प्रयोग गर्छौं।