そまちょブログのそまちょ(@somachob)です。
この記事は、京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305)のC問題についての解説です。
C – Snuke the Cookie Picker
縦Hマス、横Wマスのグリッドで、縦横2マス以上の部分長方形の欠けた1マスを求めます。
入力例1をもとに、解説します。
まずは、入力を受け取ります。
グリッドは、入力の1行ごとの文字列をリストとして受け取ります。
H, W = map(int, input().split())
S = [input() for _ in range(H)]
print(S)
"""出力結果
['......', '..#.#.', '..###.', '..###.', '......']
"""
2重の for でループすることで、すべてのマスについて探索することができます。
H, W = map(int, input().split())
S = [input() for _ in range(H)]
for i in range(H):
for j in range(W):
# i 行目、j 列目の S を出力
print(S[i][j], end='')
# 次の行になるので改行する
print()
"""出力結果
......
..#.#.
..###.
..###.
......
"""
グリッドの添え字は、次のようになります。
左上が S[0][0]、右下がS[4][5] です。
H\W | 0 | 1 | 2 | 3 | 4 | 5 |
0 | . | . | . | . | . | . |
1 | . | . | # | . | # | . |
2 | . | . | # | # | # | . |
3 | . | . | # | # | # | . |
4 | . | . | . | . | . | . |
部分長方形は縦横2マス以上のため、1マスかけていても元の部分長方形の上下左右の大きさを求めることができます。
- # の最も小さい行の値:部分長方形の上
- # の最も大きい行の値:部分長方形の下
- # の最も小さい列の値:部分長方形の左
- # の最も大きい列の値:部分長方形の右
グリッドを全探索して、そのマスが # だったときに上下左右の値を更新します。
最も小さいのは min()、最も大きいのは max() を使うことで求めることができます。
# 入力
H, W = map(int, input().split())
S = [input() for _ in range(H)]
# 部分長方形の各値
top = H
bottom = 0
left = W
right = 0
# 部分長方形の範囲を求める
for i in range(H):
for j in range(W):
# 部分長方形の各値の更新
if S[i][j] == '#':
top = min(top, i)
bottom = max(bottom, i)
left = min(left, j)
right = max(right, j)
# 部分長方形の各値の確認
print(f'top:{top}')
print(f'bottom:{bottom}')
print(f'left:{left}')
print(f'right:{right}')
"""出力結果
top:1
bottom:3
left:2
right:4
"""
print(f’top:{top}’)は、フォーマット文字列です。
「f」を文字列の頭につけることで、文字列内の{}で囲った部分は変数と認識されます。
出力結果から、問題なく部分長方形の上下左右が求められました。
H\W | 0 | 1 | 2(left) | 3 | 4(right) | 5 |
0 | . | . | . | . | . | . |
1(top) | . | . | # | . | # | . |
2 | . | . | # | # | # | . |
3(bottom) | . | . | # | # | # | . |
4 | . | . | . | . | . | . |
あとは、部分長方形の上下左右について、探索することで答えを求めることができます。
答えは、添え字に1足すことに注意してください。
# 入力
H, W = map(int, input().split())
S = [input() for _ in range(H)]
# 部分長方形の各値
top = H
bottom = 0
left = W
right = 0
# 部分長方形の範囲を求める
for i in range(H):
for j in range(W):
# 部分長方形の各値の更新
if S[i][j] == '#':
top = min(top, i)
bottom = max(bottom, i)
left = min(left, j)
right = max(right, j)
# 答えの変数
answer_i = 0
answer_j = 0
# 部分長方形の探索
for i in range(top, bottom + 1):
for j in range(left, right + 1):
# 欠けたマス
if S[i][j] == '.':
# 答えの格納
answer_i = i + 1
answer_j = j + 1
# 答えの出力
print(answer_i, answer_j)
別解
部分長方形の一部のとき、そのマスから上下左右の4方向のうち、2方向は # になります。
欠けたマスが、部分長方形の真ん中のとき
欠けたマスの周りには、# が4つ
###
#.#
###
欠けたマスが、部分長方形の辺のとき
欠けたマスの周りには、# が3つ
###
.##
###
#.#
###
###
欠けたマスが、部分長方形の角のとき
欠けたマスの周りには、# が2つ
.##
###
###
##.
###
###
この性質から、各マスについて探索し、. のマスの上下左右に # が2つ以上あれば、それが答えになります。
上下左右のマスが、グリッドの範囲内か事前に確認しています。
# 入力
H, W = map(int, input().split())
S = [input() for _ in range(H)]
# 答えの変数
answer_i = 0
answer_j = 0
for i in range(H):
for j in range(W):
if S[i][j] == '.':
count = 0 # 「#」の数
if 0 <= i-1 < H:
# 上のマス
if S[i-1][j] == '#':
count += 1
if 0 <= i+1 < H:
# 下のマス
if S[i+1][j] == '#':
count += 1
if 0 <= j-1 < W:
# 左のマス
if S[i][j-1] == '#':
count += 1
if 0 <= j+1 < W:
# 右のマス
if S[i][j+1] == '#':
count += 1
# 答えの格納
if count >= 2:
answer_i = i + 1
answer_j = j + 1
# 答えの出力
print(answer_i, answer_j)
上下左右の探索は次のように書くこともできます。
4方向移動用の dx と dy のリストを作り、それを使うことで上下左右の探索をしています。
# 現在のマス。(1, 1)とする
i = 1
j = 1
# 4方向移動用のリスト
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
# 上下左右の探索
for k in range(4):
nx = i + dx[k]
ny = j + dy[k]
print(nx, ny)
"""実行結果
0 1 # 上
1 0 # 左
2 1 # 下
1 2 # 右
"""
H\W | 0 | 1 | 2 |
0 | . | (0, 1) | . |
1 | (1, 0) | (1, 1) | (1, 2) |
2 | . | (2, 1) | . |
これを使えば次のように書き換えられます。
# 入力
H, W = map(int, input().split())
S = [input() for _ in range(H)]
# 4方向移動用のリスト
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
# 答えの変数
answer_i = 0
answer_j = 0
for i in range(H):
for j in range(W):
if S[i][j] == '.':
count = 0 # 「#」の数
# 上下左右の探索
for k in range(4):
nx = i + dx[k]
ny = j + dy[k]
# グリッド内か
if 0 <= nx < H and 0 <= ny < W:
if S[nx][ny] == '#':
count += 1
# 答えの格納
if count >= 2:
answer_i = i + 1
answer_j = j + 1
# 答えの出力
print(answer_i, answer_j)
# の数の探索部分を関数に書き出し(メソッドの抽出)、if 文の条件を反転させる(ガード節)ことで、インデントを浅くすることができます。
# 入力
H, W = map(int, input().split())
S = [input() for _ in range(H)]
# 4方向移動用のリスト
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
# 答えを求める
def solve(i, j):
count = 0 # 「#」の数
# 上下左右の探索
for k in range(4):
nx = i + dx[k]
ny = j + dy[k]
# グリッド外のとき
if (nx < 0 or H <= nx) or (ny < 0 or W <= ny):
continue
if S[nx][ny] == '#':
count += 1
# 答えの出力
if count >= 2 :
print(i + 1, j + 1)
# グリッドの探索
for i in range(H):
for j in range(W):
# 「#」のときはスキップ
if S[i][j] == '#':
continue
# 上下左右の探索
solve(i, j)