Գտեք հաղթողին Tic Tac Toe Game- ի Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon խնձոր facebook Zoho
Դասավորություն

Tic Tac Toe Game- ում հաղթող գտնելու խնդիրը Leetcode Solution- ը խնդրում է մեզ պարզել tic tac toe խաղի հաղթողին: Խնդիրը մեզ ապահովում է ան դասավորություն կամ խաղացողների կողմից կատարված քայլերի վեկտորը: Մենք պետք է անցնենք քայլերի միջով և դատենք, թե ով է հաղթում խաղը: Խաղի արդյունքը կարելի է շահել, ոչ-ոքի կամ սպասել: Այն դեպքերում, երբ նրանցից որևէ մեկը շահում է խաղը, մենք վերադառնում ենք A կամ B. Բայց խաղը դատելուց առաջ մենք պետք է տեղյակ լինենք Tic Tac Toe- ի այս հատուկ տարբերակի կանոններին:

  • Խաղացողները կարող են շարժումներ կատարել միայն չօգտագործված հրապարակներում:
  • Առաջին խաղացողը A միշտ տեղադրում է «X» նիշ, մինչդեռ երկրորդ նվագարկիչը B միշտ տեղադրում է «O» նիշերը:
  • «X» և «O» նիշերը միշտ տեղադրվում են դատարկ հրապարակներում: Երբեք չպետք է օգտագործվի արդեն օգտագործված հրապարակներ:
  • Խաղն ավարտվում է, երբ առկա են 3 նույն տողերը (ոչ դատարկ), որոնք լրացնում են ցանկացած տող, սյուն կամ անկյունագիծ:
  • Խաղը նույնպես ավարտվում է, եթե բոլոր հրապարակները դատարկ չեն: Որոշ դեպքերում երկուսն էլ չեն շահում և հայտնվում են ոչ-ոքի:
  • Այլևս ոչ մի քայլ չի կարող խաղացել, եթե խաղն ավարտված է: Եթե ​​որոշ քայլեր են մնացել, դատավճիռը «առկախ է»:
  • «A» խաղացողը կատարում է առաջին քայլը, իսկ հետո այլընտրանքային շրջադարձերն օգտագործվում են երկու խաղացողների կողմից:

Եկեք նայենք մի քանի օրինակների:

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

Գտեք հաղթողին Tic Tac Toe Game- ի Leetcode լուծում

Բացատրություն. Ինչպես ցույց է տրված նկարում վերևում, «X» խաղացողը շահում է խաղը: A- ն միշտ է սկսում խաղը, ուստի հաղթողը նաև “A” - ն է:

Tic Tac Toe Խաղի Leetcode լուծման համար հաղթող գտնելու մոտեցում

Խնդիրն այն է, որ որոշ քայլերից հետո գտնվի tic tac toe խաղի վերջնական դատավճիռը: Դա ստանդարտ խաղ է, ուստի պետք է պարզապես նմանակել գործընթացը: Մենք նաև պետք է կատարենք քայլերը նույն կարգով, ինչ տրված է մուտքագրման մեջ: Մեկ տարբերակ է ստեղծել ցանց 3 a 3-ի, ապա նմանակել նույն գործընթացը: Բայց դա անելու փոխարեն, մենք հետևում ենք այն շարժումներին, որոնք կատարում են զանգվածները օգտագործող երկու խաղացողները: Մենք օգտագործում ենք 4 տարբեր զանգված երկու խաղացողների համար, 2-ը `նրանց կողմից կատարված քայլերի համար յուրաքանչյուր տողի և սյունակի վերաբերյալ: Յուրաքանչյուր շարժման համար մենք ավելացնում ենք այս զանգվածներում պահված արժեքները: Երբ արժեքները հավասար են 3. Մենք գիտենք, որ 3 շարժում կատարվում է կամ հորիզոնական կամ ուղղահայաց:

Անկյունագծերի համար մենք պարզապես օգտագործում ենք զանգվածների նման 4 փոփոխական: Երբ արժեքներից որևէ մեկը դառնա 3-ի, մենք համապատասխանաբար վերադարձնում ենք անունը: Բայց եթե մենք դատավճռի չհասնենք, քանի դեռ բոլոր քայլերը չեն կատարվել: Դրանից հետո մենք վերադարձնում ենք վիճակահանության դատավճիռը, եթե ցանցի բոլոր քառակուսիները զբաղեցված լինեն, այլապես սպասում է, որ վերադարձվի:

Tic Tac Toe Game- ի համար հաղթող գտնելու կոդ 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

Java կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), որտեղ N- ը գործառույթի համար որպես ներդրում ուղարկված շարժումների քանակն է:

Տիեզերական բարդություն

O (R + C), քանի որ tic tac toe խաղում ստեղծում ենք ցանցի տողին և սյունակին հավասար չափի 4 զանգված: