Pythonで色付きセルを含む正方形を2つの等しい部分に分割できるか判定する方法

サイズ n の正方形が与えられているとします。この正方形はさらに n² 個の単位サイズの小さな正方形（セル）に分割されており、そのうちの1つだけが特別な色で塗られています。

ここで、この大きな正方形を2つの等しい部分に切り分けることを考えます。ただし、以下の条件を満たす必要があります。

• 切断線が、色付きの小さな正方形と一切交わらないこと
• 切り分けられた2つのピースが、互いに鏡像（鏡写し）の関係になっていること

つまり、これらの条件を満たすような切り分けが可能かどうかを判定するのが課題です。入力としては、n の値と大きな正方形内における色付きセルの位置（行・列）が与えられます。

例えば、size = 50、colored_row_pos = 25、colored_col_pos = 25 のように入力された場合、出力は「Cutting is not possible.（切り分けは不可能）」となります。

解決のための手順

この問題は、次の手順で解くことができます。

• middle := size / 2 の床関数（小数点以下切り捨て）の値を求める
• (middle == colored_row_pos または middle == colored_row_pos − 1) かつ (middle == colored_col_pos または middle == colored_col_pos − 1) が成り立つ場合は False を返す
• それ以外の場合は True を返す

考え方のポイント

正方形を2つの鏡像となる等しい部分に分割する場合、切断線は必ず正方形の中心を通ることになります。したがって、色付きセルが中央付近（middle または middle − 1 の位置）に存在する場合、どのように切っても切断線がそのセルを通過してしまいます。逆に、色付きセルが中央から離れた位置にあれば、中心を通る切断線を避けてカットすることが可能です。この性質を利用することで、単純な条件判定だけで問題を解決できます。

実装例

それでは、実際のコードを見て理解を深めましょう。

def solve(size, colored_row_pos, colored_col_pos):
    middle = size // 2
    if (middle == colored_row_pos or middle == colored_row_pos - 1) and \
       (middle == colored_col_pos or middle == colored_col_pos - 1):
        print("Cutting is not possible")
    else:
        print("Cutting is possible")

size = 50
colored_row_pos, colored_col_pos = 25, 25
solve(size, colored_row_pos, colored_col_pos)

入力

50, 25, 25

出力

Cutting is not possible

この例では、サイズ50の正方形に対して色付きセルが位置(25, 25)、つまりちょうど中央に配置されているため、どのような直線で切っても切断線が色付きセルを横断してしまいます。その結果、「切り分けは不可能」という判定が出力されます。