Assume the following rules are for the tic-tac-toe game on an n x n
board between two players:
- A move is guaranteed to be valid and is placed on an empty block.
- Once a winning condition is reached, no more moves are allowed.
- A player who succeeds in placing
n
of their marks in a horizontal, vertical, or diagonal row wins the game.
Implement the TicTacToe
class:
TicTacToe(int n)
Initializes the object the size of the boardn
.int move(int row, int col, int player)
Indicates that player with idplayer
plays at the cell(row, col)
of the board. The move is guaranteed to be a valid move.
Follow up:
Could you do better than O(n2)
per move()
operation?
Example 1:
Input ["TicTacToe", "move", "move", "move", "move", "move", "move", "move"] [[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]] Output [null, 0, 0, 0, 0, 0, 0, 1] Explanation TicTacToe ticTacToe = new TicTacToe(3); Assume that player 1 is "X" and player 2 is "O" in the board. ticTacToe.move(0, 0, 1); // return 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | | ticTacToe.move(0, 2, 2); // return 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | | | ticTacToe.move(2, 2, 1); // return 0 (no one wins) |X| |O| | | | | // Player 1 makes a move at (2, 2). | | |X| ticTacToe.move(1, 1, 2); // return 0 (no one wins) |X| |O| | |O| | // Player 2 makes a move at (1, 1). | | |X| ticTacToe.move(2, 0, 1); // return 0 (no one wins) |X| |O| | |O| | // Player 1 makes a move at (2, 0). |X| |X| ticTacToe.move(1, 0, 2); // return 0 (no one wins) |X| |O| |O|O| | // Player 2 makes a move at (1, 0). |X| |X| ticTacToe.move(2, 1, 1); // return 1 (player 1 wins) |X| |O| |O|O| | // Player 1 makes a move at (2, 1). |X|X|X|
Constraints:
2 <= n <= 100
- player is
1
or2
. 1 <= row, col <= n
(row, col)
are unique for each different call tomove
.- At most
n2
calls will be made tomove
.
设计井字棋。
请在 n × n 的棋盘上,实现一个判定井字棋(Tic-Tac-Toe)胜负的神器,判断每一次玩家落子后,是否有胜出的玩家。
在这个井字棋游戏中,会有 2 名玩家,他们将轮流在棋盘上放置自己的棋子。
在实现这个判定器的过程中,你可以假设以下这些规则一定成立:
1. 每一步棋都是在棋盘内的,并且只能被放置在一个空的格子里;
2. 一旦游戏中有一名玩家胜出的话,游戏将不能再继续;
3. 一个玩家如果在同一行、同一列或者同一斜对角线上都放置了自己的棋子,那么他便获得胜利。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/design-tic-tac-toe
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这是一道设计题。题目的 follow up 问能不能对于 move() 函数,给出优于 O(n^2) 的思路,我这里给出一个最优解。这个游戏给的棋盘是一个长度为 N 的正方形,只有两个玩家,如果两个玩家有任何一个玩家的棋子摆满了某一行,某一列或者某一条对角线,则判定为胜利,那么我们可以给两个玩家分别赋值 1 和 -1,来判断到底是谁走棋。如果某一行/某一列被同一个玩家占满,则那一行/那一列的sum会是 N 或者 -N。对于对角线也是一样,只是这里对角线的计算有些复杂,但是注意因为是正方形所以计算相对简单
- 正对角线diagonal - 只要判断是否 row == col 即可
- 反对角线antiDiagonal - 判断是否 col == N - row - 1即可
时间O(1)
空间O(n^2)
Java实现
1 class TicTacToe { 2 private int[] rows; 3 private int[] cols; 4 private int diagonal; 5 private int antiDiagonal; 6 7 /** Initialize your data structure here. */ 8 public TicTacToe(int n) { 9 rows = new int[n]; 10 cols = new int[n]; 11 } 12 13 /** Player {player} makes a move at ({row}, {col}). 14 @param row The row of the board. 15 @param col The column of the board. 16 @param player The player, can be either 1 or 2. 17 @return The current winning condition, can be either: 18 0: No one wins. 19 1: Player 1 wins. 20 2: Player 2 wins. */ 21 public int move(int row, int col, int player) { 22 int toAdd = player == 1 ? 1 : -1; 23 rows[row] += toAdd; 24 cols[col] += toAdd; 25 if (row == col) { 26 diagonal += toAdd; 27 } 28 if (col == (cols.length - row - 1)) { 29 antiDiagonal += toAdd; 30 } 31 32 int size = rows.length; 33 if (Math.abs(rows[row]) == size || Math.abs(cols[col]) == size || Math.abs(diagonal) == size 34 || Math.abs(antiDiagonal) == size) { 35 return player; 36 } 37 return 0; 38 } 39 } 40 41 /** 42 * Your TicTacToe object will be instantiated and called as such: 43 * TicTacToe obj = new TicTacToe(n); 44 * int param_1 = obj.move(row,col,player); 45 */