Buckle practice - 31 effective tic tac toe games

31 Effective tic tac toe game

1. Problem description
Use string array as the game board of tic tac toe game board. If and only if during tic tac toe , When it is possible for players to place characters in the state shown on the game board , To return to true.

The game board is a 3 x 3 Array , By the character " ",“X” and “O” form . character " " For a vacant seat .

Here are the rules of the tic tac toe game ：

Players take turns putting characters in the space （" "） in .

The first player always put characters “X”, And the second player always put characters “O”.

“X” and “O” It is only allowed to be placed in an empty space , It is not allowed to fill the position where the character has been placed .

When there is 3 Same （ It's not empty ） Fill any line with characters from 、 Column or diagonal line , Game over .

When all positions are not empty , It's the end of the game .

If the game is over , Players are not allowed to place any more characters .

Example 1:

Input : board = ["O ", " ", " "]

Output : false

explain : The first player always places “X”.

Example 2:

Input : board = [“XOX”, " X ", " "]

Output : false

explain : Players should be placed in turn .

Example 3:

Input : board = [“XXX”, " ", “OOO”]

Output : false

Example 4:

Input : board = [“XOX”, “O O”, “XOX”]

Output : true

explain :

Game board board It's a length of 3 Array of strings , Each of these strings board[i] The length of is 3.

board[i][j] Is a collection {" ", “X”, “O”} A character in .

The following can be used: main function ：

int main()

{

vector<string> board;

string aRow;

for(int i=0; i<3; i++)

{

    getline(cin,aRow);

    board.push_back(aRow);

}

bool res=Solution().validTicTacToe(board);

cout<<(res?"true":"false")<<endl;



return 0;

}

2. Enter description
Enter three lines , Three characters per line , Every character belongs to a set {" ", “X”, “O”}
3. The output shows that
Output results ：true or false
4. Example
Input
XOX
O O
XOX
Output
true
5. Code

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<set>
#include<stack>
using namespace std;

bool win(vector<string>&board, char p)
{
    
	//1. a line / All are listed as X or O situation 
	for (int 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;
	}
	//2. Diagonal situation 
	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));
}


bool validTicTacToe(vector<string> board)
{
    
	//1. because X It's always better than O First put , therefore X The number must be greater than or equal to O Number   If the first player wins , be X The number ratio is O More than one 1 ; If the second player wins , be X and O The number is equal 
	//2. non-existent 3 individual X In a row / Column , meanwhile  3 individual O In another line / Column 

	//1. Calculation x and 0 Number 
	int xcount = 0;
	int ocount = 0;

	for (string &row : board)// Go through every line 
	{
    
		for (char c : row)// Traverse row Each element of the row 
		{
    
			if (c == 'X')
				xcount++;
			if (c == 'O')
				ocount++;
		}
	}

	//2. Judge whether it is normal  
	// Reduction to absurdity 
	// As long as one of these conditions exists , Then the return is true , Finally, take the negative output result is false
	return !(
		   (ocount != xcount && ocount != xcount - 1)//O and X When the number of is not equal , Be sure to meet X The number ratio is O The number is bigger 
		|| (ocount != xcount && win(board, 'O'))//O If you win ,X The number must be equal to O Number 
		|| (ocount != xcount - 1 && win(board, 'X'))//X If you win ,X The number must be equal to O Number plus 1
		);

}


 
int main()

{
    

	vector<string> board;

	string aRow;

	for (int i = 0; i < 3; i++)

	{
    

		getline(cin, aRow);

		board.push_back(aRow);

	}

	bool res = validTicTacToe(board);

	cout << (res ? "true" : "false") << endl;



	return 0;

}