問題
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
余談
一瞬、探索系かなーと思ったけど、そう複雑に考えなくても解けるなーと気づいて考え直せたのは良かったかな。
元々解説書く気はなかったのですが、解けなかった人もいるらしいので一応書いておきました。