设计一个Tic Tac Toe
根据图片可以知道,只要vertically, horizontally, 两个斜对角线 一共4个路线上 某一个路线上连了N个子就算获胜!
move(x, y, player) 是下棋function的参数。
return 只要return 谁获胜,要么player1, 要么player2, 要么没人获胜。【不需要画出棋盘】
看到了整个逻辑,但是还是非常难实现。 怎么判断有N个子连在了一起?
我初步的想法是,每当move一步之后,move(x, y, player). 把同一个x的row扫描一下,看看是不是全部== player, 是的话宣布胜利。 然后扫描一下y的col,看看是不是都是player,是的话宣布胜利。对角线的话就有点麻烦了,因为有的点是不存在对角线的,有的点在对角线上。 最中心的点还在2条对角线上。【不过后来想想其实还好,只要x !=y的,我们直接不查对角线。 如果x==y的,把两条对角线上查一下, 虽然有点费时间,但好歹也算完成任务。】
O(n) 应该可以搞定。
优化:【超级聪明。。。Player1的添加+1, Player2的添加-1, 抵消】