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

Question

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

Answer 1

使用暴力搜索吧，不外乎横、竖、左右斜对角这四种情况，我在纯暴力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;
}