首页 > 其他分享 >一个循环实现五子棋输赢判定 gobang

一个循环实现五子棋输赢判定 gobang

时间:2022-12-18 20:45:11浏览次数:44  
标签:count gobang smallPointList return continueCount 复杂度 五子棋 输赢 14

通过一个for循环实现五子棋输赢判定

看过好些人写的判定方法,发现基本都是使用三层for来遍历实现的虽然时间复杂度不是N^3但是如下算法时间复杂度仅仅是N
经过分析,时间复杂度的原因来自(x + i, y) in smallPointList->O(N)但是for i in range(-4, 5)的时间复杂度为O(1)但是可以看到的是,我们使用的空间复杂度也是O(1)已经是最低,如果要将时间复杂度降低的话,我们需要提高空间复杂度,可以考虑将smallPointList存为一个矩阵(15x15),每个矩阵的值是一个二维数组,此时虽然空间复杂度提高了一点,但是仍然不是O(N),因此在如果计算量很高的的情况下可以适当提高空间复杂度

总结如下代码时间复杂度为O(N)空间复杂度为O(1)
只要我们将判定点是否在list这段代码对应的list(x + i, y) in smallPointList改为一个二维数组数据里面存point就可以实现时间复杂度O(1),空间复杂度O(1),占用内存略微提高

def haveFive():
    # 刚下完棋的x点坐标
    x = 10
    y = 4
    # 当前需要判定的所有白子或者是黑子的坐标集合
    smallPointList = [(10, 4), (11, 3), (9, 4), (11, 4), (8, 4), (7, 4), (12, 4), (6, 0)]
    # - | / \ 四个方向
    count = [1, 1, 1, 1]
    for i in range(-4, 5):
        continueCount = 0
        # 表示超出边界
        # -
        if x + i < 0 or x + i > 14 or i == 0:
            continueCount += 1
        # |
        if y + i < 0 or y + i > 14 or i == 0:
            continueCount += 1
        # /
        if x + i < 0 or x + i > 14 or y - i < 0 or y - i > 14 or i == 0:
            continueCount += 1
        # \
        if x + i < 0 or x + i > 14 or y + i < 0 or y + i > 14 or i == 0:
            continueCount += 1

        if continueCount == 4:
            # continueCount == 1
            continue
        # 没有超出边界
        else:
            # -
            if (x + i, y) in smallPointList:
                count[0] = count[0] + 1
                if count[0] == 5:
                    print("true  - ")
                    return True
            else:
                count[0] = 1

            # |
            if (x, y + i) in smallPointList:
                count[1] = count[1] + 1
                if count[1] == 5:
                    print("true  | ")
                    return True
            else:
                count[1] = 1
            # /
            if (x + i, y - i) in smallPointList:
                count[2] = count[2] + 1
                if count[2] == 5:
                    print("true  / ")
                    return True
            else:
                count[2] = 1
            # \
            if (x + i, y + i) in smallPointList:
                count[3] = count[3] + 1
                if count[3] == 5:
                    print("true  \\ ")
                    return True
            else:
                count[3] = 1
    return False

标签:count,gobang,smallPointList,return,continueCount,复杂度,五子棋,输赢,14
From: https://www.cnblogs.com/sqmw/p/16990887.html

相关文章

  • 217行javascript代码实现五子棋游戏
    html<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metahttp-equiv="X-UA-Compatible"content="IE=edge"><metaname="viewport"c......
  • 极大极小值算法应用于五子棋
    原文链接​​MinimaxforGomoku(ConnectFive)​​--作者​​OfekGila​​回顾不知道你是否还记得​​上一篇文章​​,我们使用深度优先搜索算法来解决井字棋游戏,递归......
  • 再读《悟透javascript》之五、五子棋
    前言     五子棋是个很有趣的游戏,在用javascript开发之后,我发现其实ai算法才是最难的,这里的ai算法是直接借鉴自其它的ai算法。  代码如下:<htmlxmlns="http://www.w3......
  • 井字棋判断输赢C
    #include<stdio.h>intmain(){chara[3][3];for(inti=0;i<3;++i){for(intj=0;j<3;++j){scanf("%c",&a[i][j]);......
  • 弈悟计划——大一C程期末实验之五子棋AI的开发日志
    写在前面大一C程的期末作业,因为觉得从头学C太没意思,因此报了学校的什么挑战班(早知道不换了去混绩点了)由于本人懒得要死,刚开始想手搓GUI,然后看了各种图形界面感觉徒增烦恼......
  • 输赢只是一时
    不同的年纪看同一本书,关注点不同,感悟也不相同。2004年的夏天,我在旧书摊买了一本《长安乱》,那个时候的我还不认识韩寒,也不懂人生的痛苦和沉浮。只是把这本书当作某个下午悠......
  • 网络五子棋游戏
    题目:网络五子棋游戏项目要求运行截图程序代码下载下载链接......
  • C语言简单五子棋两人/五子棋人机
           对于初学C语言的同学,五子棋不可谓不是一个好的练习。我们不但要考虑玩家及电脑的落子,还要考虑棋盘是否已满、是否有一方已经获得胜利。因此我们要考虑好各种......
  • linux实现 五子棋(人人对战)
    分步解析对于game函数的解析进入game函数中,通过创建一个二维数组来打印棋盘,进入dowhile循环中,策略是先打印出棋盘,然后先让用户1落子,进行判定,看是否需要继续,若需......
  • 五子棋AI
    瞎写的,传上来备份一下#pragmaGCCoptimize(3)#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<ctime>......