current position:Home>leetcode 1275. Find Winner on a Tic Tac Toe Game(python)

leetcode 1275. Find Winner on a Tic Tac Toe Game(python)

2022-01-31 11:19:19 Wang Daya

「 This is my participation 11 The fourth of the yuegengwen challenge 12 God , Check out the activity details :2021 One last more challenge

describe

Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:

  • Players take turns placing characters into empty squares ' '.
  • The first player A always places 'X' characters, while the second player B always places 'O' characters.
  • 'X' and 'O' characters are always placed into empty squares, never on filled ones.
  • The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.
  • The game also ends if all squares are non-empty.
  • No more moves can be played if the game is over.

Given a 2D integer array moves where moves[i] = [rowi, coli] indicates that the ith move will be played on grid[rowi][coli]. return the winner of the game if it exists (A or B). In case the game ends in a draw return "Draw". If there are still movements to play return "Pending".

You can assume that moves is valid (i.e., it follows the rules of Tic-Tac-Toe), the grid is initially empty, and A will play first.

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: A wins, they always play first.
 Copy code 

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: B wins.
 Copy code 

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.
 Copy code 

Example 4:

Input: moves = [[0,0],[1,1]]
Output: "Pending"
Explanation: The game has not finished yet.
 Copy code 

Note:

1 <= moves.length <= 9
moves[i].length == 2
0 <= rowi, coli <= 2
There are no repeated elements on moves.
moves follow the rules of tic tac toe.
 Copy code 

analysis

According to the meaning , Two players in one 3*3 Play in the square called Tic-tac-toe The game of , The following rules :

  • Players take turns putting characters into empty squares .
  • The first player A Always place 'X' character , And the second player B Always place 'O' character .
  • 'X' and 'O' Characters are always placed in empty squares
  • When three are the same ( Non empty ) Fill any line with characters 、 Column or diagonal line , Game over .
  • If all squares are not empty , The game will end .
  • If the game is over , You can't do anything anymore .

Given a two-dimensional array of integers moves , among move[i] = [rowi,coli] It means the first one i One operation is in grid[rowi][coli] on . If A or B Can meet three consecutive characters in the same line 、 Same column or diagonal , Then return to the winner of the game . If the game ends in a draw , Then return to Draw . If there is still room to continue the game , Please return Pending .

In fact, the topic is also very simple after understanding , Ideas as follows :

  • take A Take out all the positions in the box and put them into the list A in , take B Take out all the positions in the box and put them into the list B in
  • Because there are only eight conditions to win , So list them all and put them in winCom in
  • Traverse winCom Every win in com , If the judgment list A and com If the elements in the are equal, it returns A , Similarly, if the judgment list B and com If the elements in the are equal, it returns B
  • Otherwise, if the list A And list B The sum of the length of is 9 It means a draw , Go straight back to Draw
  • Otherwise go straight back to Pending

answer

class Solution(object):
    def tictactoe(self, moves):
        """
        :type moves: List[List[int]]
        :rtype: str
        """
        winCom = [[[0,0],[0,1],[0,2]] , [[1,0],[1,1],[1,2]], [[2,0],[2,1],[2,2]],
                  [[0,0],[1,0],[2,0]],[[0,1],[1,1],[2,1]],[[0,2],[1,2],[2,2]],
                  [[0,0],[1,1],[2,2]],[[0,2],[1,1],[2,0]]]
        A = [c for c in moves[0:len(moves):2]]
        B = [c for c in moves[1:len(moves):2]]
        for com in winCom:
            if self.isWin(A, com): return 'A'
            if self.isWin(B, com): return 'B'
        if len(A)+len(B)==9: return "Draw"
        return "Pending"
            
    def isWin(self, L, com):
        result = 0
        for c in L:
            if c in com:
                result += 1
        return result == 3
            
            



        	      
		
 Copy code 

Running results

Runtime: 24 ms, faster than 52.05% of Python online submissions for Find Winner on a Tic Tac Toe Game.
Memory Usage: 13.3 MB, less than 71.11% of Python online submissions for Find Winner on a Tic Tac Toe Game.
 Copy code 

Original link :leetcode.com/problems/fi…

Your support is my greatest motivation

copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201311119176107.html

Random recommended