Janehiwang
Janehiwang
2016-04-30 08:07
采纳率: 40%
浏览 1.9k
已采纳

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

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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • leilba
    林深 2016-04-30 15: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;
    }
    
    
    点赞 评论

相关推荐