ടിക് ടാക് ടോ ഗെയിം ലീറ്റ്കോഡ് പരിഹാരത്തിൽ വിജയിയെ കണ്ടെത്തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ ഫേസ്ബുക്ക് Zoho
അറേ

ഒരു ടിക് ടോ ടോ ഗെയിമിൽ വിജയിയെ കണ്ടെത്തുക പ്രശ്നം ടീറ്റ് ടോ ടോ ഗെയിമിന്റെ വിജയിയെ കണ്ടെത്താൻ ലീറ്റ്കോഡ് പരിഹാരം ഞങ്ങളോട് ആവശ്യപ്പെടുന്നു. പ്രശ്നം ഞങ്ങൾക്ക് ഒരു നൽകുന്നു ശ്രേണി അല്ലെങ്കിൽ കളിക്കാർ നടത്തിയ നീക്കങ്ങളുടെ വെക്റ്റർ. ഞങ്ങൾ നീക്കങ്ങളിലൂടെ കടന്നുപോകുകയും ഗെയിമിൽ വിജയിക്കുന്നവരെ വിഭജിക്കുകയും വേണം. കളിയുടെ ഫലം വിജയിക്കാനോ സമനിലയിലാക്കാനോ ശേഷിക്കാനോ കഴിയും. ചില സന്ദർഭങ്ങളിൽ, അവരിൽ ആരെങ്കിലും ഗെയിമിൽ വിജയിക്കുമ്പോൾ, ഞങ്ങൾ എ അല്ലെങ്കിൽ ബി നൽകുന്നു. എന്നാൽ ഗെയിമിനെ വിഭജിക്കുന്നതിനുമുമ്പ്, ടിക് ടാക് ടോയുടെ ഈ നിർദ്ദിഷ്ട പതിപ്പിന്റെ നിയമങ്ങളെക്കുറിച്ച് ഞങ്ങൾ അറിഞ്ഞിരിക്കണം.

  • ഇതിനകം ഉപയോഗപ്പെടുത്താത്ത സ്ക്വയറുകളിൽ മാത്രമേ കളിക്കാർക്ക് നീക്കങ്ങൾ നടത്താൻ കഴിയൂ.
  • ആദ്യ കളിക്കാരൻ A എല്ലായ്പ്പോഴും “എക്സ്” പ്രതീകങ്ങൾ സ്ഥാപിക്കുന്നു, രണ്ടാമത്തെ കളിക്കാരൻ B എല്ലായ്പ്പോഴും “O” പ്രതീകങ്ങൾ സ്ഥാപിക്കുന്നു.
  • “എക്സ്”, “ഒ” പ്രതീകങ്ങൾ എല്ലായ്പ്പോഴും ശൂന്യമായ സ്ക്വയറുകളിൽ സ്ഥാപിക്കുന്നു. ഇതിനകം ഉപയോഗിച്ച സ്ക്വയറുകൾ ഒരിക്കലും ഉപയോഗിക്കരുത്.
  • ഏതെങ്കിലും വരി, നിര, അല്ലെങ്കിൽ ഡയഗണൽ എന്നിവ പൂരിപ്പിക്കുന്ന സമാന (ശൂന്യമല്ലാത്ത) 3 പ്രതീകങ്ങൾ ഉള്ളപ്പോൾ ഗെയിം അവസാനിക്കുന്നു.
  • എല്ലാ സ്ക്വയറുകളും ശൂന്യമല്ലെങ്കിൽ ഗെയിമും അവസാനിക്കുന്നു. ചില സന്ദർഭങ്ങളിൽ, ഇരുവരും വിജയിക്കുകയും സമനിലയിൽ അവസാനിക്കുകയും ചെയ്യുന്നില്ല.
  • കളി അവസാനിച്ചാൽ കൂടുതൽ നീക്കങ്ങളൊന്നും നടത്താൻ കഴിയില്ല. ചില നീക്കങ്ങൾ‌ അവശേഷിക്കുന്നുണ്ടെങ്കിൽ‌, വിധി “തീർപ്പുകൽപ്പിച്ചിട്ടില്ല”.
  • പ്ലെയർ “എ” ആദ്യ നീക്കം നടത്തുന്നു, തുടർന്ന് ഇതര വളവുകൾ രണ്ട് കളിക്കാരും ഉപയോഗിക്കുന്നു.

കുറച്ച് ഉദാഹരണങ്ങൾ നോക്കാം.

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), ഇവിടെ N എന്നത് ഫംഗ്ഷനിലേക്ക് ഇൻപുട്ടായി അയച്ച നീക്കങ്ങളുടെ എണ്ണമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (R + C), കാരണം, ടിക് ടോ ടോ ഗെയിമിൽ ഗ്രിഡിന്റെ വരിയും നിരയും തുല്യമായ 4 അറേകൾ ഞങ്ങൾ സൃഷ്ടിക്കുന്നു.