Submission #1450720

---

Source Code Expand

import sys


H, W = map(int, input().split())
m = [input() for i in range(H)]

valid = True
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
for y in range(H):
    for x in range(W):
        if m[y][x] != '#':
            continue
        cnt = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and \
               0 <= ny and ny < H and m[ny][nx] == '#':
                cnt += 1
        if cnt >= 3:
            valid = False
            print("Impossible")
            sys.exit()


def rec(x, y):
    if x == W - 1 and y == H - 1:
        return True

    if m[y][x] != '#':
        return False
    dx = [0, 1]
    dy = [1, 0]

    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < W and \
           0 <= ny and ny < H and m[ny][nx] == '#':
            ret = rec(nx, ny)
            if ret:
                return ret
    return False


if rec(0, 0):
    print("Possible")
else:
    print("Impossible")

Submission Info

Judge Result