Найдите победителя в решении Leetcode для игры в крестики-нолики


Сложный уровень Легко
Часто спрашивают в Амазонка Apple Facebook Zoho
массив

Задача «Найти победителя в игре в крестики-нолики» Leetcode Solution просит нас определить победителя в игре в крестики-нолики. Проблема дает нам массив или вектор ходов игроков. Нам нужно пройти ходы и судить, кто выиграет игру. Результатом игры может быть выигрыш, ничья или ожидание. В случаях, когда любой из них выигрывает игру, мы возвращаем A или B. Но прежде чем судить игру, мы должны знать правила этой конкретной версии Tic Tac Toe.

  • Игроки могут делать ходы только на неиспользованных клетках.
  • Первый игрок A всегда помещает символы «X», в то время как второй игрок B всегда помещает символы «O».
  • Символы «X» и «O» всегда помещаются в пустые квадраты. Никогда не следует использовать уже использованные квадраты.
  • Игра заканчивается, когда 3 одинаковых (непустых) символа заполняют любую строку, столбец или диагональ.
  • Игра также заканчивается, если все клетки не пусты. В некоторых случаях они оба не выигрывают и заканчивают вничью.
  • Если игра окончена, больше нельзя делать ходов. Если остались ходы, выносится вердикт «Ожидается».
  • Игрок «А» делает первый ход, а затем оба игрока используют поочередные ходы.

Давайте посмотрим на несколько примеров.

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

Найдите победителя в решении Leetcode для игры в крестики-нолики

Объяснение: Как показано на рисунке выше, игрок с «X» выигрывает игру. A всегда начинает игру, поэтому победителем также становится «A».

Подход к поиску победителя в решении Leetcode для игры в крестики-нолики

Задача состоит в том, чтобы после нескольких ходов найти окончательный вердикт игры в крестики-нолики. Это стандартная игра, поэтому нам нужно просто смоделировать процесс. Нам также необходимо выполнить шаги в том же порядке, что и во входных данных. Один из способов - создать сетку 3 × 3, а затем смоделировать тот же процесс. Но вместо этого мы отслеживаем ходы, сделанные обоими игроками, используя массивы. Мы используем 4 разных массива для обоих игроков, по 2 для ходов, сделанных ими в каждой строке и столбце. Для каждого хода мы увеличиваем значения, хранящиеся в этих массивах. Как только значения станут равными 3. Мы знаем, что 3 хода выполняются либо по горизонтали, либо по вертикали.

Для диагоналей мы просто используем 4 переменные, аналогичные массивам. Когда любое из значений становится равным 3. Мы возвращаем имя соответственно. Но если мы не вынесем вердикта, пока не будут сделаны все шаги. Затем мы возвращаем вердикт ничьей, если все клетки в сетке заняты, иначе возвращается ожидающий результат.

Код для поиска победителя в игре в крестики-нолики Решение Leetcode

Код 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 массива размером, равным строке и столбцу сетки в игре крестики-нолики.