そまちょブログのそまちょ（@somachob）です。
この記事は、AtCoder Beginner Contest 307 の C問題についての解説です。
C – Ideal Sheet
入力例１をもとに、解説します。
3 5
#.#..
.....
.#...
2 2
#.
.#
5 3
...
#.#
.#.
.#.
...シートA と シートB を重ねることで、シートX が作れるかを判定します。
まずは、入力の受け取りです。
それぞれのシートを同じように受け取ります。
# 入力
HA, WA = map(int, input().split())
A = [input() for _ in range(HA)]
HB, WB = map(int, input().split())
B = [input() for _ in range(HB)]
HX, WX = map(int, input().split())
X = [input() for _ in range(HX)]
# 入力確認用
print(A)
print(B)
print(X)
"""出力結果
['#.#..', '.....', '.#...']
['#.', '.#']
['...', '#.#', '.#.', '.#.', '...']
"""全探索する
こういった問題で考えるときは全探索ができるかです。
制約を確認すると、シートのサイズは最大で１０×１０なので、シートA と シートB の位置を全探索することで、解くことができそうです。
マイナス方向への移動について考慮しなくてよくするために、シートのサイズを黒いマスで切り抜きます。
そしてその左端を（０，０）に合わせて探索します。
シートの不要な範囲を削除するには次のようにします。
シートのマスを全探索して、黒いマスだったときに X と Y の最小値と最大値を更新することで、シートの黒いマスの範囲を取得します。
# 入力
HA, WA = map(int, input().split())
A = [input() for _ in range(HA)]
HB, WB = map(int, input().split())
B = [input() for _ in range(HB)]
HX, WX = map(int, input().split())
X = [input() for _ in range(HX)]
# シートの不要な範囲の削除
def resize(S, H, W):
minX, minY = 10, 10
maxX, maxY = 0, 0
for y in range(H):
for x in range(W):
if S[y][x] == '#':
minX = min(minX, x)
minY = min(minY, y)
maxX = max(maxX, x)
maxY = max(maxY, y)
resizeS = []
for y in range(minY, maxY + 1):
resizeS.append(S[y][minX:maxX+1])
return resizeS
# シートのリサイズ
A = resize(A, HA, WA)
B = resize(B, HB, WB)
X = resize(X, HX, WX)たとえば、シートX だと次のようになります。
minX=0
minY=1
maxX=2
maxY=3
ABC305 – C についての解説も参考にしてください。
これで、各シートの最小の範囲が切り取れました。
切り取りのときにスライスを使っていますが、スライスについてわからないときは次のリンクを参考にしてみてください。
あとはこれを全探索するだけです。
シートX の範囲を全探索する
たとえば、１０×１０のシートについて、シートA の貼り付ける位置を全探索するには、２重のループを使います。
外側のループで縦方向、内側のループで横方向に探索します。
# 全探索
for dy_a in range(len(X) - len(A) + 1):
for dx_a in range(len(X[0]) - len(A[0]) + 1):
# 処理探索範囲ですが、シートA の黒いマスをすべて含む必要があるため、シートX からシートA がはみ出さない範囲だけを探索します。
シートX が１０×１０の大きさだった場合、シートAの黒いマスの範囲の大きさは３×３のため、右方向には７、下方向には７だけ移動させれば大丈夫です。
探索するシートの大きさ ー 貼り付けるシートの大きさ ＝ 探索する範囲
上の図の横方向への探索について考えてみます。
横は１０マスなので、探索するシートの大きさは「１０」です。
貼り付けるシートの大きさは、横３マスなので「３」になります。
つまり、探索する範囲は「１０－３＝７」になります。
これで、for dx_a in range(7) だと、0 から 6 までになるため、for 文で７まで探索するためには＋１する必要があります。
シートX の横方向は len(X[0]) で確認でき、シートA の横方向は len(A[0]) で確認できます。
ちなみに、縦方向は len(X) と len(A) で確認できます。
# 全探索
for dy_a in range(len(X) - len(A) + 1):
for dx_a in range(len(X[0]) - len(A[0]) + 1):
# 処理これで、シートA の全探索ができるようになりました。
あとは、シートB についても全探索します。
この中に、同じように２重ループを書くことで全探索ができます。
# 全探索
for dy_a in range(len(X) - len(A) + 1):
for dx_a in range(len(X[0]) - len(A[0]) + 1):
for dy_b in range(len(X) - len(B) + 1):
for dx_b in range(len(X[0]) - len(B[0]) + 1):
# 処理シートA とシートB をシートC に貼り付ける
すべてのシートA とシートB の位置について、シートC を作成します。
それが次のコードです。
dy_a, dx_a, dy_b, dx_b が、シートA とシートB のそれぞれの縦横の移動分を表します。
# シートC の作成
def createC(dy_a, dx_a, dy_b, dx_b):
listC = [['.']*len(X[0]) for _ in range(len(X))]
for i in range(len(X)):
for j in range(len(X[0])):
# シートA が黒いマスのとき
if i < len(A) and j < len(A[0]):
if A[i][j] == '#':
listC[i + dy_a][j + dx_a] = '#'
# シートB が黒いマスのとき
if i < len(B) and j < len(B[0]):
if B[i][j] == '#':
listC[i + dy_b][j + dx_b] = '#'
# 比較しやすいように変換
C = []
for i in range(len(X)):
C.append(''.join(listC[i]))
return CシートC を作成するためにシートX のサイズで初期化します。
pythonでは、文字列は置き換えることができないため、横方向もリストで管理していることに注意してください。
たとえば、シートX が３×４だとつぎのようになります。
listC = [['.']*10 for _ in range(10)]
print(listC)
""""出力結果
[['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.']]
"""シートA とシートB が黒いマスのとき、引数の dy_a などの値によってシートC の位置を黒いマスに変換します。
その際に、i と j の値が、シートA とシートＢ の範囲外にならないようにします。
for i in range(len(X)):
for j in range(len(X[0])):
# シートA が黒いマスのとき
if i < len(A) and j < len(A[0]):
if A[i][j] == '#':
listC[i + dy_a][j + dx_a] = '#'
# シートB が黒いマスのとき
if i < len(B) and j < len(B[0]):
if B[i][j] == '#':
listC[i + dy_b][j + dx_b] = '#'最後に、シートX の横方向は文字列で管理しているので、シートC の横方向もリストから文字列に変換します。
join() メソッドで、リストを連結しています。str の文字列で iterable の要素を連結します。
str.join(iterable)# 比較しやすいように変換
C = []
for i in range(len(X)):
C.append(''.join(listC[i]))シートC とシートX が同じか
作成したシートC とシートX が同じか判定し、同じだったときは Yes を出力し、exit() で処理を終了します。
全探索しても、一致するものがなかった場合は No を出力します。
まとめたのが次のコードです。提出すれば AC できます。
# 入力
HA, WA = map(int, input().split())
A = [input() for _ in range(HA)]
HB, WB = map(int, input().split())
B = [input() for _ in range(HB)]
HX, WX = map(int, input().split())
X = [input() for _ in range(HX)]
# シートの不要な範囲の削除
def resize(S, H, W):
minX, minY = 100, 100
maxX, maxY = 0, 0
for y in range(H):
for x in range(W):
if S[y][x] == '#':
minX = min(minX, x)
minY = min(minY, y)
maxX = max(maxX, x)
maxY = max(maxY, y)
resizeS = []
for y in range(minY,maxY + 1):
resizeS.append(S[y][minX:maxX+1])
return resizeS
# シートのリサイズ
A = resize(A, HA, WA)
B = resize(B, HB, WB)
X = resize(X, HX, WX)
# シートC の作成
def createC(dy_a, dx_a, dy_b, dx_b):
listC = [['.']*len(X[0]) for _ in range(len(X))]
for i in range(len(X)):
for j in range(len(X[0])):
# シートA が黒いマスのとき
if i < len(A) and j < len(A[0]):
if A[i][j] == '#':
listC[i + dy_a][j + dx_a] = '#'
# シートB が黒いマスのとき
if i < len(B) and j < len(B[0]):
if B[i][j] == '#':
listC[i + dy_b][j + dx_b] = '#'
# 比較しやすいように変換
C = []
for i in range(len(X)):
C.append(''.join(listC[i]))
return C
# 全探索
for dy_a in range(len(X) - len(A) + 1):
for dx_a in range(len(X[0]) - len(A[0]) + 1):
for dy_b in range(len(X) - len(B) + 1):
for dx_b in range(len(X[0]) - len(B[0]) + 1):
C = createC(dy_a, dx_a, dy_b, dx_b)
if C == X:
print('Yes')
exit()
print('No')
