2 janehiwang Janehiwang 于 2016.04.30 16:07 提问

不从最后一个棋子出发,有什么可以判断五子棋棋局是否有赢棋的简单方法?

不从最后一个棋子出发,有什么可以判断五子棋棋局是否有赢棋的简单方法?

1个回答

leilba
leilba   Rxr 2016.04.30 23:54
已采纳

使用暴力搜索吧,不外乎横、竖、左右斜对角这四种情况,我在纯暴力O(n3)的基础上做了一步优化,给你一种O(n2)的解法,希望能帮到你

 #include "iostream"
using namespace std;
//假设棋盘宽为100
#define WIDTH   100
//高为100
#define HEIGHT  100

//棋盘,没有落子的地方是0,,黑子是1,白子是2
int keyMap[HEIGHT][WIDTH] = {0};

// 向右下角搜索
int rightBottomDetect(int tempI, int tempJ);
// 向左下角搜索
int leftBottomDetect(int tempI, int tempJ);

int main(){

    //测试数据
    for (int i=0; i<5; i++) {
        keyMap[8+i][23+i]=2;
    }


    int isWin = 0;
    // 水平方向是否是五子
    for(int i = 0; i < HEIGHT && !isWin; i++) {
        int stap = 1;
        for(int j = 1; j < WIDTH; j++) {
            if(keyMap[i][j] && keyMap[i][j] == keyMap[i][j-1]) {
                stap ++;
                if(stap >= 5) {
                    isWin = keyMap[i][j];
                    break;
                }
            }
        }
    }

    // 竖直方向是否是五子
    for(int j = 0; j < WIDTH && !isWin; j++) {
        int stap = 1;
        for(int i = 1; i < HEIGHT; i++) {
            if(keyMap[i][j] && keyMap[i][j] == keyMap[i-1][j]) {
                stap ++;
                if(stap >= 5) {
                    isWin = keyMap[i][j];
                    break;
                }
            }
        }
    }

    // 右下斜对角 part1
    for (int j = 0; j < WIDTH && !isWin; j++) {
        isWin = rightBottomDetect(1, j+1);

    }
    // 右下斜对角 part2
    for (int i = 0; i < HEIGHT && !isWin; i++) {
        isWin = rightBottomDetect(i+1, 1);
    }

    // 左下斜对角 part1
    for (int j = 0; j < WIDTH && !isWin; j++) {
        isWin = leftBottomDetect(1, j-1);
    }
    // 左下斜对角 part2
    for (int i = 0; i < HEIGHT && !isWin; i++) {
        isWin = rightBottomDetect(i+1, WIDTH - 2);
    }

    if (isWin) {
        cout<<"赢棋的是:";
        if (isWin == 1) {
            cout<<"黑子"<<endl;
        }
        else {
            cout<<"白子"<<endl;
        }
    } else {
        cout<<"尚未有人赢得棋局"<<endl;
    }

    return 0;
}

// 向右下角搜索
int rightBottomDetect(int tempI, int tempJ) {
    int isWin = 0;
    int stap = 1;
    while (tempJ < WIDTH && tempI < HEIGHT) {
        if (keyMap[tempI][tempJ] && keyMap[tempI][tempJ] == keyMap[tempI - 1][tempJ - 1]) {
            stap ++;
            if (stap >= 5) {
                isWin = keyMap[tempI][tempJ];
                break;
            }
        }
        tempI ++;
        tempJ ++;
    }
    return isWin;
}

// 向左下角搜索
int leftBottomDetect(int tempI, int tempJ) {
    int isWin = 0;
    int stap = 1;
    while (tempJ >= 0 && tempI < HEIGHT) {
        if (keyMap[tempI][tempJ] && keyMap[tempI][tempJ] == keyMap[tempI - 1][tempJ + 1]) {
            stap ++;
            if (stap >= 5) {
                isWin = keyMap[tempI][tempJ];
                break;
            }
        }
        tempI ++;
        tempJ --;
    }
    return isWin;
}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
五子棋危险判断 - 图与连线
这题其实不难,但是纪念一下头一次"信仰提交成功"2333 【问题描述】 已知两人分别执白棋和黑棋在一个围棋棋盘上下五子棋,若同一颜色的棋子在同一条横行、纵行或斜线上连成5个棋子,则执该颜色棋子的人获胜。编写程序读入某一时刻下棋的状态,并判断是否有人即将获胜,即:同一颜色的棋子在同一条横行、纵列或斜线上连成4个棋子,且该4个棋子的两端至少有一端为空位置。 输入的棋盘大小是19×19,用
Java实现一个简单的两人五子棋游戏(五) 判断是否有一方胜出
1)选择棋子 ✔️ 2)画棋子 ✔️ 3)判断胜负 目标 4)交换行棋方 目标 前面我们已经画好了棋盘、棋子并且可以自由的落子了,那么接下来要实现的功能是判断是否有五连珠(暂时不考虑行棋方)。 新增一个isWin()函数
我制作的一个简易五子棋,不懂来问…
简易五子棋的详细制作 摘要:    五子棋是我们日常经常玩的游戏,带给我们无无穷的乐趣。本文将详细的介绍简易五子棋的制作过程,五子棋虽然玩着简单,但要是制作的完美也需要很多耐心和技巧。 关键字 五子棋 制作 1 基本论述    首先要说明一下,本五子棋设计除了计算机下子部分是参考了有关文献后,其余全部是自己独立完成,详细源代码可见附录。  编写五子棋程序,在设计的初期,应该思考这样几个问题
Java实现一个简单的两人五子棋游戏(三) 画棋子
前面我们已经画好的棋盘,现在来实现控制模块,主要功能: 交换行棋方 选择棋子 画棋子 判断胜负
人机五子棋实现原理
人机五子棋 近期整理代码的时候,发现大二的时候(目前大三)做的几个课程设计还不错,所以把这部分的代码以及设计文档都开源出来,以供后者参考学习使用。 完整代码以及本文的word都在放在了Github上,你可以下载或使用它:人机五子棋项目地址,如果喜欢的话,就去点个Star吧 具体效果如下图,我是黑方(先手),机器是白方,本局机器胜。 从图中大概可以看出,它已经具备了一点点的智能,...
人输入坐标玩五子棋(与电脑对抗)
人输入坐标,与电脑对抗(电脑是随机下子的,没实现人工智能)代码如下:#include &amp;lt;iostream&amp;gt; //设置随机数的头文件 #include &amp;lt;cstdlib&amp;gt; #include &amp;lt;ctime&amp;gt; using namespace std; const int length = 7; //全局变量,棋盘的长与宽,可调整 int function(cha...
JAVA 五子棋 判断输赢的代码实现
//定义棋盘大小,宽w,高h int w = 11; int h = w; //用一个二维数组保存棋盘数据,1代表红棋,2代表黑棋 int[][] chess = new int[h][w]; //定义控制循环的布尔变量 boolean game_over = false; boolean win_red = false; boolean win_black = false;
codevs1004 四字连棋 BFS
1004 四子连棋  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 在一个4*4的棋盘上摆放了14颗棋子,其中有7颗白色棋子,7颗黑色棋子,有两个空白地带,任何一颗黑白棋子都可以向上下左右四个
java五子棋判断输赢算法
用一个二维数组先将棋盘存储,已下的白棋标为1,已下的黑棋标为2,未下的棋全部为0。 此时,先来判断横向输赢,即当横向有五个1或五个2连在一起即判断为赢 先向右寻找 //棋子数从一开始 int count=1; while(true)   {    x1= x1+1;    int value = chess[x1][y1];    //如果相同,则继续向后对比    if(va
1004 四子连棋(思路重要)
1004 四子连棋 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 在一个4*4的棋盘上摆放了14颗棋子,其中有7颗白色棋子,7颗黑色棋子,有两个空白地带, 任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格,这叫行棋一步,黑 白双方交替走棋,任意一方可以先走,如果某个时刻使得任意一种颜色的棋子形成四个一线(包括斜