[Swift]LeetCode348.设计井字棋游戏$DesignTic-Tac-Toe

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10740257.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves is allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Example:
Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.

TicTacToe toe = new TicTacToe(3);

toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 2 makes a move at (0, 2).
| | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 1 makes a move at (2, 2).
| | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 2 makes a move at (1, 1).
| | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 1 makes a move at (2, 0).
|X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| | // Player 2 makes a move at (1, 0).
|X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| | // Player 1 makes a move at (2, 1).
|X|X|X|
Follow up:
Could you do better than O(n2) per move() operation?

Hint:

Could you trade extra space such that move() operation can be done in O(1)?
You need two arrays: int rows[n], int cols[n], plus two variables: diagonal, anti_diagonal.

设计一个井字游戏，在N x N网格上的两个玩家之间进行。

您可以假定以下规则：

移动被保证是有效的，并且被放置在一个空块上。

一旦达到获胜条件，就不允许再移动。

在横排、竖排或斜排中成功放置N个标记的玩家获胜。

例子：

假设n=3，假设玩家1是“x”，玩家2是“o”。

TicTacToe toe = new TicTacToe(3);

toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 2 makes a move at (0, 2).
| | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 1 makes a move at (2, 2).
| | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 2 makes a move at (1, 1).
| | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 1 makes a move at (2, 0).
|X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| | // Player 2 makes a move at (1, 0).
|X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| | // Player 1 makes a move at (2, 1).
|X|X|X|

跟进：

每个move()操作可以做得比O(n2) 更好吗？

提示：

您是否可以交换额外的空间，以便在O(1)中执行move()操作？

您需要两个数组：int rows[n]、int cols[n]，加上两个变量：对角线、反斜线。

Solution:

 1 class TicTacToe {
 2     var diag:Int = 0
 3     var rev_diag:Int = 0
 4     var N:Int = 0
 5     var rows:[Int] = [Int]()
 6     var cols:[Int] = [Int]()
 7     
 8     init(_ n:Int)
 9     {
10         self.rows = [Int](repeating:0,count:n)
11         self.cols = [Int](repeating:0,count:n)
12         self.N = n
13     }
14     
15     func move(_ row:Int,_ col:Int,_ player:Int) -> Int
16     {
17         var add:Int = player == 1 ? 1 : -1
18         rows[row] += add
19         cols[col] += add
20         diag += (row == col ? add : 0)
21         rev_diag += (row == N - col - 1 ? add : 0)
22         if abs(rows[row]) == N || abs(cols[col]) == N || abs(diag) == N || abs(rev_diag) == N
23         {
24             return player
25         }
26         return 0
27     }    
28 }

点击：Playground测试

 1 var toe:TicTacToe = TicTacToe(3)
 2 
 3 //toe.move(0, 0, 1); -> Returns 0 (no one wins)
 4 print(toe.move(0, 0, 1))
 5 //Print 0
 6 
 7 //toe.move(0, 2, 2); -> Returns 0 (no one wins)
 8 print(toe.move(0, 2, 2))
 9 //Print 0
10 
11 //toe.move(2, 2, 1); -> Returns 0 (no one wins)
12 print(toe.move(2, 2, 1))
13 //Print 0
14 
15 //toe.move(1, 1, 2); -> Returns 0 (no one wins)
16 print(toe.move(1, 1, 2))
17 //Print 0
18 
19 //toe.move(2, 0, 1); -> Returns 0 (no one wins)
20 print(toe.move(2, 0, 1))
21 //Print 0
22 
23 //toe.move(1, 0, 2); -> Returns 0 (no one wins)
24 print(toe.move(1, 0, 2))
25 //Print 0
26 
27 //toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
28 print(toe.move(2, 1, 1))
29 //Print 1