برنده بازی Tic Tac Toe بازی Leetcode Solution باشید


سطح دشواری ساده
اغلب در آمازون سیب فیس بوک ZOHO
صف

مسئله Find Winner on a 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 بازی Leetcode Solution باشید

توضیحات: همانطور که در شکل بالا نشان داده شده است ، بازیکنی که دارای "X" باشد ، برنده بازی است. A همیشه بازی را شروع می کند ، بنابراین برنده نیز "A" است.

رویکرد یافتن برنده در راه حل بازی کد Tic Tac Toe

مشکل این است که بعد از برخی حرکات ، حکم نهایی بازی tic tac toe را پیدا کنید. این یک بازی استاندارد است ، بنابراین ما فقط باید فرآیند را شبیه سازی کنیم. ما همچنین باید مراحل را به همان ترتیب داده شده در ورودی انجام دهیم. یکی از راه ها ایجاد یک شبکه 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

کد جاوا

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 تعداد حرکات ارسال شده به عنوان ورودی به تابع است.

پیچیدگی فضا

O (R + C) ، زیرا ما 4 آرایه به اندازه ردیف و ستون شبکه در بازی tic tac toe ایجاد می کنیم.