ຊອກຫາຜູ້ຊະນະໃນເຄື່ອງຫຼີ້ນ Tic Tac Toe ເກມ Leetcode Solution  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ ເຟສບຸກ Zoho
ຂັ້ນຕອນວິທີ Array ລະຫັດ ການສໍາພາດ ການສໍາພາດກ່ອນ LeetCode LeetCodeSolutions

ບັນຫາຊອກຫາຜູ້ຊະນະໃນເກມ Tic Tac Toe Game Leetcode Solution ຂໍໃຫ້ພວກເຮົາຊອກຫາຜູ້ທີ່ໄດ້ຮັບລາງວັນຊະນະເລີດຂອງເກມ toe tic tac toe. ບັນຫາໃຫ້ພວກເຮົາມີ array ຫຼື vector ຂອງຍ້າຍທີ່ເຮັດໂດຍຜູ້ຫຼີ້ນ. ພວກເຮົາຕ້ອງຜ່ານການເລື່ອນຂັ້ນແລະຕັດສິນຜູ້ທີ່ຊະນະເກມ. ຜົນໄດ້ຮັບຂອງເກມສາມາດຊະນະ, ແຕ້ມ, ຫລືຍັງຄອຍ. ໃນກໍລະນີ, ເມື່ອມີໃຜໃນພວກເຂົາຊະນະເກມ, ພວກເຮົາສົ່ງຄືນ 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".

ເບິ່ງ
Newman – Shanks – Williams ນາຍົກລັດຖະ

ສາ​ລະ​ບານ

ວິທີການ ສຳ ລັບການຊອກຫາຜູ້ຊະນະເລີດໃນເກມ Tic Tac Toe Game Leetcode Solution  

ບັນຫາແມ່ນການຊອກຫາ ຄຳ ຕັດສິນສຸດທ້າຍຂອງເກມ toe tic tac toe ຫຼັງຈາກຍ້າຍບາງຄັ້ງ. ມັນເປັນເກມມາດຕະຖານ, ສະນັ້ນພວກເຮົາຕ້ອງການພຽງແຕ່ ຈຳ ລອງຂັ້ນຕອນ. ພວກເຮົາຍັງຕ້ອງໄດ້ປະຕິບັດຂັ້ນຕອນຕາມ ລຳ ດັບດຽວກັນກັບທີ່ໄດ້ກ່າວໄວ້ໃນຂໍ້ມູນ. ວິທີ ໜຶ່ງ ແມ່ນການສ້າງຕາຂ່າຍໄຟຟ້າ 3 × 3 ແລະຈາກນັ້ນ ຈຳ ລອງຂະບວນການດຽວກັນ. ແຕ່ແທນທີ່ຈະເຮັດແນວນັ້ນ, ພວກເຮົາຕິດຕາມການເຄື່ອນໄຫວທີ່ເຮັດໂດຍນັກເຕະທັງສອງໃຊ້ອາຄານ. ພວກເຮົານໍາໃຊ້ 4 ຂອດທີ່ແຕກຕ່າງກັນສໍາລັບທັງສອງຜູ້ນ, 2 ສໍາລັບການເຄື່ອນໄຫວທີ່ເຮັດໂດຍພວກເຂົາກ່ຽວກັບແຕ່ລະແຖວແລະຖັນ. ສຳ ລັບການເຄື່ອນໄຫວແຕ່ລະຄັ້ງ, ພວກເຮົາເພີ່ມມູນຄ່າທີ່ເກັບໄວ້ໃນຂບວນເຫຼົ່ານີ້. ເມື່ອຄຸນຄ່າກາຍມາເປັນເທົ່າກັບ 3. ພວກເຮົາຮູ້ແລ້ວວ່າການຍ້າຍ 3 ຢ່າງແມ່ນຕັ້ງຢູ່ຕາມແນວນອນຫລືແນວຕັ້ງ.

ສຳ ລັບເສັ້ນຂວາງ, ພວກເຮົາພຽງແຕ່ໃຊ້ 4 ຕົວແປທີ່ຄ້າຍຄືກັບປ້າຍ. ເມື່ອຄ່າໃດໆກາຍເປັນເທົ່າກັບ 3. ພວກເຮົາສົ່ງຊື່ຕາມນັ້ນ. ແຕ່ຖ້າພວກເຮົາບໍ່ບັນລຸ ຄຳ ຕັດສິນດັ່ງກ່າວຈົນກວ່າທຸກການເຄື່ອນໄຫວຈະໄດ້ຮັບການປະຕິບັດແລ້ວ. ຫຼັງຈາກນັ້ນ, ພວກເຮົາກັບຄືນ ຄຳ ຕັດສິນຂອງການແຕ້ມຖ້າທຸກຮູບສີ່ຫຼ່ຽມມົນໃນຕາຂ່າຍໄຟຟ້າຖືກຄອບຄອງອື່ນທີ່ຍັງຄ້າງຈະຖືກສົ່ງຄືນ.

ລະຫັດ ສຳ ລັບການຊອກຫາຜູ້ຊະນະໃນເຄື່ອງຫຼີ້ນ Tic Tac Toe ເກມ Leetcode Solution  

ລະຫັດ 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), ບ່ອນທີ່ N ແມ່ນ ຈຳ ນວນຍ້າຍທີ່ຖືກສົ່ງມາເປັນການປ້ອນຂໍ້ມູນເຂົ້າໃນ ໜ້າ ທີ່.

ເບິ່ງ
ລະດັບຂອງແຕ່ລະ node ໃນ Tree ຈາກ node ແຫຼ່ງ

ຄວາມສັບສົນໃນອະວະກາດ

O (R + C), ເນື່ອງຈາກວ່າພວກເຮົາສ້າງ 4 ຂບວນທີ່ມີຂະ ໜາດ ເທົ່າກັບແຖວແລະຖັນຂອງຕາຂ່າຍໄຟຟ້າໃນເກມ tic tac toe.