首页 > 试题广场 >

井字棋

[编程题]井字棋
  • 热度指数:9212 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

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

测试样例:
[[1,0,1],[1,-1,-1],[1,-1,0]]
返回:true

Python 比较暴力的一行

# -*- coding:utf-8 -*-

class Board:
def checkWon(self, board):
return [1, 1, 1] in board or (1, 1, 1) in zip(*board) or [1, 1, 1] == [board[i][i] for i in range(3)] or [1, 1, 1] == [board[i][2-i] for i in range(3)]
编辑于 2018-12-26 18:56:21 回复(0)
import java.util.*;
/*
思路:我觉得笨办法好像也慢不了多少,就逐行逐列检测即可
当然我这个心态不可取,不过好像大家都是这个办法
*/
public class Board {
    public boolean checkWon(int[][] board) {
        for(int i=0;i<3;i++){   
            if(board[i][0]+board[i][1]+board[i][2]==3) return true;
        }
        for(int i=0;i<3;i++){   
            if(board[0][i]+board[1][i]+board[2][i]==3) return true;
        }
        if(board[0][0]+board[1][1]+board[2][2]==3) return true;
        if(board[0][2]+board[1][1]+board[2][0]==3) return true;
        return false;
    }
}
运行时间:26ms
占用内存:8388k

发表于 2017-07-05 17:39:14 回复(2)
class Board:
    def checkWon(self, board):
        t = 0
        for i in range(3):
            for j in range(3):
                t |= (board[i][j] == 1) << i * 3 + j  # 转换为二进制流
        for x in Board.winNum:
            if t & x in Board.winNum:
                return True
        return False

    winNum = set([448, 292, 7, 73, 273, 146, 84, 56])  # 打表

# A = [i for i in range(9)]
# s = set()
# for i in range(3):
#     a, b = 0, 0
#     for j in range(3):
#         a += 2 ** A[i * 3 + j]
#         b += 2 ** A[j * 3 + i]
#     s.add(a)
#     s.add(b)
# a = b = 0
# for i in range(3):
#     a += 2 ** A[i * 3 + i]
#     b += 2 ** A[i * 3 + 2 - i]
# s.add(a)
# s.add(b)
# print s
编辑于 2017-03-05 20:47:06 回复(0)
class Board {
public:
	bool checkWon(vector<vector<int>> board) {

		//鲁棒性检查
		int row = 0, col = 0, len = board.size();
		if (len <= 2) return false;
		for (row = 0; row < len; row++)
		{
			if (board.size() != len)
				return false;
		}

		//检查行
		for (row = 0; row < len; row++)
		{
			col = 0;
			if (board[row][0] == 1 && board[row][len - 1] == 1)
			{
				for (col = 1; col < len; col++)
				{
					if (board[row][col] != 1)
						break;
				}
			}
			if (col == len)
				return true;
		}

		//检查列
		for (col = 0; col < len; col++)
		{
			row = 0;
			if (board[0][col] == 1 && board[len - 1][col] == 1)
			{
				for (row = 1; row < len; row++)
				{
					if (board[row][col] != 1)
						break;
				}
			}
			if (row == len)
				return true;
		}

		//检查主对角线
		if (board[0][0] == 1 && board[len - 1][len - 1] == 1)
		{
			for (row = 0; row < len; row++)
			{
				if (board[row][row] != 1)
					break;
			}
			if (row == len)
				return true;
		}


		//检查逆对角线
		if (board[0][len - 1] == 1 && board[len - 1][0] == 1)
		{
			for (row = 0; row < len; row++)
			{
				if (board[row][len - 1 - row] != 1)
					break;
			}
			if (row == len)
				return true;
		}

		return false;
	}
};
扩展为N阶的
编辑于 2015-09-04 17:21:55 回复(1)
//直接统计1和-1的个数,比较即可
import java.util.*;
public class Board {
    public boolean checkWon(int[][] board) {
        int m = 0;
        int n = 0;
        for(int i = 0;i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                if(board[i][j] == 1)
                    m++;
                else if(board[i][j] == -1)
                    n++;
            }
        }
        return m > n;
    }
}

发表于 2017-05-11 16:39:01 回复(0)
class Board {
public:
    bool checkWon(vector<vector<int> > board) {
        int a[9]={0},k=0;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
            a[k]+=board[i][j];
            a[k+1]+=board[j][i];
            }
             k+=2;
            a[7]+=board[i][i];
            a[8]+=board[i][2-i];
        }
        int flag=0;
        for(int i=0;i<9;i++){
            if(a[i]==3){
                   flag=1;break;
            }
             
        }
        if(flag)
            return true;
        return false;
    }
};

发表于 2017-10-10 11:12:15 回复(1)
只考虑是的几种情况,最多需要11次判断,已经最简化了吧
class Board {
public:
    bool checkWon(vector<vector<int> > board) {
        // write code here
        if(board[1][1]==1){
            if((board[0][0]==1 && board[2][2]==1)||(board[2][0]==1 &&board[0][2]==1))
                return true;
        }else{
            if(board[0][0]==1){
                if((board[0][1]==1 && board[0][2]==1)||(board[1][0]==1 && board[2][0]==1))
                    return true;
            }
            if(board[2][2]==1){
                if((board[2][1]==1 && board[2][0]==1)||(board[1][2]==1 && board[1][0]==1))
                    return true;
            } 
        }
        return false;
    }
};
发表于 2015-09-08 17:34:40 回复(0)
L0L头像 L0L
//3竖3横两条斜线
 bool checkWon(vector<vector<int> > a) {
       if(a[0][0]+a[1][1]+a[2][2]==3) return true;
       if(a[0][2]+a[1][1]+a[2][0]==3) return true;
       for(int i=0;i<3;i++){
       	    if(a[i][0]+a[i][1]+a[i][2]==3) return true;
       	    if(a[0][i]+a[1][i]+a[2][i]==3) return true;
	   }
	   return false;
    }

编辑于 2015-10-14 17:15:51 回复(9)
//扩展到N阶的棋盘同样适用;
class Board {
public:
    bool checkWon(vector<vector<int> > board) {
        // write code here
        int len=board.size();
        //检查行
        for(int i=0;i<len;i++)
        {
            int sum=0;
            for(int j=0;j<len;j++)
                sum+=board[i][j];
            if(sum==len)
                return true;
        }
        //检查列
        for(int i=0;i<len;i++)
        {
            int sum=0;
            for(int j=0;j<len;j++)
                sum+=board[j][i];
            if(sum==len)
                return true;
        }
        //检查主对角线
        int temp=0;
        for(int i=0;i<len;i++)
        {
            temp+=board[i][i];
        }
        if(temp==len) return true;
        
        //检查副对角线
        temp=0;
        for(int i=0;i<len;i++)
        {
            temp+=board[i][len-i-1];
        }
        if(temp==len) return true;
        
        return false;
    }
};

发表于 2016-08-18 22:48:39 回复(0)
import java.util.*;

public class Board {
    public boolean checkWon(int[][] board) {
        int arr[]=new int[3];
        int i0=0;
        int i2=2;
        
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                arr[board[i][j]+1]++;
            }
        }
        return arr[i2]>arr[i0]?true:false;
    }
}

发表于 2017-06-26 22:06:36 回复(0)

python 一行解法

    def checkWon(self, board):
        return sum(map(lambda c:c.count(1),board))>sum(map(lambda c:c.count(-1),board))
发表于 2017-10-31 18:18:56 回复(2)
bool checkWon(vector<vector<int>> board) {
    for(int i = 0; i < 3; ++i){
        if(board[i][0] + board[i][1] + board[i][2] == 3 ||
           board[0][i] + board[1][i] + board[2][i] == 3){//3行3列
            return true;
        }
    }
    if(board[0][0] + board[1][1] + board[2][2] == 3 ||
       board[0][2] + board[1][1] + board[2][0] == 3){//对角线
        return true;
    }
    return false;
}
另一种相对复杂的解法
class Board {
public:
    bool checkWon(vector<vector<int>> board) {
        int N = board.size();
        int sum = 0;
        for(int i = 0; i < N; ++i){
            sum = 0;
            for(int j = 0; j < N; ++j){
                sum += board[i][j];
            }
            if(sum == N){
                return true;
            }
        }
        for(int i = 0; i < N; ++i){
            sum = 0;
            for(int j = 0; j < N; ++j){
                sum += board[j][i];
            }
            if(sum == N){
                return true;
            }
        }
        sum = 0;
        for(int i = 0; i < N; ++i){
            sum += board[i][i];
        }
        if(sum == N){
            return true;
        }
        sum = 0;
        for(int i = 0; i < N; ++i){
            sum += board[i][N - i - 1];
        }
        if(sum == N){
            return true;
        }
        return false;
    }
};


编辑于 2020-06-05 15:25:50 回复(0)
//直接对井字方阵中的元素进行计算就行,如果结果大于0,说明胜利,小于零则失败
class Board {
public:
bool checkWon(vector<vector<int> > board) {
    // write code here
    int sum = 0;
    for(int i = 0; i < board.size(); i++)
    {
        for(int j = 0; j < board[0].size(); j++)
        {
            sum += board[i][j];
           }
        }
        if(sum > 0)
            return true;
        return false;
    }
};
编辑于 2017-01-25 18:22:05 回复(4)
class Board {
public:
    bool checkWon(vector<vector<int> > board) {
        if(board.size()==0 || board[0].size()==0)
            return false;
        int row=board.size(), col=board[0].size();
        for(int i=0;i<row;++i) {
            bool flag=true;
            for(int j=0;j<col;++j) { //判断该行是否连成排
                if(board[i][j]!=1) {
                    flag=false;
                    break;
                }
            }
            if(flag)
                return true;
        }
        for(int i=0;i<col;++i) {
            bool flag=true;
            for(int j=0;j<row;++j) {
                if(board[j][i]!=1) {
                    flag=false;
                    break;
                }
            }
            if(flag)
                return true;
        }
        int x=0,y=0;
        bool flag=true;
        while(x<row && y<col) { //对角线(左上到右下的)
            if(board[x][y]!=1) {
                flag=false;
                break;
            }
            ++x;
            ++y;
        }
        if(flag)
            return true;
        flag=true;
        x=0, y=col-1;
        while(x<row && y>=0) { //另一条对角线(右上到左下的)
            if(board[x][y]!=1) {
                flag=false;
                break;
            }
            ++x;
            --y;
        }
        return flag;
    }
};

发表于 2021-09-28 17:59:00 回复(0)
class Board {
public:
    bool checkWon(vector<vector<int> > b) {
        for(int i=0;i<3;i++) {
            int v1 = 0;
            int v2 = 0;
            for(int j=0;j<3;j++) {
                v1 += b[i][j];
                v2 += b[j][i];
            }
            if(v1==3 || v2==3)
                return true;
        }
        return b[0][0]+b[1][1]+b[2][2]==3 || b[0][2]+b[1][1]+b[2][0]==3;
    }
};

发表于 2020-07-20 22:52:35 回复(0)
import java.util.*;

public class Board {
    public boolean checkWon(int[][] board) {
      boolean a=false;
      if(board[0][0]+board[1][1]+board[2][2]==3||board[0][2]+board[1][1]+board[2][0]==3) a=true;
     for(int i=0;i<3;i++) {
         if(board[i][0]+board[i][1]+board[i][2]==3||board[0][i]+board[1][i]+board[2][i]==3) a=true;
     }
        return a;
    }
}
发表于 2019-03-03 13:01:53 回复(0)
class Board {
public:
    bool checkWon(vector<vector<int> > board) {
        // 所有胜局
        static const int win[] = {
            256+128+64, 32+16+8, 7,
            64+16+4, 256+16+1,
            256+32+4, 128+16+2, 64+8+1
        };
        
        // 将当前棋局映射为bit串
        int phrase = 0;
        for (int i = 0; i < board.size(); ++ i) {
            for (int j = 0; j < board[0].size(); ++ j) {
                phrase = (phrase << 1)| (board[i][j] == 1);
            }
        }
        
        return accumulate(win, win+8, 
                          false, [phrase](bool x, int y) {return x || (y == (y&phrase));});
    }
};
发表于 2016-08-27 12:21:16 回复(0)
写的是   不限棋盘大小  也可以自己定义连续几个就可以赢得比赛  的代码
import java.util.*;

public class Board {
   
    public boolean checkWon(int[][] board) {
        // write code here
        int last = 0;
        int count = 0;
        for(int i=0;i<board.length;i++){
            last = board[i][0];
            if(last!=0)
                count = 1;
            for(int j=1;j<board.length;j++){
                if(board[i][j]==0){
                    last = board[i][j];
                    count = 0;
                }else if(board[i][j]!=0){
                    if(board[i][j]==last){
                        last = board[i][j];
                        count++;
                        //这个地方if(count==5)就可以是五子棋了 if(count==board.length){
                            if(last==1){
                               return true; 
                            }else if(last==-1){
                               return false;
                            }
                              
                        }
                        if(j==(board.length-1)){
                            count=0;
                        }
                        
                    }else if(board[i][j]!=last){
                        last = board[i][j];
                        count = 1;
                    }
                }
            }
        }
        
         last = 0;
         count = 0;
        for(int i=0;i<board.length;i++){
            last = board[0][i];
            if(last!=0)
                count = 1;
            for(int j=1;j<board.length;j++){
                if(board[j][i]==0){
                    last = board[j][i];
                    count = 0;
                }else if(board[j][i]!=0){
                    if(board[j][i]==last){
                        last = board[j][i];
                        count++;
                        
                        if(count==board.length){
                             if(last==1){
                               return true; 
                            }else if(last==-1){
                               return false;
                            } 
                        }
                        if(j==(board.length-1)){
                            count=0;
                        }
                    }else if(board[j][i]!=last){
                        last = board[j][i];
                        count = 1;
                    }
                }
            }
        }
        
         last = 0;
         count = 0;
        for(int i=board.length-3;i>=0;i--){
            last = board[i][0];
            if(last!=0)
                count = 1;
            int row = i+1;
            for(int j=1;j<board.length;j++){
                if(row>=board.length)
                    continue;
                if(board[row][j]==0){
                    last = board[row][j];
                    count = 0;
                    row++;
                }else if(board[row][j]!=0){
                    if(board[row][j]==last){
                        last = board[row][j];
                        count++;
                        
                        if(count==board.length){
                             if(last==1){
                               return true; 
                            }else if(last==-1){
                               return false;
                            } 
                        }
                        if(row==(board.length-1)||j==(board.length-1)){
                            count=0;
                        }
                    }else if(board[row][j]!=last){
                        last = board[row][j];
                        count=1;
                    }
                    row++;
                }
                
            }
        }
        
       
         last = 0;
         count = 0;
         for(int i=1;i<board.length;i++){
            last = board[0][i];
             if(last!=0)
                 count = 1;
            int row = 1;
            for(int j=1;j<board.length;j++){
                if(row>=board.length)
                    continue;

                if(board[row][j]==0){
                    last = board[row][j];
                    count = 0;
                    row++;
                }else if(board[row][j]!=0){
                    if(board[row][j]==last){
                        last = board[row][j];
                        count++;
                        
                        if(count==board.length){
                             if(last==1){
                               return true; 
                            }else if(last==-1){
                               return false;
                            } 
                        }
                        if(row==(board.length-1)||j==(board.length-1)){
                            count=0;
                        }
                    }else if(board[row][j]!=last){
                        last = board[row][j];
                        count =1;
                    }
                    row++;
                }
                
            }
         }
        
        
         last = 0;
         count = 0;
        for(int i=2;i<board.length;i++){
            last = board[i][0];
            if(last!=0)
                count = 1;
            int row = i-1;
            for(int j=1;j<board.length;j++){
                if(row<0)
                    continue;
                if(board[row][j]==0){
                    last = board[row][j];
                    count = 0;
                    row--;
                }else if(board[row][j]!=0){
                    if(board[row][j]==last){
                        last = board[row][j];
                        count++;
                        
                        if(count==board.length){
                             if(last==1){
                               return true; 
                            }else if(last==-1){
                               return false;
                            } 
                        }
                        if(row==0||j==(board.length-1)){
                            count=0;
                        }
                    }else if(board[row][j]!=last){
                        last = board[row][j];
                        count = 1;
                    }
                    row--;
                }
            }
        }
        
        
         last = 0;
         count = 0;
         for(int i=1;i<board.length;i++){
            last = board[board.length-1][i];
             if(last!=0)
                 count = 1;
            int row = board.length-1-1;
            for(int j=2;j<board.length;j++){
                if(row<0)
                    continue;
                if(board[row][j]==0){
                    last = board[row][j];
                    count = 0;
                    row--;
                }else if(board[row][j]!=0){
                    if(board[row][j]==last){
                        last = board[row][j];
                        count++;
                        
                        if(count==board.length){
                             if(last==1){
                               return true; 
                            }else if(last==-1){
                               return false;
                            } 
                        }
                        if(row==0||j==(board.length-1)){
                            count=0;
                        }
                    }else if(board[row][j]!=last){
                        last = board[row][j];
                        count = 1;
                    }
                    row--;
                }
                
            }
         }
        return false;
    }
}

发表于 2016-06-30 17:44:35 回复(2)
井字棋就是3*3棋盘。
发表于 2015-08-20 15:23:28 回复(0)
题目思路
玩家棋子为1
整个一行相加结果为列数 就获胜了
整个一列相加结果为行数 就获胜了
正斜 board[row][row]
副斜board[row][col-1-i]
class Board {
public:
    bool checkWon(vector<vector<int> > board) {
        // write code here
        int row=board.size();
        int col=board[0].size();

        //行连成排
        for(int i=0;i<row;i++)
        {
            int sum=0;
            for(int j=0;j<col;j++)
            {
                sum+=board[i][j];
            }
            if(sum==row) return true;
        }
        //列连成排
        for(int i=0;i<col;i++)
        {
            int sum=0;
            for(int j=0;j<row;j++)
            {
                sum+=board[j][i];
            }
            if(sum==row) return true;
        }
        //正斜成排
        int sum=0;
        for(int i=0;i<row;i++)
        {
            sum+=board[i][i];
        }
        if(sum==row)  return true;
        //副斜成排
        sum=0;
        for(int i=0;i<row;i++)
        {
            sum+=board[i][col-1-i];
        }
        if(sum==row) return true;

        return false;
    }
};
发表于 2024-03-08 20:20:03 回复(0)