AtCoder Grand Contest 007: A - Shik and Stone

,

http://agc007.contest.atcoder.jp/tasks/agc007_a

$1$WA。

solution

#の数が$H + W - 1$に一致するか見る。$O(HW)$。

implementation

#!/usr/bin/env python3
def solve(h, w, a):
    b = []
    b += [ '.' * (w + 2) ]
    b += [ '.' + row + '.' for row in a ]
    b += [ '.' * (w + 2) ]
    y, x = 1, 1
    while (y, x) != (h, w):
        if b[y - 1][x] == b[y][x - 1] == '#':
            return False
        if b[y + 1][x] == b[y][x + 1] == '#':
            return False
        if b[y + 1][x] == '#':
            y += 1
        elif b[y][x + 1] == '#':
            x += 1
        else:
            return False
    return True
h, w = map(int, input().split())
a = [ input() for _ in range(h) ]
print(['Impossible', 'Possible'][solve(h, w, a)])