【Day_10 0428】井字棋

井字棋

题目来源

牛客网：井字棋

题目描述

给定一个二维数组board，代表棋盘，其中元素为1的代表是当前玩家的棋子，0表示没有棋子，-1代表是对方玩家的棋子。当一方棋子在横竖斜方向上有连成排的及获胜（及井字棋规则），返回当前玩家是否胜出。

示例

输入

[[1,0,1],[1,-1,-1],[1,-1,0]]

返回

true

思路分析

思路一

暴力求解

• 井字棋可以在横、竖、斜三个方向连成排，只要对三个方向进行遍历即可
• 对二维数组横向和纵向进行遍历，遇到非1即退出循环，因为如果有一个元素不是1，则本行（或列），将不能连成排
• 在循环结束时进行判断，如果此时循环控制变量的值已经不满足循环条件，说明循环是正常执行结束的，此行（或行）都为1；若此时循环控制变量仍满足循环条件，则说明循环是break退出的。
• 判断横向时数组一维的下标为常量，二维的下标为变量，如[0,0],[0,1],[0,2]；判断纵向时，一维的下标为变量，二维的下标为常量如[0,0][1,0][2,0]；二维数组与坐标点不同，二维数组中，x控制的是纵向的变化，y控制的是横向的变化，要注意区分。
  

思路二

计算元素和

• 基本原理相同，遍历二维数组，但是由于这里棋盘中当前玩家的棋子是用1表示，所以可以用加和的方式进行判断。
• 井字棋默认是正方形键盘，长宽相等，所以只需遍历一次即可

代码展示

解法一

class Board {
    
public:
    bool checkWon(vector<vector<int> > board) {
    
        int len = board.size();
        //横向
        for (int i = 0; i < len; i++)
        {
    
            if (board[i][0] == 1)
            {
    
                int j;
                for (j = 0; j < len; j++)
                {
    
                    if (board[i][j] == 0 || board[i][j] == -1)
                    {
    
                        break;
                    }
                }
                //循环结束时，如果j=len，说明没有break
                //for循环要自增到不满足循环条件为止，所以这里是len,而不是j==len-1
                //j==len-1时，循环内部程序执行结束后，会先对j进行自增，此时j==len
                //再判断循环条件不满足，此时循环结束
                if (j == len)
                {
    
                    return true;
                }
            }
        }

        //纵向
        for (int k = 0; k < len; k++)
        {
    
            if (board[0][k] == 1)
            {
    
                int l;
                for (l = 0; l < len; l++)
                {
    
                    if (board[l][k] == 0 || board[l][k] == -1)
                    {
    
                        break;
                    }
                }
                if (l == len)
                {
    
                    return true;
                }
            }
        }
        //对角线
        int m = 0;
        int n = 0;
        for (m = 0; m < len; m++)
        {
    
            if (board[m][n] == 0 || board[m][n] == -1)
            {
    
                break;
            }
            //for括号中已经对m进行了自增，此处只要对n自增即可
            //m++
            n++;
        }
        if (m == len)
        {
    
            return true;
        }

        //反斜线
        int r = len;
        int s = 0;
        for (r = len - 1; r >= 0; r--)
        {
    
            if (board[r][s] == 0 || board[r][s] == -1)
            {
    
                break;
            }
            s++;
        }
        if (r == -1)
        {
    
            return true;
        }
        return false;
    }
};

解法二

class Board {
    
public:
    bool checkWon(vector<vector<int> > board) {
    
        //井字棋长宽相同
        int sz = board.size();
        int sum_row, sum_col, sum_l, sum_r;
       
        for (int i = 0; i < sz; i++)
        {
    
            for (int j = 0; j < sz; j++)
            {
    
                //因为长宽相同，所以可以用这种方法同时求行和列的和,只需一次遍历
                sum_row += board[i][j];
                sum_col += board[j][i];
            }
            //每行（列）遍历结束都进行判断
            if (sum_row == sz || sum_col == sz) {
    
                return true;
            }
            //左上对角线
            sum_l += board[i][i];
            //右上对角线
            sum_r += board[i][sz - 1 - i];
        }
        if (sum_l == sz || sum_r == sz) {
    
            return true;
        }
        return false;
    }
};