名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

ABC096 C - Grid Repainting 2

問題

C: Grid Repainting 2 - AtCoder Beginner Contest 096 | AtCoder

読解

パッと見全探索か、シミュレーションで制約見てもせいぜいO(HW)で、H, Wともに小さいのでそこまで工夫せず全探索でいいなーと判断。

テーブルみたいな問題はx, yの方向を間違えがちなので、ミスをしないように意識する。

方針

実は解説と違う解放だったらしい。

実際に塗ってみて結果をシミュレーションする。 全て . のテーブルを入力と別に持って、入力されたテーブルで # が見つかれば、上下左右見て上下左右に # があれば別に持ったテーブルに # を書き込む。

そして書き込みテーブル結果と入力データが等しいかどうか見て、Yes、Noを判断する。

ポイントとしてはmx, my を使ってif文を書き連ねないことですかね…。自分が技術書典で出したコードを見返していて、これ積極的に使わないとなーと思ったことの1つです(ifネストとか、ifが無数に増えるとかWA出したときにコードが追えなくなるので大変、3分前にコード書いていた自分はすでに別人なのだ…、解釈時間が必要なのは惜しい)

競技では可読性うんぬんの話がされますが、ガチガチに意識しないでいいとはいえ、自分があとから見返してCOOLだったなこれ(早く書けたとか、気付きによって美しくまとめられたとか)とか思えないのも捗らないかなーと思うので、コンテスト中ないしコンテストが終わったあともコードを見返して成長を実感していきたいなと思います。

コード

Submission #2469355 - AtCoder Beginner Contest 096 | AtCoder

h, w = map(int, input().split())
table = [list(input()) for _ in range(h)]
visited = [["." for _ in range(w)] for _ in range(h)]

mx = [0, 1, 0, -1]
my = [1, 0, -1, 0]
for i in range(h):
  for  j in range(w):
    if table[i][j] == "#":
      for k in range(4):
        tx, ty = j + mx[k], i + my[k]
        if 0 <= tx < w and 0 <= ty < h and table[ty][tx] == "#":
          visited[i][j] = visited[ty][tx] = "#"

for i in range(h):
  for  j in range(w):
    if table[i][j] != visited[i][j]:
      print("No")
      exit(0)
print("Yes")

解説どおりのコード

実はシミュレーションしなくても良かった。ほぼ変えなくて済んだので、一応書いて出しておいた。(ブログにはコード略)

Submission #2474624 - AtCoder Beginner Contest 096 | AtCoder

余談

一瞬、探索系かなーと思ったけど、そう複雑に考えなくても解けるなーと気づいて考え直せたのは良かったかな。

元々解説書く気はなかったのですが、解けなかった人もいるらしいので一応書いておきました。