読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

AtCoder Beginner Contest 039 D - 画像処理高橋君

解法

目標になる画像のある点(i, j)が黒色なら, その点もしくはその回り 8 マスのいずれかを塗る必要があります。このいずれかで, 白色になるべきところを黒く塗ってしまうようなのがあったらダメですが, そういうのがなければ考えている点がもともと黒くても問題ないです。ということでこれを愚直に実装しましょう。

…って考えたのが下のコードなんですが, 「目標の (i, j) が黒色なら」っていうの余計な気がしてきました。

初めてのそれっぽい python コード(もっとカッコよく書けるところがあったら教えてほC)

H, W = map(int, raw_input().split())
board = [raw_input() for i in range(H)]
ans = [[0 for i in range(W)] for i in range(H)]

dx = [1, 1, 0, -1, -1, -1, 0, 1, 0]
dy = [0, -1, -1, -1, 0, 1, 1, 1, 0]

for i in range(H):
    for j in range(W):
        if (board[i][j] == '#'):
            ok = -1
            for k in range(9):
                x = j+dx[k]
                y = i+dy[k]
                if (y < 0 or y >= H or x < 0 or x >= W):
                    continue
                ng = False
                for l in range(9):
                    nx = x+dx[l]
                    ny = y+dy[l]
                    if (ny < 0 or ny >= H or nx < 0 or nx >= W):
                        continue
                    if (board[ny][nx] == '.'):
                        ng = True
                        break
                if (not ng):
                    ok = k
                    break
            if (ok == -1):
                print("impossible")
                exit(0)
            ans[i+dy[ok]][j+dx[ok]] = 1
print("possible")
for i in range(H):
    print "".join(['#' if ans[i][j] == 1 else '.' for j in range(W)])