एक टिक टॅक टू गेम लीटकोड सोल्यूशनवर विजेता शोधा


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन सफरचंद फेसबुक Zoho
अरे

एक टिक टॅक टू गेम लीटकोड सोल्यूशनवर विजेता शोधा ही समस्या आम्हाला टिक टॅक टू गेमचा विजेता शोधण्यास सांगते. समस्या आम्हाला एक प्रदान करते अॅरे किंवा खेळाडूंनी केलेल्या चालींचा वेक्टर. गेममध्ये कोण विजय मिळविते हे आम्हाला समजून घेण्याची आवश्यकता आहे. खेळाचा निकाल जिंकणे, ड्रॉ करणे किंवा प्रलंबित असणे शक्य आहे. अशा प्रकरणांमध्ये जेव्हा त्यापैकी कोणीही गेम जिंकतो तेव्हा आम्ही ए किंवा बी परत करतो. परंतु खेळाचा न्याय करण्यापूर्वी, आम्हाला टिक टॅक टोच्या या विशिष्ट आवृत्तीच्या नियमांची माहिती असणे आवश्यक आहे.

  • खेळाडू केवळ अशा चौरसांवर हालचाली करू शकतात ज्याचा आधीपासून वापर केला गेला नाही.
  • पहिला खेळाडू A नेहमीच "एक्स" वर्ण ठेवते, तर दुसरा खेळाडू B नेहमी "ओ" वर्ण ठेवते.
  • “एक्स” आणि “ओ” वर्ण नेहमी रिक्त चौकांमध्ये ठेवले जातात. आधीपासून वापरलेले वर्ग कधीही वापरू नये.
  • जेव्हा गेममध्ये एक समान (रिक्त नसलेले) तीन पंक्ती, स्तंभ किंवा कर्ण भरतात तेव्हा खेळ संपेल.
  • सर्व स्क्वेअर रिक्त नसल्यास गेम देखील समाप्त होईल. काही प्रकरणांमध्ये, ते दोघे जिंकत नाहीत आणि बरोबरीत सुटतात.
  • खेळ संपल्यास यापुढे आणखी हालचाल करता येणार नाहीत. जर काही हालचाली बाकी असतील तर, निकाल “प्रलंबित” आहे.
  • प्लेअर “ए” प्रथम फिरतो आणि नंतर वैकल्पिक वळणे दोन्ही खेळाडू वापरतात.

चला काही उदाहरणे पहा.

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

एक टिक टॅक टू गेम लीटकोड सोल्यूशनवर विजेता शोधा

स्पष्टीकरणः वर दर्शविल्याप्रमाणे, “एक्स” असलेला खेळाडू गेम जिंकतो. नेहमी खेळ सुरू होतो, अशा प्रकारे विजेता देखील “ए” असतो.

तिकिट टॅक टू गेम लीटकोड सोल्यूशनवर विनर शोधा

काही हालचालींनंतर टिक टॅक टू गेमचा अंतिम निर्णय शोधण्यात समस्या आहे. हा एक मानक खेळ आहे, म्हणून आम्हाला फक्त प्रक्रियेचे अनुकरण करण्याची आवश्यकता आहे. इनपुटमध्ये दिलेल्या पद्धती प्रमाणे आम्हाला त्याच क्रमाने पावले देखील आवश्यक आहेत. एक मार्ग म्हणजे 3 × 3 चे ग्रिड तयार करणे आणि नंतर त्याच प्रक्रियेचे नक्कल करणे. परंतु असे करण्याऐवजी आम्ही दोन्ही खेळाडूंनी अ‍ॅरे वापरून केलेल्या हालचालींचा मागोवा ठेवतो. आम्ही दोन्ही खेळाडूंसाठी 4 वेगवेगळ्या अ‍ॅरे वापरतो, प्रत्येक पंक्ती आणि स्तंभ संबंधित त्यांच्याद्वारे केलेल्या हालचालींसाठी 2. प्रत्येक हालचालीसाठी आपण या अ‍ॅरे मध्ये संग्रहित केलेली व्हॅल्यूज वाढवू. एकदा व्हॅल्यूज 3 च्या समान झाल्या तेव्हा आम्हाला माहित आहे की 3 हालचाली आडव्या किंवा अनुलंब केल्या जातात.

कर्णांसाठी आम्ही अ‍ॅरे प्रमाणेच 4 व्हेरिएबल्स वापरतो. जेव्हा कोणतीही मूल्य 3 च्या समान होते तेव्हा आम्ही त्यानुसार नाव परत करतो. परंतु सर्व हालचाली होईपर्यंत आम्ही निर्णयापर्यंत पोहोचत नाही तर. ग्रीडवरील सर्व स्क्वेअर व्यापलेले असल्यास बाकी सोडल्यास आम्ही ड्रॉचा निकाल परत करतो.

एक टिक टॅक टू गेम लीटकोड सोल्यूशनवर विजेता शोधा यासाठी कोड

सी ++ कोड

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), जेथे एन ही फंक्शनला इनपुट म्हणून पाठविलेल्या मूव्हसची संख्या आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (आर + सी), कारण आम्ही टिक टॅ टू गेममध्ये ग्रिडच्या पंक्ती आणि स्तंभ समान आकाराचे 4 अ‍ॅरे तयार करतो.