How to Design a Tic-Tac-Toe Game?
- 时间:2020-09-24 11:41:27
- 分类:网络文摘
- 阅读:89 次
Design a Tic-tac-toe game that is played between two players on a n x n grid.
You may assume the following rules:
- A move is guaranteed to be valid and is placed on an empty block.
- Once a winning condition is reached, no more moves is allowed.
- A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Example:
Given n = 3, assume that player 1 is “X” and player 2 is “O” in the board.
1 TicTacToe toe = new TicTacToe(3);TicTacToe toe = new TicTacToe(3);toe.move(0, 0, 1); -> Returns 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | | toe.move(0, 2, 2); -> Returns 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | | | toe.move(2, 2, 1); -> Returns 0 (no one wins) |X| |O| | | | | // Player 1 makes a move at (2, 2). | | |X| toe.move(1, 1, 2); -> Returns 0 (no one wins) |X| |O| | |O| | // Player 2 makes a move at (1, 1). | | |X| toe.move(2, 0, 1); -> Returns 0 (no one wins) |X| |O| | |O| | // Player 1 makes a move at (2, 0). |X| |X| toe.move(1, 0, 2); -> Returns 0 (no one wins) |X| |O| |O|O| | // Player 2 makes a move at (1, 0). |X| |X| toe.move(2, 1, 1); -> Returns 1 (player 1 wins) |X| |O| |O|O| | // Player 1 makes a move at (2, 1). |X|X|X|Could you do better than O(n^2) per move() operation? Could you trade extra space such that move() operation can be done in O(1)? Could you trade extra space such that move() operation can be done in O(1)?
Tic-Tac-Toe Game Design with O(1) Move
Your TicTacToe object will be instantiated and called as such:
1 2 | TicTacToe* obj = new TicTacToe(n); int param_1 = obj->move(row,col,player); |
TicTacToe* obj = new TicTacToe(n); int param_1 = obj->move(row,col,player);
When a player makes a move, we need to check if he/she wins the game. A simple solution is to check O(N^2) grid for horizontal, vertical and two diagonals to see if they are all occupied by this player. However, a better solution that has O(1) time would be to trade space for time. That is, we use O(N) space to record the number of each players in each row, column and two diagonals.
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 | class TicTacToe { public: /** Initialize your data structure here. */ TicTacToe(int n) { board.resize(n); rowc[0].resize(n); rowc[1].resize(n); colc[0].resize(n); colc[1].resize(n); d[0][0] = 0; d[0][1] = 0; d[1][0] = 0; d[1][1] = 0; for (int i = 0; i < n; ++ i) { board[i].resize(n); rowc[0][i] = 0; rowc[1][i] = 0; colc[0][i] = 0; colc[1][i] = 0; } } /** Player {player} makes a move at ({row}, {col}). @param row The row of the board. @param col The column of the board. @param player The player, can be either 1 or 2. @return The current winning condition, can be either: 0: No one wins. 1: Player 1 wins. 2: Player 2 wins. */ int move(int row, int col, int player) { board[row][col] = player; int n = board.size(); if (++rowc[player - 1][row] == n) return player; if (++colc[player - 1][col] == n) return player; if (row == col) { if (++d[player - 1][0] == n) return player; } if (n - row - 1 == col) { if (++d[player - 1][1] == n) return player; } return 0; } private: vector<vector<int>> board; int d[2][2]; vector<int> rowc[2]; vector<int> colc[2]; }; |
class TicTacToe { public: /** Initialize your data structure here. */ TicTacToe(int n) { board.resize(n); rowc[0].resize(n); rowc[1].resize(n); colc[0].resize(n); colc[1].resize(n); d[0][0] = 0; d[0][1] = 0; d[1][0] = 0; d[1][1] = 0; for (int i = 0; i < n; ++ i) { board[i].resize(n); rowc[0][i] = 0; rowc[1][i] = 0; colc[0][i] = 0; colc[1][i] = 0; } } /** Player {player} makes a move at ({row}, {col}). @param row The row of the board. @param col The column of the board. @param player The player, can be either 1 or 2. @return The current winning condition, can be either: 0: No one wins. 1: Player 1 wins. 2: Player 2 wins. */ int move(int row, int col, int player) { board[row][col] = player; int n = board.size(); if (++rowc[player - 1][row] == n) return player; if (++colc[player - 1][col] == n) return player; if (row == col) { if (++d[player - 1][0] == n) return player; } if (n - row - 1 == col) { if (++d[player - 1][1] == n) return player; } return 0; } private: vector<vector<int>> board; int d[2][2]; vector<int> rowc[2]; vector<int> colc[2]; };
Instead of storing the counters for each player, We can alternatively reduce the space usage to half i.e. increment the counter for player 1 and decrement the counter for player 2. Then we need to check if the absolute value of the counter equals to N.

tic-tac-toe
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:The Brace Expansion Algorithms using Breadth First Search or Dep Coding Exercise: Sum of Digits in the Minimum Number Javascript Coding Exercise: The QuickSort Implementation in Java In-place Run-Length String Compressions using C++ Algorithms to Compute the Factor Combinations for An Integer usi How and Why You Should Use Infographics On Your Blog How to Make Your “Contact Us” Page Kick Ass The A to Z of Content Marketing: Habits Every Content Marketer S Keeping the Flame Going: How to Rock a Steady Job and Still Have How to Use Social Media and User-Generated Content to Boost Traf
- 评论列表
-
- 添加评论