AtCoder ABC 107 B – Grid Compression Python解説

スポンサーリンク

Grid Compression

縦 H 行、横 W 列のマス目があります。各マスは白または黒です。
ai,j が . ならばマス (i, j) は白であり、ai,j が # ならばマス (i, j) は黒です。

すぬけ君はこのマス目を圧縮しようとしています。 そのために、白いマスのみからなる行または列が存在する間、次の操作を繰り返し行います。

操作: 白いマスのみからなる行または列をひとつ任意に選び、その行または列を取り除いて空白を詰める。

各操作でどの行または列を選ぶかによらず、最終的なマス目は一意に定まることが示せます。 最終的なマス目を求めてください。

AtCoder Beginner Contest 「Grid Compression」

この問題の圧縮とは次のようなものです。

入力例
4 4
##.#
....
##.#
.#.#

出力例
###
###
.##

上記のように白マスのみの行と列は出力していません。これをどのように実装するか、行だけだったら入力から受け取る段階で黒マスを含んでいないものを弾いてしまえば良いのですが、列の方はなかなか面倒くさそうなので今回は行と列、共にflagで管理していきます。

h, w = map(int, input().split())

a = [input() for _ in range(h)]

r = [False] * h
c = [False] * w

for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            r[i] = True
            c[j] = True
            
for i in range(h):
    if r[i]:
        for j in range(w):
            if c[j]:
                print(a[i][j], end="")
        print()

まず行を管理するr = [False] * h、そして列を管理するc = [False] * wです。続くfor文で一度マス目の中身を確認しています。ここで黒マス(#)があれば、行と列のflagをTrueにしています。

2つめのfor文で実際に出力していきます。出力されるマスは行と列のflagが共にTrueのマス目のみです。
if文でflagが共にTrueならマス目を出力し、片方でもFalseなら処理を行わないので、これで空白を詰めることができます。

AtCoderB問題

Posted by cheese