ఈడ్పు టాక్ టో గేమ్ లీట్‌కోడ్ సొల్యూషన్‌లో విజేతను కనుగొనండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ ఆపిల్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> జోహో
అర్రే

ఈడ్పు టాక్ బొటనవేలు గేమ్‌లో విజేతను కనుగొనండి సమస్య లీట్‌కోడ్ సొల్యూషన్ ఈడ్పు టాక్ బొటనవేలు ఆట విజేతను కనుగొనమని అడుగుతుంది. సమస్య మాకు ఒక అందిస్తుంది అమరిక లేదా ఆటగాళ్ళు చేసిన కదలికల వెక్టర్. మేము కదలికల ద్వారా వెళ్ళాలి మరియు ఆట గెలిచిన న్యాయమూర్తి. ఆట యొక్క ఫలితం గెలవవచ్చు, డ్రా చేయవచ్చు లేదా పెండింగ్‌లో ఉంటుంది. సందర్భాల్లో, వారిలో ఎవరైనా ఆట గెలిచినప్పుడు, మేము A లేదా B ని తిరిగి ఇస్తాము. కాని ఆటను నిర్ణయించే ముందు, ఈ నిర్దిష్ట సంస్కరణ యొక్క టిక్ టాక్ టో యొక్క నియమాల గురించి మనం తెలుసుకోవాలి.

  • ఇప్పటికే ఉపయోగించని చతురస్రాలపై మాత్రమే ఆటగాళ్ళు కదలికలు చేయవచ్చు.
  • మొదటి ఆటగాడు A ఎల్లప్పుడూ “X” అక్షరాలను ఉంచుతుంది, రెండవ ఆటగాడు B ఎల్లప్పుడూ “O” అక్షరాలను ఉంచుతుంది.
  • “X” మరియు “O” అక్షరాలు ఎల్లప్పుడూ ఖాళీ చతురస్రాల్లో ఉంచబడతాయి. ఇప్పటికే ఉపయోగించిన చతురస్రాలను ఎప్పుడూ ఉపయోగించకూడదు.
  • ఏదైనా వరుస, కాలమ్ లేదా వికర్ణాన్ని నింపే ఒకే (ఖాళీ కాని) అక్షరాలలో 3 ఉన్నప్పుడు ఆట ముగుస్తుంది.
  • అన్ని చతురస్రాలు ఖాళీగా లేకుంటే ఆట కూడా ముగుస్తుంది. కొన్ని సందర్భాల్లో, ఇద్దరూ గెలవలేరు మరియు డ్రాలో ముగుస్తుంది.
  • ఆట ముగిస్తే ఎక్కువ కదలికలు ఆడలేము. కొన్ని కదలికలు మిగిలి ఉంటే, తీర్పు “పెండింగ్”.
  • ప్లేయర్ “ఎ” మొదటి కదలికను చేస్తుంది మరియు తరువాత ప్రత్యామ్నాయ మలుపులు ఇద్దరు ఆటగాళ్ళు ఉపయోగిస్తారు.

కొన్ని ఉదాహరణలను పరిశీలిద్దాం.

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

ఈడ్పు టాక్ టో గేమ్ లీట్‌కోడ్ సొల్యూషన్‌లో విజేతను కనుగొనండి

వివరణ: చిత్రంలో పైన చూపిన విధంగా, “X” ఉన్న ఆటగాడు ఆటను గెలుస్తాడు. ఎల్లప్పుడూ ఆట ప్రారంభమవుతుంది, అందువలన విజేత కూడా “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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), ఇక్కడ N అనేది ఫంక్షన్‌కు ఇన్‌పుట్‌గా పంపిన కదలికల సంఖ్య.

అంతరిక్ష సంక్లిష్టత

O (R + C), ఎందుకంటే మేము ఈడ్పు టాక్ కాలి ఆటలో గ్రిడ్ యొక్క అడ్డు వరుస మరియు కాలమ్‌కు సమానమైన 4 శ్రేణుల పరిమాణాన్ని సృష్టిస్తాము.