問題 4 までとは違う問題についてここからは学習していきます。


問題

3×3 のグリッドが与えられます。AさんとBさんはグリッドの格子点 (16 個) を以下のように選んでいきます。

今まで選んだ任意の 4 点がそれぞれの辺がグリッドの辺に平行な長方形にならないように格子点を選ぶ。

先に行動が出来なくなった人が負けです。今までの 2 人の選んだ点の座標が与えられるので、最適戦略を行ったときの勝敗を判定してください。


この問題を解くために必要なことについてステップごとに行っていきます。

ここでは終了条件について、学習していきます。

まず初めに、ある盤面が与えられたときにそのゲームはもう終了しているかについて判定していきます。

ゲームの終了条件はそれぞれの辺がグリッドの辺に平行な長方形となる 4 点が存在することです。この場合、ゲームは終了しています。

グリッド上のそれぞれの辺がグリッドの辺に平行な長方形を全探索してみましょう。左上と右下の点が確定すれば、それぞれの辺がグリッドの辺に平行な長方形は 1 通りに定まります。よって、左上と右下の点を全探索してみましょう。

では実際にやってみましょう。

(問題)

3×3 のグリッドが与えられます。16 個の整数 S_{i,j} (1 ≦ i ≦ 4, 1 ≦ j ≦ 4) が与えられるので、ゲームがこの時点で終了しているかを判定してください。S_{i,j} (1 ≦ i ≦ 4, 1 ≦ j ≦ 4) は上から i 行目、左から j 列目の格子点がすでに選ばれていれば 1、そうでなければ 0 となっています。