【AtCoder】ABC305 – C問題について解説【Python】

そまちょブログのそまちょ（@somachob）です。

この記事は、京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305)のC問題についての解説です。

C – Snuke the Cookie Picker
別解

C – Snuke the Cookie Picker

縦Hマス、横Wマスのグリッドで、縦横２マス以上の部分長方形の欠けた１マスを求めます。

入力例１をもとに、解説します。

入力例１

5 6
......
..#.#.
..###.
..###.
......

まずは、入力を受け取ります。

グリッドは、入力の１行ごとの文字列をリストとして受け取ります。

H, W = map(int, input().split())
S = [input() for _ in range(H)]
print(S)

"""出力結果
['......', '..#.#.', '..###.', '..###.', '......']
"""

２重の 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	.	.	.	.	.	.

部分長方形は縦横２マス以上のため、１マスかけていても元の部分長方形の上下左右の大きさを求めることができます。

# の最も小さい行の値：部分長方形の上
# の最も大きい行の値：部分長方形の下
# の最も小さい列の値：部分長方形の左
# の最も大きい列の値：部分長方形の右

グリッドを全探索して、そのマスが # だったときに上下左右の値を更新します。

最も小さいのは 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	.	.	.	.	.	.

あとは、部分長方形の上下左右について、探索することで答えを求めることができます。

答えは、添え字に１足すことに注意してください。

# 入力
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)

別解

部分長方形の一部のとき、そのマスから上下左右の４方向のうち、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)

上下左右の探索は次のように書くこともできます。

４方向移動用の dx と dy のリストを作り、それを使うことで上下左右の探索をしています。

# 現在のマス。（1, 1）とする
i = 1
j = 1

# ４方向移動用のリスト
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)]

# ４方向移動用のリスト
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)]

# ４方向移動用のリスト
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)

リンク