3

このすばらしい本では、三目並べのゲームで誰かが勝ったかどうかを判断するためのアルゴリズムを設計するように求められています。次の解決策が与えられ、その後、著者は次のように述べました。

行数と列数の配列（および対角線の2つの合計）を追加することで、実行時間を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 に答える