Codeforces #300 D: Weird Chess

面白い問題だったがTLEしてしまった。

問題

N×Nのチェス盤の情報が与えられる(N ≦ 50)。チェス盤には同じ種類同じ色の駒が1つ以上のっており、あるマスは、駒がいる、駒が効いている、駒が効いていないのどれかである。駒はあるマスに移動するのにナイトのようにジャンプをするとする。また駒がいるマスにほかの駒が効いている場合もある。チェス盤にのっている駒の移動範囲としてありうるものがあるかどうか、あるならそのうちの一つ答えよ。

解法

駒の移動範囲としてあり得ないものを調べていくという方針で解ける。盤上のある駒に注目したとき、その駒から見て駒が効いていないマスは駒の移動範囲としてはあり得ない。これを盤上のすべての駒に適用すれば、駒が満たすべき移動範囲を得ることができる。

あとはこの移動範囲が与えられた盤上の状態を満たすかどうか確認する。駒が効いているはずのすべてのマスが、実際にどこかの駒から効いていることを確認する。これが満たせなければ条件を満たす移動範囲はなく、"NO"が答えとなる。

満たす場合は移動範囲の真ん中を駒に変えて出力すればいい。

下の書き方だとO(N⁴)。50⁴ = 6250000 でpythonでも間に合うかと思ったがTLE。TLEがありうるときはオーダーを落とすか、PyPyかC++で答えるようにしないといけない。

n = int(raw_input())
A = [list(raw_input()) for i in xrange(n)]
dxy = [["x"] * (2 * n - 1) for i in xrange(2 * n - 1)]
for y in xrange(n):
    for x in xrange(n):
        if A[y][x] == "o":
            for dy in xrange(-y, n - y):
                for dx in xrange(-x, n - x):
                    if dx == dy == 0: continue
                    if A[y + dy][x + dx] in ".":
                        dxy[dy + n - 1][dx + n - 1] = "."

for y in xrange(n):
    for x in xrange(n):
        if A[y][x] == "o":
            for dy in xrange(-y, n - y):
                for dx in xrange(-x, n - x):
                    if A[y + dy][x + dx] == "x" and dxy[dy + n - 1][dx + n - 1] == "x":
                        A[y + dy][x + dx] = "."

for y in xrange(n):
    if "x" in A[y]:
        print "NO"
        exit()
        
dxy[n - 1][n - 1] = "o"                     
print "YES"
for line in dxy:
    print "".join(line)