794. 有效的井字游戏(中等)

Posted on Edited on In Views:

1，问题描述

794. 有效的井字游戏

难度：中等

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

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

以下是井字游戏的规则：

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

示例 1：

img

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

示例 2：

img

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

示例 3:

img

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

提示：

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

2，初步思考

​ 使用模拟法，一步步去探测限制条件

3，代码处理

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import java.util.ArrayList;
import java.util.List;

public class _794有效的井字游戏 {

    // 检查有效性
    // 条件：
    // 1，x先填写
    // 2，轮流填写，cnt(x)=cnt(o) || cnt(x)+1=cnt(o)
    // 3，只能有一个人win，不能同时win
    // 4，o win后，两者的计数应该是一样的
    // 4，x win后，两者的计数 x多1
    public boolean validTicTacToe(String[] board) {
        char[][] dp = new char[3][3];
        for (int i = 0; i < board.length; i++) {
            String s = board[i];
            dp[i] = s.toCharArray();
        }

        int cntx = 0, cnto = 0;
        int[] cntwin = new int[2];// O,x
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                char c = dp[i][j];
                switch (c) {
                    case 'X':
                        cntx++;
                        list.add(new int[]{i, j});
                        break;
                    case 'O':
                        cnto++;
                        list.add(new int[]{i, j});
                        break;
                    case ' ':
                        break;
                }
            }
        }
        if (!(cntx == cnto + 1 || cnto == cntx)) {// 1，数量不正确
            return false;
        }
        int cntxCur = 0, cntoCur = 0;
        for (int i = 0; i < 3; i++) {// 行检测
            cntxCur = 0;
            cntoCur = 0;
            for (int j = 0; j < 3; j++) {
                char c = dp[i][j];
                if (c == ' ') {
                    break;
                } else if (c == 'X') {
                    cntxCur++;
                } else {
                    cntoCur++;
                }
            }
            cntwin[0] += cntoCur == 3 ? 1 : 0;
            cntwin[1] += cntxCur == 3 ? 1 : 0;
        }
        for (int i = 0; i < 3; i++) {// 列检测
            cntxCur = 0;
            cntoCur = 0;
            for (int j = 0; j < 3; j++) {
                char c = dp[j][i];
                if (c == ' ') {
                    break;
                } else if (c == 'X') {
                    cntxCur++;
                } else {
                    cntoCur++;
                }
            }
            cntwin[0] += cntoCur == 3 ? 1 : 0;
            cntwin[1] += cntxCur == 3 ? 1 : 0;
        }

        // 对角线检测 左上角->右下角
        cntxCur = 0;
        cntoCur = 0;
        for (int i = 0; i < dp.length; i++) {
            char c = dp[i][i];
            if (c == ' ') {
                break;
            } else if (c == 'X') {
                cntxCur++;
            } else {
                cntoCur++;
            }
        }
        cntwin[0] += cntoCur == 3 ? 1 : 0;
        cntwin[1] += cntxCur == 3 ? 1 : 0;

        // 对角线检测 右上角->左下角
        cntxCur = 0;
        cntoCur = 0;
        for (int i = 0; i < dp.length; i++) {
            char c = dp[i][2 - i];
            if (c == ' ') {
                break;
            } else if (c == 'X') {
                cntxCur++;
            } else {
                cntoCur++;
            }
        }
        cntwin[0] += cntoCur == 3 ? 1 : 0;
        cntwin[1] += cntxCur == 3 ? 1 : 0;


        // 判断win与其他限制条件融合
        if (cntwin[0] > 0 && cntwin[1] > 0) return false;// 不能同时win
        if (cntwin[0] > 0 && cntx > cnto) return false;
        if (cntwin[1] > 0 && cntx == cnto) return false;

        return true;
    }

    public static void main(String[] args) {
        _794有效的井字游戏 validTicTacToe = new _794有效的井字游戏();
//        String[] board = new String[]{"XXX", "OOX", "OOX"};
        String[] board = new String[]{"OXX", "XOX", "OXO"};
        System.out.println(validTicTacToe.validTicTacToe(board));
    }
}