求助一个编程技术问题的思路,大数范围内的五子棋

查看 86|回复 4
作者:wasd6267016   
比如想判断一个二维五子棋棋盘上是不是有某一方获胜了(五子连珠)
如果只是 100*100 的棋盘,就比较简单
但是突发奇想,如果棋盘特别特别大,比如是长宽都是 int 范围内的,该如何站在技术的角度解决这个问题
我第一反应想到的是肯定不能全量储存,只需要存储有棋子的那部分,
用四叉树的结构去划分整个 int * int 的空间 ,逐层分割下去,到最后每个“小棋盘”比如大约是 50*50 的范围
然后对于任何一个很大的坐标( x ,y) 都可以按层级一级一级塞到这个四叉树里面去,直到去放到对应的 50*50 的小棋盘里去,没有棋子的小棋盘位置都不需要真正的创建空间;
同时还要有个辅助的数据结构( map )去记录当前所有的棋子,不然遍历棋子都没得遍历
对于给定的某个棋子( x ,y ),可以找到它所在的 50*50 的“小棋盘”,如果它不在边界上,那直接判断这个小棋盘内是否有人获胜就行;如果在边界上,就要去读取附近边界的棋子信息;
↑整体思路是这样的
空间复杂度最坏情况下可能是 棋子个数 N 的 2500 倍( 50*50 )
时间复杂度可能是 棋子个数 N * 附近范围的两个棋盘 大约是 5000N
这是我目前想到的思路,抛砖引玉,各位大佬有什么建议吗~

棋盘, 棋子, int, 四叉树

linauror   
感觉是不是直接判断当前落子的这个位置的 8 个方向上,是不是有连续 5 个子就可以了,这样是不是简单点。棋盘再大无所谓,因为扫描范围很小,就在 8 个方向的 5 个长度范围内
XiLingHost   
为啥不能全量存储,每 2bit 可以存储一个棋盘位置,00 未落子 01 黑 10 白 11 保留,然后就是个遍历查找子串的过程了,这个子串查找可以大量剪枝优化
实际上合法的五子连珠只有 4 类,连续的 5 个同类落子,连续 5 个间隔为棋盘宽度的同类落子,未跨过棋盘宽度整数倍情况下的间隔为棋盘宽度每次-1 和+1 的连续 5 个同类落子
coderluan   
我选择放弃棋盘遍历棋子,O(N^2),而且代码可以用 chatgpt 写。
linauror   
存储方面可以使用数据,一个点位算一个索引,值为 0 代表空,1 代表白子,2 代表黑子。当落子的时候,应该会知道当前的索引,然后写一个方法去获取 8 个方向的索引的值,来判断是否跟落子属性一致,直到连续 5 个同样的,即为胜利。为胜出的情况下,就是将当前索引写入一个值。不过这个数组可能会比较大,跟棋盘大小有关,但处理速度应该还是很快的
您需要登录后才可以回帖 登录 | 立即注册

返回顶部