Tic-tac-toe is played by two players A and B on a 3 x 3 grid.
Here are the rules of Tic-Tac-Toe:
- 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 3 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 an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.
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 (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.
一行或一列或者对角线如果全是一个人棋，那么这个人就赢了。注意还有两种状态，和棋和正在下，"Draw" and "Pending"
我感觉操作二维数组的写法有点麻烦，所以转换成一维的来判断。
class Solution(object): def tictactoe(self, moves): """ :type moves: List[List[int]] :rtype: str """ # 0 1 2 # 3 4 5 # 6 7 8 candidates = [ [0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6] ] grid = [-1] * 9 player = 0 for move in moves: grid[move[0] * 3 + move[1]] = player player += 1 player %= 2 for candidate in candidates: flag = True for i in range(1, len(candidate), 1): if grid[candidate[i]] != grid[candidate[i - 1]] or grid[candidate[i]] == -1: flag = False break if flag: return ‘A‘ if grid[candidate[0]] == 0 else ‘B‘ draw = 0 for i in range(9): if grid[i] != -1: draw += 1 if draw == 9: return ‘Draw‘ else: return ‘Pending‘