問題
要約
-
N行N列のマス目があり、各マスは白か黒で塗られている。
-
マス目の状態はN個の文字列S_iで表される。
- '#'は黒いマス
- '.'は白いマス
-
高橋君は最大2つの白いマスを選んで黒く塗ることができる。
目標は、黒いマスが縦、横、斜めのいずれかの方向に6つ以上連続するようにできるかどうかを判定すること。
斜めの連続については、N×Nのマス目内に完全に含まれる6×6のマス目で、少なくとも一方の対角線上のマスがすべて黒く塗られている状態を指す。
変数情報：
- N: マス目の行数と列数
- S_i: i行目のマスの状態を表す文字列（1 ≤ i ≤ N）
既存投稿一覧ページへのリンク
アプローチ
マス目の状態を確認し、縦、横、斜めの各方向で6つ以上の黒いマスが連続するパターンを作れるかどうかを判断する。
最大2つの白いマスを黒く塗ることができるため、6マス連続の中で最大2つまでの白いマスを許容する。
解法手順
-
入力からマス目の状態を2次元リストとして読み込む。
-
横方向と縦方向（90度回転後の横方向）のチェック
-
斜め方向（左上から右下と右上から左下）のチェック
-
いずれかの方向で条件を満たす場合は "Yes" を出力し、プログラムを終了する。
-
すべての方向で条件を満たさない場合は "No" を出力する。
ACコード
import sys
def io_func():
# マス目のサイズNを入力
N = int(input())
# N×Nのマス目の状態を2次元リストとして読み込む
grid = [list(input()) for _ in range(N)]
return N, grid
def check_direction(grid, N):
# 横方向と縦方向（90度回転後の横方向）のチェック
for _ in range(2):
for i in range(N):
for j in range(N):
if N - j < 6:
break
white_count = 0
# 6マス連続で確認
for k in range(6):
if grid[i][j+k] != "#":
white_count += 1
if white_count >= 3:
break
else:
# 白いマスが2つ以下なら条件を満たす
return True
# マス目を90度回転（転置して逆順に）
grid = list(zip(*grid))[::-1]
return False
def check_diagonal(grid, N):
# 斜め方向（左上から右下と右上から左下）のチェック
for _ in range(2):
for i in range(N):
for j in range(N):
if N - j < 6 or N - i < 6:
break
white_count = 0
# 6マス連続で確認（斜め方向）
for k in range(6):
if grid[i+k][j+k] != "#":
white_count += 1
if white_count >= 3:
break
else:
# 白いマスが2つ以下なら条件を満たす
return True
# マス目を90度回転（転置して逆順に）
grid = list(zip(*grid))[::-1]
return False
def solve(N, grid):
# 横方向と縦方向のチェック
if check_direction(grid, N):
return "Yes"
# 斜め方向のチェック
if check_diagonal(grid, N):
return "Yes"
# どの方向でも条件を満たさない場合
return "No"
if __name__=="__main__":
# メイン処理
N, grid = io_func()
result = solve(N, grid)
print(result)
##################################################################
# 変数の意味
# - N: マス目のサイズ（N×N）
# - grid: マス目の状態を表す2次元リスト
# - white_count: 6マス連続の中での白いマスの数
# 1. io_func関数
# - 標準入力からマス目のサイズNとマス目の状態を読み込む
# - 返り値: N（整数）, grid（2次元リスト）
# 2. check_direction関数
# - 横方向と縦方向（90度回転後の横方向）のチェックを行う
# - 6マス連続で白いマスが2つ以下かを確認
# - 条件を満たす場合はTrueを返す
# 3. check_diagonal関数
# - 斜め方向（左上から右下と右上から左下）のチェックを行う
# - 6マス連続で白いマスが2つ以下かを確認
# - 条件を満たす場合はTrueを返す
# 4. solve関数
# - check_direction関数とcheck_diagonal関数を呼び出し、結果を判定
# - どちらかの関数がTrueを返した場合は"Yes"を、そうでない場合は"No"を返す
# 5. メイン処理:
# - io_func関数でデータを読み込み
# - solve関数で結果を得て出力
思考過程
- マス目全体を走査し、6マス連続で条件を満たす箇所を探す。
- 縦、横、斜めの4方向すべてを確認する必要がある。
- コードの重複を避けるため、マス目を回転させて同じロジックを再利用する。
計算量の概算
- 最悪の場合、O(N^2)
- N x Nのマス目に対して、各マスを起点として4方向（実際には2回の回転で4方向をカバー）を確認するため。
その他周辺知識
二次元配列（行列）
grid = [list(input()) for _ in range(N)]
この部分で、N×Nの二次元配列（行列）を作成している。これは、平面上の座標系を離散化して表現する方法である。
座標系と繰り返し（ループ）
for i in range(N):
for j in range(N):
if N - j < 6:
break
# ...
この二重ループは、二次元平面上の各点を走査している。
i, jはそれぞれ行と列の添字であり、離散的な座標を表している。
条件判定
white_count = 0
for k in range(6):
if grid[i][j+k] != "#":
white_count += 1
if white_count >= 3:
break
else:
return True
この部分では、6マス連続の中で白いマス（"#"でないマス）の数をカウントし、その数が2以下であるかを判定している。
回転変換と転置行列(*)
grid = list(zip(*grid))[::-1]
この行は、マス目を90度回転させている。
行列の転置（zip(*grid)）と行の逆順（[::-1]）を組み合わせることで、90度回転を実現している。
ベクトルと対角線
for k in range(6):
if grid[i+k][j+k] != "#":
white_count += 1
# ...
check_diagonal関数内のこの部分は、対角線方向のマスを走査している。
(i+k, j+k)は、(1,1)というベクトルの整数倍で表される対角線上の点を表している。