tic tac toe 실행 시간을 O (N)로 줄입니다.

이 great book에는 누군가 tic-tac-toe 게임에서 승리했는지 알아보기위한 알고리즘을 설계해야합니다. 은 다음 용액 저자가 상기 후 주어진다 : 런타임이 행과 열의 수 어레이 (및 대각선 두 합)tic tac toe 실행 시간을 O (N)로 줄입니다.

첨가하여 O (N)으로 감소 될 수

하는 것으로

나는 열심히 노력했지만 그 말의 의미를 알 수 없었다. 이 배열과 합계는 어떻게 추가됩니까? 감사 !

enum Piece { Empty, Red, Blue }; 
enum Check { Row, Column, Diagonal, ReverseDiagonal } 

Piece getIthColor(Piece[][] board, int index, int var, Check check) { 
    if (check == Check.Row) return board[index][var]; 
    else if (check == Check.Column) return board[var][index]; 
    else if (check == Check.Diagonal) return board[var][var]; 
    else if (check == Check.ReverseDiagonal)  
    return board[board.length - 1 - var][var];  

    return Piece.Empty; 
} 

Piece getWinner(Piece[][] board, int fixed_index, Check check) {  
    Piece color = getIthColor(board, fixed_index, 0, check); 
    if (color == Piece.Empty) return Piece.Empty; 
    for (int var = 1; var < board.length; var++) { 
    if (color != getIthColor(board, fixed_index, var, check)) { 
     return Piece.Empty; 
    } 
    } 
    return color; 
} 

Piece hasWon(Piece[][] board) { 
    int N = board.length; 
    Piece winner = Piece.Empty; 

    // Check rows and columns 
    for (int i = 0; i < N; i++) { 

    winner = getWinner(board, i, Check.Row); 
    if (winner != Piece.Empty) { 
     return winner; 
    }  

    winner = getWinner(board, i, Check.Column);  
    if (winner != Piece.Empty) { 
     return winner; 
    } 

    }  

    winner = getWinner(board, -1, Check.Diagonal); 
    if (winner != Piece.Empty) { 
    return winner; 
    }  

    // Check diagonal  
    winner = getWinner(board, -1, Check.ReverseDiagonal); 
    if (winner != Piece.Empty) { 
    return winner; 
    } 

    return Piece.Empty; 
}

출처

2012-10-07 Jihed Amine