एक टिक टीएसी को पैर की अंगुली खेल Leetcode समाधान पर विजेता का पता लगाएं


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना सेब Facebook Zoho
ऐरे

समस्या एक टिक टीएसी को पैर की अंगुली खेल Leetcode समाधान पर विजेता का पता लगाएं, हमें एक टिक टीएसी को पैर की अंगुली खेल के विजेता का पता लगाने के लिए कहता है। समस्या हमें एक प्रदान करती है सरणी या खिलाड़ियों द्वारा किए गए चालों के वेक्टर। हमें चाल और जज के माध्यम से जाने की जरूरत है जो खेल जीतता है। खेल के परिणाम को जीता जा सकता है, आकर्षित किया जा सकता है या लंबित हो सकता है। मामलों में, जब उनमें से कोई भी गेम जीतता है, तो हम ए या बी लौटाते हैं, लेकिन गेम को जज करने से पहले, हमें टिक टीएसी पैर के इस विशिष्ट संस्करण के नियमों के बारे में पता होना चाहिए।

  • खिलाड़ी केवल उन चौकों पर चालें बना सकते हैं जिनका पहले से उपयोग नहीं किया गया है।
  • पहला खिलाड़ी A हमेशा "X" अक्षर रखता है, जबकि दूसरा खिलाड़ी B हमेशा "O" अक्षर रखते हैं।
  • "X" और "O" अक्षर हमेशा खाली वर्गों में रखे जाते हैं। पहले से उपयोग किए गए वर्गों का उपयोग कभी नहीं करना चाहिए।
  • खेल तब समाप्त होता है जब किसी पंक्ति, स्तंभ या विकर्ण को भरने वाले (गैर-खाली) वर्ण के 3 होते हैं।
  • यदि सभी वर्ग गैर-रिक्त हैं, तो खेल भी समाप्त हो जाता है। कुछ मामलों में, दोनों ही जीत नहीं पाते हैं और ड्रा में खत्म हो जाते हैं।
  • खेल खत्म होने पर और कोई चाल नहीं चल सकती। यदि कुछ चालें शेष हैं, तो निर्णय "लंबित" है।
  • प्लेयर "ए" पहली चाल बनाता है और फिर वैकल्पिक बारी दोनों खिलाड़ियों द्वारा उपयोग किया जाता है।

आइए कुछ उदाहरणों पर एक नज़र डालते हैं।

moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
"A"

एक टिक टीएसी को पैर की अंगुली खेल Leetcode समाधान पर विजेता का पता लगाएं

स्पष्टीकरण: जैसा कि चित्र में दिखाया गया है, "X" वाला खिलाड़ी गेम जीतता है। एक खेल हमेशा शुरू होता है, इस प्रकार विजेता "ए" भी होता है।

एक टिक टीएसी को पैर की अंगुली खेल Leetcode समाधान पर विजेता का पता लगाने के लिए दृष्टिकोण

समस्या कुछ चालों के बाद टिक टीएसी पैर की अंगुली के खेल के अंतिम फैसले को खोजने के लिए है। यह एक मानक खेल है, इसलिए हमें प्रक्रिया को अनुकरण करने की आवश्यकता है। हमें उसी क्रम में चरणों को निष्पादित करने की आवश्यकता है जैसा कि इनपुट में दिया गया है। एक तरीका 3 × 3 का ग्रिड बनाना है और फिर उसी प्रक्रिया का अनुकरण करना है। लेकिन ऐसा करने के बजाय, हम दोनों खिलाड़ियों द्वारा सरणियों का उपयोग करके किए गए चालों पर नज़र रखते हैं। हम दोनों खिलाड़ियों के लिए 4 अलग-अलग सरणियों का उपयोग करते हैं, प्रत्येक पंक्ति और स्तंभ के बारे में उनके द्वारा किए गए कदमों के लिए 2। प्रत्येक चाल के लिए, हम इन सरणियों में संग्रहीत मूल्यों को बढ़ाते हैं। एक बार मान 3 के बराबर हो जाते हैं। हम जानते हैं कि 3 चालें क्षैतिज या लंबवत रूप से बनाई जाती हैं।

विकर्णों के लिए, हम बस सरणियों के समान 4 चर का उपयोग करते हैं। जब कोई मान 3. के बराबर हो जाता है तो हम उसी के अनुसार नाम वापस करते हैं। लेकिन अगर हम किसी फैसले पर नहीं पहुंचते हैं जब तक कि सभी कदम नहीं उठाए गए हैं। फिर हम ड्रॉ का एक फैसला लौटाते हैं यदि ग्रिड पर मौजूद सभी वर्गों पर कब्जा कर लिया जाता है और लंबित है।

एक टिक टीएसी को पैर की अंगुली खेल Leetcode समाधान पर विजेता खोजने के लिए कोड

C ++ कोड

#include <bits/stdc++.h>
using namespace std;

string tictactoe(vector<vector<int>>& moves) {
    int aRow[3] = {0}, bRow[3] = {0}, aCol[3] = {0}, bCol[3] = {0};
    int aDiagonal1 = 0, bDiagonal1 = 0, aDiagonal2 = 0, bDiagonal2 = 0;
    int n = moves.size();
    for (int i = 0; i < n; i++) {
        int r = moves[i][0], c = moves[i][1];
        if (i % 2 == 1) {
            if (++bRow[r] == 3 || ++bCol[c] == 3 || (r == c && ++bDiagonal1 == 3) || (r + c == 2 && ++bDiagonal2 == 3)) return "B";
        }else {
            if (++aRow[r] == 3 || ++aCol[c] == 3 || (r == c && ++aDiagonal1 == 3) || (r + c == 2 && ++aDiagonal2 == 3)) return "A";
        }
    }
    return n == 9 ? "Draw" : "Pending";
}

int main(){
    vector<vector<int>> moves = {{0,0}, {2,0}, {1,1}, {2,1}, {2,2}};
    cout<<tictactoe(moves);
}
A

जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static String tictactoe(int[][] moves) {
        int[] aRow = new int[3];
        int[] aCol = new int[3];
        int[] bRow = new int[3];
        int[] bCol = new int[3];
        int aDiagonal1 = 0, bDiagonal1 = 0, aDiagonal2 = 0, bDiagonal2 = 0;
        int n = moves.length;
        for (int i = 0; i < n; i++) {
            int r = moves[i][0], c = moves[i][1];
            if (i % 2 == 1) {
                if (++bRow[r] == 3 || ++bCol[c] == 3 || (r == c && ++bDiagonal1 == 3) || (r + c == 2 && ++bDiagonal2 == 3)) return "B";
            }else {
                if (++aRow[r] == 3 || ++aCol[c] == 3 || (r == c && ++aDiagonal1 == 3) || (r + c == 2 && ++aDiagonal2 == 3)) return "A";
            }
        }
        return n == 9 ? "Draw" : "Pending";        
    }
    
  public static void main (String[] args) throws java.lang.Exception {
    int[][] moves = {{0,0}, {2,0}, {1,1}, {2,1}, {2,2}};
    	System.out.println(tictactoe(moves));
  }
}
A

जटिलता विश्लेषण

समय जटिलता

पर), जहां N फ़ंक्शन में इनपुट के रूप में भेजे गए मूव की संख्या है।

अंतरिक्ष जटिलता

O (R + C), क्योंकि हम टिक टीएसी पैर की अंगुली के खेल में पंक्ति और स्तंभ के बराबर आकार के 4 सरणियों का निर्माण करते हैं।