3

在这本很棒的书中，我们被要求设计一种算法来判断某人是否在井字游戏中获胜。给出了以下解决方案，之后作者说：

请注意，通过添加行数和列数数组（以及对角线的两个总和），运行时间可以减少到 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;
}
4

2 回答 2

4

每次在棋盘中放置新棋子时，您将相应的行、列和（可能）对角线计数器增加 1。您可以为玩家提供单独的计数器，或者使用 +1/-1。

现在当你检查棋盘时，你只需要检查这个计数器是否等于 N，这可以在O(N)(2N+2 个计数器) 中完成。

于 2012-10-07T23:21:25.250 回答
2

他们可能的意思是，当您放置片段时，您会更新片段贡献的每个数组的总和。即对应的行和列。如果它在对角线上，那么你也更新它。

在更新方面，如果是红色则加 1，如果是蓝色则减 1。如果您的计数从 0 开始，那么如果该值达到 -3 或 3，您就有赢家。

于 2012-10-07T23:23:24.020 回答