2

別のサイトでこのインタビューの質問に出くわしました。

オセロのゲームでは、特定のルールに従って、赤または黒のディスクが 8x8 のグリッドに配置されます。プレーヤーは自分の色を選択し、グリッド上のディスクの数が最大のプレーヤーが勝ちます。

ディスクの有無を表す 2 つの 2D 配列 (1 つは赤、もう 1 つは黒) と、次の規則があるとします。

  • 長さ n > 3 のシーケンスの場合、(n-2) をそのプレーヤーのポイントとして割り当てます。
  • シーケンスは、垂直、水平、または斜めにすることができます
  • ディスクは複数のシーケンスに属することはできません

たとえば、次の 2D 配列の場合、ポイントは対角要素 ([0,0] を含む) と最初の行の要素 ([0,0] を除く)、または対角要素 ([0] を除く) の最大値になります。 ,0]) および水平要素 ([0,0] を含む)。iemax(4+0, 3+2) = 5

1 1 1 1 0 0
0 1 0 0 0 0
0 1 0 0 0 0
0 1 0 0 0
0 0 1 0
0 0 0 0 1

最大得点で勝者を決定します。

4

2 に答える 2

0

もっと簡単なものが見つかるかもしれませんが、私には提案があります。

プレーヤーのスコアを計算するには、構造体の 8X8 2D 配列を割り当てます。これには、垂直、水平、対角 1、対角 2 のフィールドが含まれます。

アルゴリズムの実行の最後に、この 4 つのフィールドは「これまで」のシーケンスのサイズを保持します。例として、セル (x,y) の「垂直」フィールドは、このセルにディスクがあり、そこにディスクがある場合に 1 を保持します。 (x,y-1) にディスクがなく、(x,y) と (x,y-1) にディスクがあるが (x, y-2) にディスクがない場合は 2 などです。3 についても同じです。他の分野。達成されたスコアを合計するには、スコア変数も必要です。

ここで、(0,0) セル [(0,0),(0,1)....(0,7),(1,0) から始めて、この配列を行ごとに昇順に調べる必要があります。 ...]、そして構造体を埋めます。各セルで、最初に元の 2D 配列の同等のセルにディスクがあるかどうかを確認します。ディスクがない場合は、スコアを保持し、現在のセルの構造体のすべてのフィールドを 0 に設定する必要があります。ディスクがある場合 (現在のセルが (x,y) であるとします)、次のように割り当てる必要があります。

(x,y)->vertical = (x,y-1)->vertical,
(x,y)->horizontal = (x-1,y)->horizontal,
(x,y)->diagonal1 = (x-1,y-1)->diagonal1,
(x,y)->diagonal2 = (x+1,y-1)->diagonal2.

各ポイントで、必要なすべての値がすでに計算されていることに注意してください。範囲外 (x-1 < 0 など) の場合、値は 0 です。また、4 を割り当てたフィールドごとにスコア カウンターを 2 ずつ、または 5 以上を割り当てたフィールドごとに 1 ずつ増やす必要があります (これにより、長さ n > 3 の各シーケンスに n-2 ポイントを与えます)。

それで全部です。すべての 2D 配列を通過した後、スコア カウンターはプレイヤーのスコアを保持します。

複雑さは O(n^2) であり、これはまったく悪くありません (実際、複雑さの点でより良い解決策を見つけることはできません)。

于 2012-04-15T00:17:06.210 に答える
0

ルールを理解するには、このリンクを試してくださいwww.springfrog.com/games/othello/othello.htm

使用されるデータ構造:

ボード: int[8][8];

uncounted_red: 2、uncounted_black: -2、空: 0;

count_red: 1、counted_black: -1

score_red: int、score_black: int;

アルゴリズム：

  1. 長さが 3 を超える連続した赤のシーケンスを検索

  2. 見つかったシーケンスごとに、スコアの長さを追加します - 2

  3. シーケンスで遭遇したすでにカウントされたペグによってスコアをさらに減らします。

  4. スコアを計算した後、カウントされていないすべてのペグをカウント済みとしてマークします。

  5. 黒のプロセスを繰り返します。

  6. 勝者 = スコア_赤 > スコア_黒 ? 赤、黒。

問題は、ステップ 1 をどのように実行するかということになります。

于 2012-07-27T02:47:21.793 に答える