题目

类型：Array

image.png

解题思路

给定的棋盘大小固定，对于无效情况进行分情况讨论即可：

  • 由于 X 先手，O 后手，两者轮流下子。因此 O 的数量不会超过 X，且两者数量差不会超过 1，否则为无效局面；
  • 若局面是 X 获胜，导致该局面的最后一个子必然是 X，此时必然有 X 数量大于 O（X 为先手），否则为无效局面；
  • 若局面是 O 获胜，导致该局面的最后一个子必然是 O，此时必然有 X 数量等于 O（X 为先手），否则为无效局面；
  • 局面中不可能出现两者同时赢（其中一方赢后，游戏结束）。

代码

  1. class Solution {
  2.     public boolean validTicTacToe(String[] board) {
  3.         char[][] cs = new char[3][3];
  4.         int x = 0, o = 0;
  5.         for (int i = 0; i < 3; i++) {
  6.             for (int j = 0; j < 3; j++) {
  7.                 char c = board[i].charAt(j);
  8.                 if (c == 'X') x++;
  9.                 else if (c == 'O') o++;
  10.                 cs[i][j] = c;
  11.             }
  12.         }
  13.         boolean a = check(cs, 'X'), b = check(cs, 'O');
  14.         if (o > x || x - o > 1) return false;
  15.         if (a && x <= o) return false;        
  16.         if (b && o != x) return false;
  17.         if (a && b) return false;
  18.         return true;
  19.     }
  20.     boolean check(char[][] cs, char c) {
  21.         for (int i = 0; i < 3; i++) {
  22.             if (cs[i][0] == c && cs[i][1] == c && cs[i][2] == c) return true;
  23.             if (cs[0][i] == c && cs[1][i] == c && cs[2][i] == c) return true;
  24.         }
  25.         boolean a = true, b = true;
  26.         for (int i = 0; i < 3; i++) {
  27.             for (int j = 0; j < 3; j++) {
  28.                 if (i == j) a &= cs[i][j] == c;
  29.                 if (i + j == 2) b &= cs[i][j] == c;
  30.             }
  31.         }
  32.         return a || b;
  33.     }
  34. }