Generalized solutions for n players


  • 0
    M

    Instead of using positive and negative integer to represent the two players, my solution could be generalized for n players. For player more than 2, the previous approach doesn't work. The trade-off here is that we need twice the space than the former solution, but the performance will not be sacrificed.

    Some follow-ups could be solved by this generalized solution.

    How could you implement m players Tic-Tac-Toe game?

    With the generalized solution below, you just need to change the playerNum = m;

    Another follow-up could be

    If the marks for a players is more than k (maybe less than n), the player wins.

    With the generalized solution below, you just need to change the comparison logic in the move function. When the number of marks is larger than k, then return that player.

    Here is the code:

    public class TicTacToe {
        
        int[][] rows;
        int[][] cols;
        int[][] diags;
        int n;
        int playerNum = 2; // can be replaced with n players
    
        public TicTacToe(int n) {
            this.rows = new int[n][playerNum];
            this.cols = new int[n][playerNum];
            this.diags = new int[2][playerNum];
            this.n = n;
        }
        
        public int move(int row, int col, int player) {
            rows[row][player-1] ++;
            cols[col][player-1] ++;
            diags[0][player-1] += row - col == 0 ? 1 : 0;
            diags[1][player-1] += row + col == n - 1 ? 1 : 0;
            if (rows[row][player - 1] == n || cols[col][player - 1] == n // n could be placed with K
                    || diags[0][player - 1] == n || diags[1][player - 1] == n) {
                return player;            
            }
            return 0;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.