[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，Y的输入顺序，即X最多比O多一个，或者相等。

Input: board = ["O  ", "   ", "   "]这种情况O比X多所以输出false

（2）棋盘只能存在一个赢家

Input: board = ["XXX", " ", "OOO"]这种存在两个赢家也是False

（3）题目没有给出的一种具体情况

　　　

X X X O O _ O _ _ 当X赢得胜利时，应停止输入所以应该有两个。三、技巧与编码（1） 表示输入顺序用一个turn 来表示，若为X则加O则减判断最后 turn的值若为0或者1则为正常。（2）用一次两层循环记录所有的状态，整合变量的思想，记录某一行某一列的状态而不是中情况的状态。c++代码如下：class Solution {public:    bool validTicTacToe(vector<string>& board) {        //定义变量        int turn=0;        int row[3]={0},col[3]={0};        int diag=0,antidiag=0;        bool winx,wino;        for(int i=0;i<=2;i++)        {            for(int j=0;j<=2;j++)            {                if(board[i][j]=='X')                {                    row[i]++;                    col[j]++;                    turn++;                    if(i==j)                    {                        diag++;                                            }                    if(i+j==2)                    {                        antidiag++;                    }                                    }                else if(board[i][j]=='O')                {                    row[i]--;                    col[j]--;                    turn--;                    if(i==j)                    {                        diag--;                                            }                    if(i+j==2)                    {                        antidiag--;                    }                                                                            }                                            }        }        winx = row[0] == 3 || row[1] == 3 || row[2] == 3 ||               col[0] == 3 || col[1] == 3 || col[2] == 3 ||               diag == 3 || antidiag == 3;            wino = row[0]==-3 || row[1] == -3 || row[2] == -3 ||               col[0] == -3 || col[1] == -3 || col[2] == -3 ||               diag == -3 || antidiag == -3;        if((winx&&turn==0) || (wino&&turn==1))        {            return false;        }        return (turn==0||turn==1)&&(!winx||!wino);//当顺序没有错误，并且两者都没有全部胜利的时候。            }};

转载于:https://www.cnblogs.com/zydxx/p/9879612.html

相关资源：JAVA上百实例源码以及开源项目