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-150x150 How to Design a Tic-Tac-Toe Game? algorithms c / c++ code design questions games

tic-tac-toe

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
What Should Your Anti Virus Software Have in Order to Be Effecti  The Importance of SEO and How They Improve the Number of Your Cl  Learn The Basics Of Google My Business  Iterative and Recursion Algorithms to Compute the Number of Step  How to Check if a DLL or EXE is 32-bit or 64-bit (x86 or x64) us  C++: How to Iterate the Elements over the Sets (set, unordered_s  How to Iterate over the Items in Java’s Map (HashMap, Hash  Dynamic Programming Algorithm to Count Vowels Permutation  Exploring the Importance of Brand Consistency  Cleaning A WordPress Malware Infection For Dummies 
评论列表
添加评论