[Leetcode] 794. Valid Tic-Tac-Toe State 解題報告

題目：

A Tic-Tac-Toe board is given as a string array 

board

. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The 

board

 is a 3 x 3 array, and consists of characters 

" "

, 

"X"

, and 

"O"

.  The " " character represents an empty square.

Here are the rules of Tic-Tac-Toe:

• Players take turns placing characters into empty squares (" ").
• The first player always places "X" characters, while the second player always places "O" characters.
• "X" and "O" characters are always placed into empty squares, never filled ones.
• The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
• The game also ends if all squares are non-empty.
• No more moves can be played if the game is over.

Example 1:
Input: board = ["O  ", "   ", "   "]
Output: false
Explanation: The first player always plays "X".

Example 2:
Input: board = ["XOX", " X ", "   "]
Output: false
Explanation: Players take turns making moves.

Example 3:
Input: board = ["XXX", "   ", "OOO"]
Output: false

Example 4:
Input: board = ["XOX", "O O", "XOX"]
Output: true
      

Note:

• board

   is a length-3 array of strings, where each string 

  board[i]

   has length 3.
• Each 

  board[i][j]

   is a character in the set 

  {" ", "X", "O"}

  .

思路：

分為兩步進行檢查：

1）統計‘X’出現的次數x_count和‘O’出現的次數o_count，合法的棋盤應該是要麼‘X’出現的次數等于‘O’出現的次數（最後一步由player2下出），要麼‘X’出現的次數等于‘O’出現的次數加1（最後一步由player1下出）。如果都不符合這兩種情況，那麼就可以直接傳回false了。

2）統計形成三個連續‘X’的個數x_lines，以及形成三個連續‘O’的個數o_lines。由于棋盤上隻有9個位置，是以o_lines不可能等于2。然後我們對x_lins的出現次數進行分類讨論：a) x_lines == 2，此時隻有可能是某一行（列）和某個對角線形成了兩個x_liens，例如["XXX", "OXO", "OOX"]，是以隻需要判斷x_count是否為5即可；b) x_lines == 1，此時必須o_lines == 0并且棋盤上‘X’的個數大于‘O’的個數才行，因為隻有這樣才能說明是player1最後一步下了一個‘X’導緻獲勝的；c) 如果x_lines == 0，那麼要麼o_lines == 0表示雙方都沒有獲勝，要麼players2獲勝了，即o_lines == 1 && (x_count == o_count)。

代碼：

class Solution {
public:
    bool validTicTacToe(vector<string>& board) {
        // step 1: check the number of 'X's and 'O's
        int x_count = 0, o_count = 0;
        for (int r = 0; r < 3; ++r) {
            for (int c = 0; c < 3; ++c) {
                x_count += board[r][c] == 'X';
                o_count += board[r][c] == 'O';
            }
        }
        if (x_count != o_count && x_count != o_count + 1) {
            return false;
        }
        // step 2: check the number of 'X'lines and 'O' lines
        int x_lines = 0, o_lines = 0;
        const string &r1 = board[0], &r2 = board[1], &r3 = board[2];
        string c1, c2, c3, d1, d2;
        c1 += board[0][0], c1 += board[1][0], c1 += board[2][0];
        c2 += board[0][1], c2 += board[1][1], c2 += board[2][1];
        c3 += board[0][2], c3 += board[1][2], c3 += board[2][2];
        d1 += board[0][0], d1 += board[1][1], d1 += board[2][2];
        d2 += board[0][2], d2 += board[1][1], d2 += board[2][0];
        x_lines += r1 == "XXX", x_lines += r2 == "XXX", x_lines += r3 == "XXX";
        x_lines += c1 == "XXX", x_lines += c2 == "XXX", x_lines += c3 == "XXX";
        x_lines += d1 == "XXX", x_lines += d2 == "XXX";
        o_lines += r1 == "OOO", o_lines += r2 == "OOO", o_lines += r3 == "OOO";
        o_lines += c1 == "OOO", o_lines += c2 == "OOO", o_lines += c3 == "OOO";
        o_lines += d1 == "OOO", o_lines += d2 == "OOO";
        if (x_lines == 2) {
            return x_count == 5;
        }
        else if (x_lines == 1) {
            return o_lines == 0 && (x_count > o_count);
        }
        else {
            return o_lines == 0 || (o_lines == 1 && x_count == o_count);
        }
    }
};