Tic Tac Toe Oyunu Leetcode Çözümündə Qalib tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon alma Facebook Zoho
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 35

Tic Tac Toe Oyununun Qalibini tapma problemi Leetcode Solution bizdən tic tac toe oyununun qalibini tapmağımızı xahiş edir. Problem bizə bir array və ya oyunçular tərəfindən edilən hərəkətlərin vektoru. Hamlelərdən keçməli və oyunu kimin qazandığını qiymətləndirməliyik. Oyunun nəticəsi qazanmaq, heç-heçə etmək və ya gözləmək olar. Hər hansı birində oyunu qazandıqda, A və ya B-yə qayıdırıq. Ancaq oyunu qiymətləndirmədən əvvəl Tic Tac Toe-nin bu xüsusi versiyasının qaydalarından xəbərdar olmalıyıq.

  • Oyunçular yalnız onsuz da istifadə olunmamış kvadratlarda hərəkət edə bilər.
  • İlk oyunçu A həmişə ikinci oyunçu ikən “X” işarələrini yerləşdirir B həmişə “O” simvollarını yerləşdirir.
  • “X” və “O” simvolları həmişə boş kvadratlara yerləşdirilir. Artıq istifadə edilmiş kvadratlardan heç vaxt istifadə etmək olmaz.
  • Hər hansı bir sıra, sütun və ya diaqonal dolduran eyni 3 (boş olmayan) simvol olduqda oyun başa çatır.
  • Bütün meydanların boş olmadığı təqdirdə oyun da bitir. Bəzi hallarda, ikisi də qalib gəlmir və heç-heçə ilə nəticələnir.
  • Oyun bitmişsə, daha çox hərəkət edilə bilməz. Bəzi hərəkətlər qalıbsa, qərar “Gözləməlidir”.
  • Oyunçu "A" ilk hərəkəti edir, sonra alternativ növbələr hər iki oyunçu tərəfindən istifadə olunur.

Bir neçə nümunəyə nəzər salaq.

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

Tic Tac Toe Oyunu Leetcode Çözümündə Qalib tapınPin

İzahat: Yuxarıda şəkildə göstərildiyi kimi “X” olan oyunçu oyunda qalib gəlir. A həmişə oyuna başlayır, beləliklə qalib “A” olur.

Tic Tac Toe Oyunu Leetcode Çözümündə Qalib axtarın yanaşması

Problem, bəzi hərəkətlərdən sonra tik tac toe oyununun son qərarını tapmaqdır. Standart bir oyundur, buna görə prosesi sadəcə simulyasiya etməliyik. Həm də addımları girişdə göstərilən qaydada yerinə yetirməliyik. Bir üsul 3 × 3 hörgü yaratmaq və sonra eyni prosesi simulyasiya etməkdir. Ancaq bunu etmək əvəzinə, hər iki oyunçunun massivlərdən istifadə etdiyi hərəkətləri izləyirik. Hər iki oyunçu üçün 4 fərqli sıra istifadə edirik, hər biri hər bir sıra və sütunla əlaqəli hərəkətlər üçün 2. Hər bir hərəkət üçün bu massivlərdə saxlanılan dəyərləri artırırıq. Dəyərlər 3-ə bərabər olduqda bilirik ki, 3 hərəkət ya üfüqi, həm də şaquli olaraq edilir.

Diaqonallar üçün sadəcə massivlərə bənzər 4 dəyişəndən istifadə edirik. Dəyərdən hər hansı biri 3-ə bərabər olduqda, adı müvafiq olaraq qaytarırıq. Ancaq bütün hərəkətlər edilməyənə qədər bir hökm çıxarmırıqsa. Şəbəkədəki bütün kvadratlar zəbt olunduqda geri çəkildikdə, çəkiliş hökmünü qaytarırıq.

Tic Tac Toe Oyunu Leetcode Çözümündə Qalib Bulma Kodu

C ++ kodu

#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 kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), burada N - funksiyaya giriş olaraq göndərilən hərəkətlərin sayı.

Kosmik Mürəkkəblik

O (R + C), çünki tic tac toe oyununda ızgaranın sətirinə və sütununa bərabər 4 ölçülü massiv yaradırıq.

Şərh yaz

Translate »
1