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