【ACM/算法】五子棋

[zkeenly]

[zkeenly]

此题尚未完全AC，但是在牛客网另一道五子棋试题中稍加修改是可以AC的，当然是由于样例没有完全分析到的原因 牛客网-五子棋

这道题其实看起来是比较容易的，做起来也非麻烦的事情，就是每个点判断上下左右是否成立五子棋的标准。 但是我有一个比较普适性的且容易扩展的方法来解决，就是采用卷积滤波的方式，采用四个5*5的卷积滤波来对棋盘卷积判定，这样的方法对于六子棋，四子棋之类的都可以很容易扩展。 首先构建四个卷积滤波： array_line = [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] array_long = [[0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [0, 0, 1, 0, 0]] array_slant1 = [[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1]] array_slant2 = [[0, 0, 0, 0, 1], [0, 0, 0, 1, 0], [0, 0, 1, 0, 0], [0, 1, 0, 0, 0], [1, 0, 0, 0, 0]] 将原始棋盘进行上下左右padding0扩展（由于有可能出现第一行出现五个连续棋子的情况，所有必须要扩展边界。） 对逐个元素卷积判定。记录统计所有五子棋的情况个数。

代码不是很复杂，直接贴上来好了 五子棋