Java O(n) solution | Each move checks 4 possibilities to win (Column, Row, Forward Diagonal '\' , Backward Diagonal '/')


  • 0
    M
    public class TicTacToe {
        
        char[][] board;
        int count;
        int size;
    
        /** Initialize your data structure here. */
        public TicTacToe(int n) {
            board = new char[n][n];
            size = n;
        }
        
        /** 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. */
        public int move(int row, int col, int player) {
            char c = ' ';
            if (player == 1) {
                board[row][col] = 'X';
                c = 'X';
            } else {
                board[row][col] = '0';
                c = '0';
            }
            
            count++;
            
            /*
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    System.out.print(board[i][j] + " ");
                }
                System.out.println();
            }
            */
            
            if (count <= size*size && checkIfWin(row, col, c)) {
                return player;
            }
            
            return 0;
        }
        
        private boolean checkIfWin(int row, int col, char c) {
            
            // System.out.println("\n" + row + "," + col + "\n");
            
            if (checkColumn(0, col, c) || checkRow(row, 0, c)) {
                return true;
            } 
            
            if ((row == col || row + col == size - 1) && (checkForwardDiagonal(0, 0, c) || checkBackwardDiagonal(0, size - 1, c))) {
                return true;
            }
            
            return false;
        }
        
        private boolean checkColumn(int row, int col, char c) {
            
            System.out.println("Checking Column :  Start Point = " + row + "," + col);
            
            if (row == size) {
                return true;
            }
            
            if (isValid(row, col, size) && board[row][col] == c && checkColumn(row + 1, col, c)) {
                return true;
            }
            
            return false;
            
        }
        
        private boolean checkRow(int row, int col, char c) {
            
            // System.out.println("Checking Row :  Start Point = " + row + "," + col);
            
            if (col == size) {
                return true;
            }
            
            if (isValid(row, col, size) && board[row][col] == c && checkRow(row, col + 1, c)) {
                return true;
            }
            
            return false;        
        }
        
        private boolean checkForwardDiagonal(int row, int col, char c) {
            
            // System.out.println("Checking Forward Diagonal :  Start Point = " + row + "," + col);
            
            if (col == size && row == size) {
                return true;
            }
            
            if (isValid(row, col, size) && board[row][col] == c && checkForwardDiagonal(row + 1, col + 1, c)) {
                return true;
            }
            
            return false;
        }
                
        private boolean checkBackwardDiagonal(int row, int col, char c) {
            
            // System.out.println("Checking Backward Diagonal :  Start Point = " + row + "," + col);
            
            if (row == size && col < 0) {
                return true;
            }
            
            if (isValid(row, col, size) && board[row][col] == c && checkBackwardDiagonal(row + 1, col - 1, c)) {
                return true;
            }
            
            return false;
        }
        
        private boolean isValid(int row, int col, int n) {
            return row >= 0 && row < n && col >= 0 && col < n;
        }
    }
    
    /**
     * Your TicTacToe object will be instantiated and called as such:
     * TicTacToe obj = new TicTacToe(n);
     * int param_1 = obj.move(row,col,player);
     */
    

Log in to reply
 

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