0794-有效的井字游戏

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

给你一个字符串数组 board 表示井字游戏的棋盘。当且仅当在井字游戏过程中，棋盘有可能达到 board 所显示的状态时，才返回 true 。

井字游戏的棋盘是一个 3 x 3 数组，由字符 ' '，'X' 和 'O' 组成。字符 ' ' 代表一个空位。

以下是井字游戏的规则：

  • 玩家轮流将字符放入空位（' '）中。
  • 玩家 1 总是放字符 'X' ，而玩家 2 总是放字符 'O' 。
  • 'X' 和 'O' 只允许放置在空位中，不允许对已放有字符的位置进行填充。
  • 当有 3 个相同（且非空）的字符填充任何行、列或对角线时，游戏结束。
  • 当所有位置非空时，也算为游戏结束。
  • 如果游戏结束，玩家不允许再放置字符。

示例 1：

**输入：** board = ["O  ","   ","   "]
**输出：** false
**解释：** 玩家 1 总是放字符 "X" 。

示例 2：

**输入：** board = ["XOX"," X ","   "]
**输出：** false
**解释：** 玩家应该轮流放字符。

示例 3:

**输入：** board = ["XOX","O O","XOX"]
**输出：** true

提示：

  • board.length == 3
  • board[i].length == 3
  • board[i][j] 为 'X'、'O' 或 ' '

方法一：分类讨论

思路

题目要求判断当前游戏板是否生效，我们思考游戏板生效的规则：

  • 玩家轮流将字符放入空位 “ “ 中。第一个玩家总是放字符 “X”，且第二个玩家总是放字符 “O”。因为第一个玩家总是先手，这就要求游戏板中字符 “X” 的数量一定是大于等于字符 “O” 的数量。
  • “X” 和 “O” 只允许放置在空位中，不允许对已放有字符的位置进行填充。
  • 当有 3 个相同（且非空）的字符填充任何行、列或对角线时，游戏结束。当所有位置非空时，也算为游戏结束。如果游戏结束，玩家不允许再放置字符，不可能能出现二者同时获胜的情况，因此游戏板上不可能同时出现 3 个 “X” 在一行和 3 个 “O” 在另一行。
  • 获胜的玩家一定是在自己放棋后赢得比赛，赢得比赛后，立马停止放置字符。
    • 如果第一个玩家获胜，由于第一个玩家是先手，则次数游戏板中 “X” 的数量比 “O” 的数量多 1。
    • 如果第二个玩家获胜，则 “X” 的数量与 “O” 的数量相同。

以上条件包含了游戏板生效的全部情况，可以通过反证法验证上面分类条件的正确性。在合法的游戏板，只能有 3 种结果合法，要么没有任何玩家赢，要么玩家一赢，要么玩家二赢。我们可以通过检查两种棋的数量关系即可验证是否有效，同时我们要检测是否存在两个玩家同时赢这种非法情况。

算法实现细节如下:

  • 首先统计游戏板上 “X” 和 “O” 的数量并记录在 xCount 和 oCount 中，如果不满足 xCount} \ge \textit{oCount，则此时为非法，直接返回 false。
  • 然后我们检查是否有玩家是否获胜，我们检查在棋盘的 3 行，3 列和 2 条对角线上是否有该玩家的连续 3 枚棋子。我们首先检测玩家一是否获胜，如果玩家一获胜,则检查 xCount 是否等于 oCount} + 1；我们继续检测玩家二是否获胜，如果玩家二获胜，则检查 xCount 是否等于 oCount。
  • 对于特殊情况如果两个玩家都获胜，是否可以检测出该非法情况？如果同时满足两个玩家都获胜，则 “X” 和 “O” 数量的合法的组合可能为 (3,3),(4,3),(4,4),(5,4)，对于 (3,3),(4,4) 不满足玩家一获胜的检测条件，对于 (4,3),(5,4) 满足玩家一获胜的检测条件但不满足玩家二的获胜条件。

代码

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean validTicTacToe(String[] board) {
        int xCount = 0, oCount = 0;
        for (String row : board) {
            for (char c : row.toCharArray()) {
                xCount = (c == 'X') ? (xCount + 1) : xCount;
                oCount = (c == 'O') ? (oCount + 1) : oCount;
            }
        }
        return !((oCount != xCount && oCount != xCount - 1) ||
               (oCount != xCount - 1 && win(board, 'X')) ||
               (oCount != xCount && win(board, 'O')));
    }

    public boolean win(String[] board, char p) {
        for (int i = 0; i < 3; ++i) {
            if ((p == board[0].charAt(i) && p == board[1].charAt(i) && p == board[2].charAt(i)) ||
               (p == board[i].charAt(0) && p == board[i].charAt(1) && p == board[i].charAt(2))) {
                return true;
            }
        }
        return ((p == board[0].charAt(0) && p == board[1].charAt(1) && p == board[2].charAt(2)) ||
                (p == board[0].charAt(2) && p == board[1].charAt(1) && p == board[2].charAt(0)));
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool validTicTacToe(vector<string>& board) {
        int xCount = 0, oCount = 0;
        for (string & row : board) {
            for (char c : row) {
                xCount = (c == 'X') ? (xCount + 1) : xCount;
                oCount = (c == 'O') ? (oCount + 1) : oCount;
            }
        }
        return !((oCount != xCount && oCount != xCount - 1) ||
               (oCount != xCount - 1 && win(board, 'X')) ||
               (oCount != xCount && win(board, 'O')));
    }

    bool win(vector<string>& board, char p) {
        for (int i = 0; i < 3; ++i) {
            if ((p == board[0][i] && p == board[1][i] && p == board[2][i]) ||
               (p == board[i][0] && p == board[i][1] && p == board[i][2])) {
                return true;
            }
        }
        return ((p == board[0][0] && p == board[1][1] && p == board[2][2]) ||
                (p == board[0][2] && p == board[1][1] && p == board[2][0]));
    }
};
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public bool ValidTicTacToe(string[] board) {
        int xCount = 0, oCount = 0;
        foreach (string row in board) {
            foreach (char c in row) {
                xCount = (c == 'X') ? (xCount + 1) : xCount;
                oCount = (c == 'O') ? (oCount + 1) : oCount;
            }
        }
        return !((oCount != xCount && oCount != xCount - 1) ||
               (oCount != xCount - 1 && win(board, 'X')) ||
               (oCount != xCount && win(board, 'O')));
    }

    public bool win(string[] board, char p) {
        for (int i = 0; i < 3; ++i) {
            if ((p == board[0][i] && p == board[1][i] && p == board[2][i]) ||
               (p == board[i][0] && p == board[i][1] && p == board[i][2])) {
                return true;
            }
        }
        return ((p == board[0][0] && p == board[1][1] && p == board[2][2]) ||
                (p == board[0][2] && p == board[1][1] && p == board[2][0]));
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def win(self, board: List[str], p: str) -> bool:
        return any(board[i][0] == p and board[i][1] == p and board[i][2] == p or
                   board[0][i] == p and board[1][i] == p and board[2][i] == p for i in range(3)) or \
                   board[0][0] == p and board[1][1] == p and board[2][2] == p or \
                   board[0][2] == p and board[1][1] == p and board[2][0] == p

    def validTicTacToe(self, board: List[str]) -> bool:
        oCount = sum(row.count('O') for row in board)
        xCount = sum(row.count('X') for row in board)
        return not (oCount != xCount and oCount != xCount - 1 or
                    oCount != xCount and self.win(board, 'O') or
                    oCount != xCount - 1 and self.win(board, 'X'))
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func win(board []string, p byte) bool {
    for i := 0; i < 3; i++ {
        if board[i][0] == p && board[i][1] == p && board[i][2] == p ||
            board[0][i] == p && board[1][i] == p && board[2][i] == p {
            return true
        }
    }
    return board[0][0] == p && board[1][1] == p && board[2][2] == p ||
        board[0][2] == p && board[1][1] == p && board[2][0] == p
}

func validTicTacToe(board []string) bool {
    oCount, xCount := 0, 0
    for _, row := range board {
        oCount += strings.Count(row, "O")
        xCount += strings.Count(row, "X")
    }
    return !(oCount != xCount && oCount != xCount-1 ||
        oCount != xCount && win(board, 'O') ||
        oCount != xCount-1 && win(board, 'X'))
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var validTicTacToe = function(board) {
    let xCount = 0, oCount = 0;
    for (const row of board) {
        for (const c of row) {
            xCount = (c === 'X') ? (xCount + 1) : xCount;
            oCount = (c === 'O') ? (oCount + 1) : oCount;
        }
    }
    return !((oCount != xCount && oCount != xCount - 1) ||
               (oCount != xCount - 1 && win(board, 'X')) ||
               (oCount != xCount && win(board, 'O')));
};

const win = (board, p) => {
    for (let i = 0; i < 3; ++i) {
        if ((p == board[0][i] && p == board[1][i] && p == board[2][i]) ||
            (p == board[i][0] && p == board[i][1] && p == board[i][2])) {
            return true;
        }
    }
    return ((p == board[0][0] && p == board[1][1] && p == board[2][2]) ||
            (p == board[0][2] && p == board[1][1] && p == board[2][0]));
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool win(const char ** board, char p) {
    for (int i = 0; i < 3; ++i) {
        if ((p == board[0][i] && p == board[1][i] && p == board[2][i]) ||
            (p == board[i][0] && p == board[i][1] && p == board[i][2])) {
            return true;
        }
    }
    return ((p == board[0][0] && p == board[1][1] && p == board[2][2]) ||
            (p == board[0][2] && p == board[1][1] && p == board[2][0]));
}

bool validTicTacToe(char ** board, int boardSize){
    int xCount = 0, oCount = 0;
    for (int i = 0; i < boardSize; ++i) {
        for (int j = 0; j < 3; ++j) {
            xCount = (board[i][j] == 'X') ? (xCount + 1) : xCount;
            oCount = (board[i][j] == 'O') ? (oCount + 1) : oCount;
        }
    }
    return !((oCount != xCount && oCount != xCount - 1) ||
            (oCount != xCount - 1 && win(board, 'X')) ||
            (oCount != xCount && win(board, 'O')));
}

复杂度分析

  • 时间复杂度：O(C)，由于此题给定的棋盘大小为常数 C = 9，因此时间复杂度为常数。

  • 空间复杂度：O(1)。

 Comments
On this page
0794-有效的井字游戏