Пронајдете победник на прст со прсти во играта Tic Tac Toe


Ниво на тешкотија Лесно
Често прашувано во Амазон Јаболко Facebook Zoho
Низа

Проблемот Пронајдете победник на играта со прсти со прсти, решението „Leetcode Solution“ нè замолува да го откриеме победникот во играта со прсти со прсти. Проблемот ни обезбедува ан низа или вектор на потези направени од играчите. Треба да поминеме низ потезите и да процениме кој ја добива играта. Исходот од играта може да се победи, да се извлече нерешено или да се чека. Во случаи, кога некој од нив ќе ја добие играта, ние враќаме А или Б. Но, пред да ја судиме играта, мора да бидеме свесни за правилата на оваа специфична верзија на Тик Так То.

  • Играчите можат да прават потези само на квадрати што не се искористени веќе.
  • Првиот играч A секогаш поставува знаци „X“, додека вториот играч B секогаш поставува знаци „О“.
  • Знаците „X“ и „O“ секогаш се поставуваат на празни плоштади. Никогаш не треба да се користат квадрати што се веќе искористени.
  • Играта завршува кога има 3 со ист (непразен) карактер што исполнува кој било ред, колона или дијагонала.
  • Играта исто така завршува ако сите плоштади не се празни. Во некои случаи, и двајцата не победуваат и завршуваат нерешено.
  • Нема повеќе потези ако играта е завршена. Ако останат некои потези, пресудата е „Во тек“.
  • Играчот „А“ го прави првиот потег, а потоа алтернативните вртења ги користат и двајцата играчи.

Ајде да погледнеме неколку примери.

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

Пронајдете победник на прст со прсти во играта Tic Tac Toe

Објаснување: Како што е прикажано погоре на сликата, играчот со „X“ ја добива играта. А секогаш ја започнува играта, со што победник е и „А“.

Пристап кон пронаоѓање на победник на решение за лет код за игра на прсти со прсти

Проблемот е да се најде конечната пресуда за играта тик-прст по неколку потези. Тоа е стандардна игра, затоа треба само да го симулираме процесот. Исто така, треба да ги извршиме чекорите по истиот редослед како што е дадено во влезот. Еден начин е да се создаде мрежа од 3 × 3 и потоа да се симулира истиот процес. Но, наместо да го правиме тоа, ние ги следиме потезите направени од двајцата играчи со користење на низи. Ние користиме 4 различни низи за двајцата играчи, 2 за потези направени од нив во врска со секој ред и колона. За секој потег, ги зголемуваме вредностите зачувани во овие низи. Штом вредностите станат еднакви на 3. Знаеме дека 3 потези се прават или хоризонтално или вертикално.

За дијагоналите, ние едноставно користиме 4 варијабли слични на низите. Кога која било од вредноста стане еднаква на 3. Ние соодветно го враќаме името. Но, ако не донесеме пресуда се додека не се направат сите потези. Потоа враќаме пресуда за ждрепката ако сите плоштади на решетката се зафатени на друго место во очекување е вратена.

Код за пронаоѓање на победник на прст со прсти во играта Tic Tac Toe Игра Решение за лет код

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

Анализа на сложеност

Временска комплексност

НА), каде што N е бројот на потези испратени како влез на функцијата.

Комплексноста на просторот

О (R + C), затоа што создаваме 4 низи со големина еднакви на редот и колоната на решетката во играта tic tac toe.