Пронађите победника на Леиццоде решењу игре Тиц Тац Тое  


Ниво тешкоће Лако
Често питани у амазонка јабука фацебоок Зохо
алгоритми Ред шифрирање Интервју интервјупреп ЛеетЦоде ЛеетЦодеСолутионс

Проблем Пронађи победника у игри Тиц Тац Тое Леетцоде Солутион тражи да откријемо победника игре тик тактичари. Проблем нам пружа поредак или вектор потеза играча. Морамо проћи кроз потезе и пресудити ко добија утакмицу. Исход игре се може добити, извући или чекати. У случајевима када било ко од њих победи у игри, враћамо А или Б. Али пре него што оценимо игру, морамо бити свесни правила ове специфичне верзије Тиц Тац Тое.

  • Играчи могу да праве потезе само на квадратима који већ нису искоришћени.
  • Први играч A увек ставља знакове „Кс“, док други играч B увек ставља знакове „О“.
  • Знакови „Кс“ и „О“ увек се стављају у празне квадрате. Никада не треба користити квадрате који су већ искоришћени.
  • Игра се завршава када постоје 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

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

Сложеност времена

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

Види такође
Ниво сваког чвора у дрвету од изворног чвора

Сложеност простора

О (Р + Ц), јер стварамо 4 низа величине једнака реду и колони мреже у игри тик-так.

1