Submission #979570

---

Source Code Expand

from collections import deque
h, w =  map(int, input().split())
a = [list(input()) for i in range(h)]
mv = [[1, 0], [0, 1]]

sx, sy = 0, 0
gx, gy = h - 1, w - 1
nxt = deque()
nxt.appendleft([sx, sy])

for i in range(h - 1):
    count = 0
    for j in range(w):
        if a[i][j] == a[i + 1][j]:
            count += 1
    if count > 1:
        nxt.clear()
        break
        
flag = 0
while len(nxt) > 0:
    tmp = nxt.pop()
    nwx, nwy = tmp[0], tmp[1]
    if nwx == gx and nwy == gy:
        flag = 1
        break
    for i in range(2):
        tmpx = mv[i][0] + nwx
        tmpy = mv[i][1] + nwy
        if tmpy < w and tmpx < h:
            if a[tmpx][tmpy] == '#':
                nxt.appendleft([tmpx, tmpy])
if flag:
    print("Possible")
else:
    print("Impossible")

Submission Info

Judge Result