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)])