[ACM/算法]五子棋

问题:
image
image

解决方法:
此题尚未完全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扩展(由于有可能出现第一行出现五个连续棋子的情况,所有必须要扩展边界。)
对逐个元素卷积判定。记录统计所有五子棋的情况个数。

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