oli51467 / go-datastructure Goto Github PK

下棋时，对弈双方各执一种颜色的棋子，黑先白后，轮流将一枚棋子放置于交叉点上。与棋子直线相连的空白交叉点叫做气。当这些气都被对方棋子占据后，该棋子就没有了“气”，要被从棋盘上提掉。

如果棋子的相邻（仅上下左右）直线交叉点上有了同色的棋子，则这两个棋子被叫做相连的。任意多个棋子可以以此方式联成一体，连成一体的棋子的气的数目是所有组成这块棋的单个棋子气数之和。如果这些气都被异色棋子占领，这块棋子就要被一起提掉。

劫是围棋中较特殊的一种情况。举例来说，当黑方某一手提掉对方一子，而这一个黑子恰好处于白方虎口之内，这时白方不能立即提掉这一黑子，而必须在棋盘其他地方着一手（称为“找劫材”），使黑方不得不应一手（称为“应劫”），然后白才能够提掉这个黑子。

下子时，除非能令对方某些子失去所有的气，否则不得下子令自己某些子失去所有气，这亦被称为“禁止自杀规则”

getAllGroupsLengthAndLiberty：

使用Flood Fill遍历棋盘上的所有位置，如果这个位置没有棋子，则 跳过。如果有棋子，从该棋子开始遍历所有连接该棋子的同色棋子(组)，(即使组内只有一颗棋子)。

遍历完成后， 获取该组的长度和它的所有的气。根据围棋规则，当一步落下时，除了该子所属的组，不可能杀死自己的其它组，所以 这里只需要判断对方的某个或某些组是否被杀死。

一个局部形成打劫，当且仅当：该子落下后，该子所在的组失去了所有的气并且该子所在的组只有一个棋子(即它本身)&& 该子落下后对方仅有一个组失去了所有的气且该组只有一颗棋子。 如果该局部形成打劫，更新对方的禁入点，禁入点即为 该子落下后，对方被提吃的仅有的一颗子的位置。

play：判断一步棋是否可以走在棋盘上，如果可以，则更新棋盘，如果不可能，则什么都不会更新。

1. 如果该点在棋盘外或者该点的位置已经有子，则不可以落子，返回false
2. 如果该点在本方记录的打劫禁入点内，则不可以落子，返回false
3. 排除以上两种情况后，则一定可以落子(没有反例)

判断可以落子后：

1. 清空辅助数组
2. 将该子真正地更新在棋盘上(很重要)
3. 遍历该子所属的整个组，并记录该组的长度
4. 遍历棋盘，检查对方是否有一个或一串棋子被吃
5. 如果没有对方没有棋子被吃，并且自己该子落下后失去了所有的气，那么该行为属于自杀，落子无效，恢复该位置的棋盘落子，并返回false
6. 否则该位置可以落子，并清空自己的所有禁入点，因为该落子的有效意味着这是一枚劫财，之后的所有打劫处都可以落子。

欢迎提出问题！🌟🌟🌟