Problem:


Score : 200 points

Problem Statement

   #nck {
      width: 30px;
      height: auto;
   }

We have a grid of H rows and W columns. Initially, there is a stone in the top left cell. Shik is trying to move the stone to the bottom right cell. In each step, he can move the stone one cell to its left, up, right, or down (if such cell exists). It is possible that the stone visits a cell multiple times (including the bottom right and the top left cell).

You are given a matrix of characters a_{ij} (1 \leq i \leq H, 1 \leq j \leq W). After Shik completes all moving actions, a_{ij} is # if the stone had ever located at the i-th row and the j-th column during the process of moving. Otherwise, a_{ij} is .. Please determine whether it is possible that Shik only uses right and down moves in all steps.

Constraints

2 \leq H, W \leq 8

a_{i,j} is either # or ..

There exists a valid sequence of moves for Shik to generate the map a.

Input

The input is given from Standard Input in the following format:

H W
a_{11}a_{12}...a_{1W}
:
a_{H1}a_{H2}...a_{HW}

Output

If it is possible that Shik only uses right and down moves, print Possible. Otherwise, print Impossible.

Sample Input 1

4 5
##...
.##..
..##.
...##

Sample Output 1

Possible

The matrix can be generated by a 7-move sequence: right, down, right, down, right, down, and right.

Sample Input 2

5 3
###
..#
###
#..
###

Sample Output 2

Impossible

Sample Input 3

4 5
##...
.###.
.###.
...##

Sample Output 3

Impossible



Sample input:
4 5
##...
.##..
..##.
...##


Sample output:
Possible

Submission status: Wrong Answer

Solution code:
h, w = list(map(int, input().split()))

grid = [input() for _ in range(h)]

x = 0
y = 0

while not (x == w-1 and y == h-1):
    c = []
    neighbours = 0
    if x != w-1:
        c.append([x+1, y, 1])
    if y != h-1:
        c.append([x, y+1, 3])

    for coords in c:
        if grid[coords[1]][coords[0]] == "#":
            neighbours += 1
            x2 = coords[0]
            y2 = coords[1]

    if neighbours != 1:
        print("Impossible")
        exit()

    c = []
    neighbours = 0
    if x != 0:
        c.append([x-1, y, 0])
    if y != 0:
        c.append([x, y-1, 2])

    for coords in c:
        if grid[coords[1]][coords[0]] == "#":
            neighbours += 1

    if neighbours > 1:
        print("Impossible")
        exit()

    x = x2
    y = y2

print("Possible")

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
list1 =[]
count = 0
for i in range(H):
  a = list(input())
  list1.append(a)
for i in range(H-1):
  for j in range(W-1):
    if list1[i][j] =='#':
      if list1[i+1][j] == '#' and list1[i][j+1] =='#':
        count +=1
if count == 0:
  print('Possible')
else:
  print('Impossible')

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [['.']+list(input())+['.'] for i in range(H)]
A = [['.']*(W+2)] + A + [['.']*(W+2)]
# print(A)
flag = True
for i in range(1, H+2):
    for j in range(1, W+2):
        # print(i, j)
        if i == j == 1 or (i == H and j == W):
            continue
        if A[i][j] != '#':
            continue
        if sum([A[i+1][j]=='#', A[i][j+1]=='#']) == 1 \
            and sum([A[i-1][j]=='#', A[i][j-1]=='#']) == 1:
            continue
        flag = False
        break
    if not flag:
        break
if flag:
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
from collections import deque


def main():
    H, W = list(map(int, input().split()))
    A = [input() for _ in range(H)]
    # 「右or下のみ移動可」で深さ優先探索
    # 途中で、右にも下にも移動できるマスが出てきたらNG
    # ゴールに到達できなくてもNG
    que = deque()
    que.append((0, 0))
    ok = False
    while len(que) > 0:
        h, w = que.pop()
        if (h, w) == (H - 1, W - 1):
            ok = True
            break
        can_go_both = True
        for dh, dw in [(1, 0), (0, 1)]:
            next_h, next_w = h + dh, w + dw
            if next_w >= W or next_h >= H or A[next_h][next_w] == '.':
                can_go_both = False
            else:
                que.append((next_h, next_w))
        if can_go_both:
            break
    if ok:
        print('Possible')
    else:
        print('Impossible')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
A=[input() for i in range(H)]

IsPossible=True
res=[]
for y in range(H):
    left=-1
    right=0
    for x in range(W):
        if A[y][x]=='#':
            if left<0:
                left=x
                right=x
            else:
                if x-left==1:
                    right=x
                else:
                    IsPossible=False
                    break
    res.append((left,right))

for y in range(1,H):
    if res[y-1][1]!=res[y][0]:
        IsPossible=False

if IsPossible:
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]

i = 0
j = 0

while True:
    if i == h-1 and j == w-1:
        print('Possible')
        exit()
    flg = [0, 0]
    if i != h-1:
        if a[i+1][j] == '#':
            flg[0] = 1
    if j != w-1:
        if a[i][j+1] == '#':
            flg[1] = 1
    if flg == [1, 1] or flg == [0, 0]:
        print('Impossible')
        exit()
    elif flg == [1, 0]:
        i += 1
    else:
        j += 1

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]

i = 0
j = 0
prev = (0, 0)

while True:
    if i == h-1 and j == w-1:
        if a[i][j] == '#':
            print('Possible')
        else:
            print('Impossible')
        exit()
    if j != 0:
        if (i, j-1) != prev:
            if a[i][j-1] == '#':
                print('Impossible')
                exit()
    if i != 0:
        if (i-1, j) != prev:
            if a[i-1][j] == '#':
                print('Impossible')
                exit()
    if j != w-1 and a[i][j+1] == '#':
        prev = (i, j)
        j += 1
    elif i != h-1 and a[i+1][j] == '#':
        prev = (i, j)
        i += 1
    else:
        print('Impossible')
        exit()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]

i = 0
j = 0
prev = (0, 0)

while True:
    if i == h-1 and j == w-1:
        print('Possible')
        exit()
    if j != 0:
        if (i, j-1) != prev:
            if a[i][j-1] == '#':
                print('Impossible')
                exit()
    if i != 0:
        if (i-1, j) != prev:
            if a[i-1][j] == '#':
                print('Impossible')
                exit()
    if j != w-1 and a[i][j+1] == '#':
        prev = (i, j)
        j += 1
    elif i != h-1 and a[i+1][j] == '#':
        prev = (i, j)
        i += 1
    else:
        print('Impossible')
        exit()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]

i = 0
j = 0
prev = (0, 0)

while True:
    if i == h-1 and j == w-1:
        print('Possible')
        exit()
    if j != 0:
        if (i, j-1) != prev:
            if a[i][j-1] == '#':
                print('Impossible')
                exit()
    if i != 0:
        if (i-1, j) != prev:
            if a[i-1][j] == '#':
                print('Impossible')
                exit()
    if j != w-1 and a[i][j+1] == '#':
        prev = (i, j)
        j += 1
    elif i != h-1 and a[i+1][j] == '#':
        prev = (i, j)
        i += 1

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]
now = 0
ng = 0
for i in range(h):
    # print(now)
    # 限界まで伸ばせる点を探し、それより先に#がないことを確認
    extended = 0
    if a[i][now] != "#" or "#" in a[i][:now]:
        ng = 1
        break
    for j in range(now, w):
        if not extended:
            if a[i][j] == "#":
                now = j
            else:
                extended = 1
        else:
            if a[i][j] != "#":
                ng = 1
                break
        if i == h - 1 and j == w - 1 and extended == 0:
            print("Possible")
            exit()
    if ng:
        break
if ng:
    print("Impossible")

"""
while True:
    right_most = j
    bit = 0
    for k in range(w):
        if a[i][k] == "#":
            if k < j:
                print("Impossible")
                exit()
            if not bit:
                right_most = k
            else:
                print("Impossible")
                exit()
        else:
            if k > j:
                bit = 1
    j = right_most
    if i == h - 1 and j == w - 1:
        print("Possible")
        exit()
    else:
        down_most = i
        bit = 0
        for k in range(h):
            if a[k][j] == "#":
                if k < i:
                    print("Impossible")
                    exit()
                if not bit:
                    down_most = k
                else:
                    print("Impossible")
                    exit()
            else:
                if k > i:
                    bit = 1
        i = down_most
        if i >= h - 1 and j >= w - 1:
            print("Possible")
            exit()"""

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]
now = 0
ng = 0
for i in range(h):
    # print(now)
    # 限界まで伸ばせる点を探し、それより先に#がないことを確認
    extended = 0
    if a[i][now] != "#" or "#" in a[i][:now]:
        ng = 1
        break
    for j in range(now, w):
        if not extended:
            if a[i][j] == "#":
                now = j
            else:
                extended = 1
        else:
            if a[i][j] != "#":
                ng = 1
                break
        if i == h - 1 and j == w - 1 and extended == 0:
            print("Possible")
            exit()
if ng:
    print("Impossible")

"""
while True:
    right_most = j
    bit = 0
    for k in range(w):
        if a[i][k] == "#":
            if k < j:
                print("Impossible")
                exit()
            if not bit:
                right_most = k
            else:
                print("Impossible")
                exit()
        else:
            if k > j:
                bit = 1
    j = right_most
    if i == h - 1 and j == w - 1:
        print("Possible")
        exit()
    else:
        down_most = i
        bit = 0
        for k in range(h):
            if a[k][j] == "#":
                if k < i:
                    print("Impossible")
                    exit()
                if not bit:
                    down_most = k
                else:
                    print("Impossible")
                    exit()
            else:
                if k > i:
                    bit = 1
        i = down_most
        if i >= h - 1 and j >= w - 1:
            print("Possible")
            exit()"""

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
num = 0
for i in range(H):
    a = input()
    if "#" in a[:num]:
        print("Impossible")
        exit()
    cnt = -1
    for j in range(num, W):
        if a[j] == "#":
            cnt += 1
        else:break
    num += cnt
print("Possible" if num == W-1 else "Impossible")

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
num = 0
for i in range(H):
    a = input()
    if "#" in a[:num]:
        print("Impossible")
        exit()
    cnt = -1
    for j in range(num, W):
        if a[j] == "#":
            cnt += 1
        else:break
    num += cnt
print("Possible")

Submission status: Wrong Answer

Solution code:
from collections import deque
dx=[0,1]
dy=[1,0]
def bfs(x,y):
    que=deque([(x,y)])
    while(que):
        nx,ny=que.popleft()
        seen[nx][ny]=True
        if (nx+1<H-1 and G[nx+1][ny]=='#') and (ny+1<W-1 and G[nx][ny+1]=='#'):
            return False
        elif nx+1<H and G[nx+1][ny]=='#':
            que.append((nx+1,ny))
            continue
        elif ny+1<W and G[nx][ny+1]=='#':
            que.append((nx,ny+1))
            continue
        else:
            if nx==H-1 and ny==W-1:
                return True
            else:
                return False
    return True


memo={}
H,W=map(int,input().split())
G=[list(input()) for i in range(H)]
seen=[[False]*W for i in range(H)]
isok=bfs(0,0)
for i in range(H):
    for j in range(W):
        if G[i][j]=='#' and seen[i][j]==False:
            isok=False
print("Possible" if isok else "Imporssible")

Submission status: Wrong Answer

Solution code:
from collections import deque
dx=[0,1]
dy=[1,0]
def bfs(x,y):
    que=deque([(x,y)])
    while(que):
        nx,ny=que.popleft()
        if (nx+1<H-1 and G[nx+1][ny]=='#') and (ny+1<W-1 and G[nx][ny+1]=='#'):
            return False
        elif nx+1<H and G[nx+1][ny]=='#':
            que.append((nx+1,ny))
            continue
        elif ny+1<W and G[nx][ny+1]=='#':
            que.append((nx,ny+1))
            continue
        else:
            if nx==H-1 and ny==W-1:
                return True
            else:
                return False
    return True


memo={}
H,W=map(int,input().split())
G=[list(input()) for i in range(H)]

print("Possible" if bfs(0,0) else "Impossible")

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(S):  # 幅優先探索  # キュー
    que, frag = deque([S]), set([S])
    while len(que) > 0:
        p, q = que.popleft()
        cnt = 0
        for i, j in [(p + 1, q), (p, q + 1)]:  # 移動先の候補
            if (i, j) in frag or i >= h or j >= w:  # 処理済みか否か
                continue
            if a[i][j] == '#':
                cnt += 1
                que.append((i, j)), frag.add((i, j))
        if cnt == 2:
            print('Impossible')
            break
    else:
        print('Possible' if (h - 1, w - 1) in frag else 'Impossible')


h, w = map(int, input().split())
a = [input() for _ in range(h)]
bfs((0, 0))

Submission status: Wrong Answer

Solution code:
HW = [int(i) for i in input().split(' ')]
l = []
for h in range(HW[0]):
    A = []
    aa = list(input())
    for a in aa:
        A.append(a)
    l.append(A)

d = (0,0)
#右 l[d[0]][d[1]+1]
#下 l[d[0]+1][d[1]]
flag = 0
while True:
    #シュウリョウジョウケン
    if d[0] == HW[0]-1 and d[1] == HW[1]-1:
        if l[d[0]-1][d[1]] == '#' and l[d[0]][d[1]-1]== '#':
            flag = 1
            break
        else:
            break
    #一番右列
    if d[1] == HW[1]-1:
        if l[d[0]+1][d[1]] == '#':
            d = (d[0]+1,d[1])
        else:
            flag = 1
            break
    #一番下行
    elif d[0] == HW[0]-1:
        if l[d[0]][d[1]+1] == '#':
            d = (d[0],d[1]+1)
        else:
            flag = 1
            break
    else:
    #じゃないとき
        if l[d[0]][d[1]+1] == '#' and l[d[0]+1][d[1]] != '#':
            if l[d[0]][d[1]-1]== '#' and l[d[0]-1][d[1]] == '#':
                flag = 1
                break
            elif l[d[0]][d[1]-1] == '#' and  l[d[0]-1][d[1]] != '#':
                d = (d[0],d[1]+1)
            elif l[d[0]][d[1]-1] != '#' and  l[d[0]-1][d[1]] == '#':
                d = (d[0],d[1]+1)
            else:
                d = (d[0],d[1]+1)
        elif l[d[0]][d[1]+1] != '#' and l[d[0]+1][d[1]] == '#':
            if l[d[0]][d[1]-1]== '#' and l[d[0]-1][d[1]] == '#':
                flag = 1
                break
            elif l[d[0]][d[1]-1] == '#' and  l[d[0]-1][d[1]] != '#':
                d = (d[0]+1,d[1])
            elif l[d[0]][d[1]-1] != '#' and  l[d[0]-1][d[1]] == '#':
                d = (d[0]+1,d[1])
            else:
                flag = 1
                break
        elif l[d[0]][d[1]+1] == '#' and l[d[0]+1][d[1]] == '#':
            flag = 1
            break
        elif l[d[0]][d[1]+1] == '.' and l[d[0]+1][d[1]] == '.':
            flag = 1
            break
        else:
            flag = 1
            break

if flag == 1:
    print('Impossible')
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
HW = [int(i) for i in input().split(' ')]
l = []
for h in range(HW[0]):
    A = []
    aa = list(input())
    for a in aa:
        A.append(a)
    l.append(A)

d = (0,0)
#右 l[d[0]][d[1]+1]
#下 l[d[0]+1][d[1]]
flag = 0
while True:
    #シュウリョウジョウケン
    if d[0] == HW[0]-1 and d[1] == HW[1]-1:
        if l[d[0]-1][d[1]] == '#' and l[d[0]][d[1]-1]== '#':
            flag = 1
            break
        else:
            break
    #一番右列
    if d[1] == HW[1]-1:
        if l[d[0]+1][d[1]] == '#':
            d = (d[0]+1,d[1])
        else:
            flag = 1
            break
    #一番下行
    elif d[0] == HW[0]-1:
        if l[d[0]][d[1]+1] == '#':
            d = (d[0],d[1]+1)
        else:
            flag = 1
            break
    else:
    #じゃないとき
        if l[d[0]][d[1]+1] == '#' and l[d[0]+1][d[1]] != '#':
            if l[d[0]][d[1]-1]== '#' and l[d[0]-1][d[1]] == '#':
                flag = 1
                break
            else:
                d = (d[0],d[1]+1)
        elif l[d[0]][d[1]+1] != '#' and l[d[0]+1][d[1]] == '#':
            if l[d[0]][d[1]-1]== '#' and l[d[0]-1][d[1]] == '#':
                flag = 1
                break
            else:
                d = (d[0]+1,d[1])    
        elif l[d[0]][d[1]+1] == '#' and l[d[0]+1][d[1]] == '#':
            flag = 1
            break
        elif l[d[0]][d[1]+1] == '.' and l[d[0]+1][d[1]] == '.':
            flag = 1
            break
        else:
            flag = 1
            break

if flag == 1:
    print('Impossible')
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
HW = [int(i) for i in input().split(' ')]
l = []
for h in range(HW[0]):
    A = []
    aa = list(input())
    for a in aa:
        A.append(a)
    l.append(A)

d = (0,0)
#右 l[d[0]][d[1]+1]
#下 l[d[0]+1][d[1]]
flag = 0
while True:
    #シュウリョウジョウケン
    if d[0] == HW[0]-1 and d[1] == HW[1]-1:
        if l[d[0]-1][d[1]] == '#' and l[d[0]][d[1]-1]== '#':
            flag = 1
            break
        else:
            break
    #一番右列
    if d[1] == HW[1]-1:
        if l[d[0]+1][d[1]] == '#':
            d = (d[0]+1,d[1])
        else:
            flag = 1
            break
    #一番下行
    elif d[0] == HW[0]-1:
        if l[d[0]][d[1]+1] == '#':
            d = (d[0],d[1]+1)
        else:
            flag = 1
            break
    else:
    #じゃないとき
        if l[d[0]][d[1]+1] == '#' and l[d[0]+1][d[1]] != '#':
            d = (d[0],d[1]+1)
        elif l[d[0]][d[1]+1] != '#' and l[d[0]+1][d[1]] == '#':
            d = (d[0]+1,d[1])    
        elif l[d[0]][d[1]+1] == '#' and l[d[0]+1][d[1]] == '#':
            flag = 1
            break
        elif l[d[0]][d[1]+1] == '.' and l[d[0]+1][d[1]] == '.':
            flag = 1
            break
        else:
            flag = 1
            break

if flag == 1:
    print('Impossible')
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
HW = [int(i) for i in input().split(' ')]
l = []
for h in range(HW[0]):
    A = []
    aa = list(input())
    for a in aa:
        A.append(a)
    l.append(A)

d = (0,0)
#右 l[d[0]][d[1]+1]
#下 l[d[0]+1][d[1]]
flag = 0
while True:
    #シュウリョウジョウケン
    if d[0] == HW[0]-1 and d[1] == HW[1]-1:
        break
    #一番右列
    if d[1] == HW[1]-1:
        if l[d[0]+1][d[1]] == '#':
            d = (d[0]+1,d[1])
        else:
            flag = 1
            break
    #一番下行
    elif d[0] == HW[0]-1:
        if l[d[0]][d[1]+1] == '#':
            d = (d[0],d[1]+1)
        else:
            flag = 1
            break
    else:
    #じゃないとき
        if l[d[0]][d[1]+1] == '#' and l[d[0]+1][d[1]] != '#':
            d = (d[0],d[1]+1)
        elif l[d[0]][d[1]+1] != '#' and l[d[0]+1][d[1]] == '#':
            d = (d[0]+1,d[1])    
        elif l[d[0]][d[1]+1] == '#' and l[d[0]+1][d[1]] == '#':
            flag = 1
            break
        elif l[d[0]][d[1]+1] == '.' and l[d[0]+1][d[1]] == '.':
            flag = 1
            break
        else:
            flag = 1
            break

if flag == 1:
    print('Impossible')
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
HW = [int(i) for i in input().split(' ')]
l = []
for h in range(HW[0]):
    A = []
    aa = list(input())
    for a in aa:
        A.append(a)
    l.append(A)

d = (0,0)
#右 l[d[0]][d[1]+1]
#下 l[d[0]+1][d[1]]
flag = 0
while True:
    #シュウリョウジョウケン
    if d[0] == HW[0]-1 and d[1] == HW[1]-1:
        break
    #一番右列
    if d[1] == HW[1]-1:
        if l[d[0]+1][d[1]] == '#':
            d = (d[0]+1,d[1])
        else:
            flag = 1
            break
    #一番下行
    elif d[0] == HW[0]-1:
        if l[d[0]][d[1]+1] == '#':
            d = (d[0],d[1]+1)
        else:
            flag = 1
            break
    else:
    #じゃないとき
        if l[d[0]][d[1]+1] == '#' and l[d[0]+1][d[1]] != '#':
            d = (d[0],d[1]+1)
        elif l[d[0]][d[1]+1] != '#' and l[d[0]+1][d[1]] == '#':
            d = (d[0]+1,d[1])    
        else:
            flag = 1
            break

if flag == 1:
    print('Impossible')
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
HW = [int(i) for i in input().split(' ')]
l = []
for h in range(HW[0]):
    A = []
    aa = list(input())
    for a in aa:
        A.append(a)
    l.append(A)

d = (0,0)
#右 l[d[0]][d[1]+1]
#下 l[d[0]+1][d[1]]
flag = 0
while True:
    #シュウリョウジョウケン
    if d[0] == HW[0]-1 and d[1] == HW[1]-1:
        break
    #一番右列
    if d[1] == HW[1]-1:
        if l[d[0]+1][d[1]] == '#':
            d = (d[0]+1,d[1])
        else:
            flag = 1
            break
    #一番下行
    elif d[0] == HW[0]-1:
        if l[d[0]][d[1]+1] == '#':
            d = (d[0],d[1]+1)
        else:
            flag = 1
            break
    else:
    #じゃないとき
        if (l[d[0]][d[1]+1] == '#' and l[d[0]+1][d[1]] != '#') or (l[d[0]][d[1]+1] != '#' and l[d[0]+1][d[1]] == '#'):
            if l[d[0]][d[1]+1] == '#':
                d = (d[0],d[1]+1)
            elif l[d[0]+1][d[1]] == '#':
                d = (d[0]+1,d[1])
        else:
            flag = 1
            break

if flag == 1:
    print('Impossible')
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
field = []
check = [[False for _ in range(w)] for _ in range(h)]
for i in range(h):
    s = list(input().strip())
    field.append(s)

sx, sy = 0, 0
d = deque()
dirx = [0, 1, 0, -1]
diry = [1, 0, -1, 0]
d.append([sx, sy])
# 離れ島がないかのチェック
while (d):
    nowx, nowy = d.popleft()
    check[nowx][nowy] = True
    for x, y in zip(dirx, diry):
        nx = nowx + x
        ny = nowy + y
        if nx in range(h) and ny in range(w) and (
                not check[nx][ny]) and field[nx][ny] == '#':
            d.append([nx, ny])
for i in range(h):
    for j in range(w):
        if not check[i][j] and field[i][j] == '#':
            print('Impossible')
            exit()

# 右or下のみの最短でいけるかチェック
d.append([sx, sy])
check = [[False for _ in range(w)] for _ in range(h)]
while (d):
    nowx, nowy = d.pop()
    for x, y in zip(dirx[0:2], diry[0:2]):
        nx = nowx + x
        ny = nowy + y
        if nx in range(h) and ny in range(w) and field[nx][ny] == '#':
            d.append([nx, ny])
            check[nx][ny] = True
    for x, y in zip(dirx[2:4], diry[2:4]):
        nx = nowx + x
        ny = nowy + y
        if nx in range(h) and ny in range(
                w) and field[nx][ny] == '#' and not check[nx][ny]:
            print('Impossible')
            exit()

    if len(d) == 2:
        print('Impossible')
        exit()
    if nowx == h - 1 and nowy == w - 1:
        print('Possible')
        exit()

print('Impossible')

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
field = []
check = [[False for _ in range(w)] for _ in range(h)]
for i in range(h):
    s = list(input().strip())
    field.append(s)

sx, sy = 0, 0
d = deque()
dirx = [0, 1, 0, -1]
diry = [1, 0, -1, 0]
d.append([sx, sy])
# 離れ島がないかのチェック
while (d):
    nowx, nowy = d.popleft()
    check[nowx][nowy] = True
    for x, y in zip(dirx, diry):
        nx = nowx + x
        ny = nowy + y
        if nx in range(h) and ny in range(w) and (
                not check[nx][ny]) and field[nx][ny] == '#':
            d.append([nx, ny])
for i in range(h):
    for j in range(w):
        if not check[i][j] and field[i][j] == '#':
            print('Impossible')
            exit()

# 右or下のみの最短でいけるかチェック
d.append([sx, sy])
while (d):
    nowx, nowy = d.pop()
    for x, y in zip(dirx[0:2], diry[0:2]):
        nx = nowx + x
        ny = nowy + y
        if nx in range(h) and ny in range(w) and field[nx][ny] == '#':
            d.append([nx, ny])

    if len(d) == 2:
        print('Impossible')
        exit()
    if nowx == h - 1 and nowy == w - 1:
        print('Possible')
        exit()

print('Impossible')

Submission status: Wrong Answer

Solution code:
h, w =list(map(int, input().split())) 
mat = []
for i in range(h):
    s = input()
    mat.append([s[x] for x in range(w)])

flag = True
for i in range(h-1):
    for j in range(w-1):
        if mat[i][j] == '#':
            if( (mat[i+1][j]=='#')& (mat[i][j+1]=='#') ):
                flag = False
def mycheck(mat, h, w, i, j):
    ret = False
    if( (0<=i)&(i<h) ):
        if( (0<=j)&(j<w) ):
            if(mat[i][j] == '#' ):            
                ret = True
    return ret

#飛び地検知

for i in range(h):
    for j in range(w):
        if mat[i][j] == '#':
            n = sum([mycheck(mat, h, w, i-1, j-1),
                mycheck(mat, h, w, i-1, j),
                mycheck(mat, h, w, i-1, j+1),
                mycheck(mat, h, w, i, j-1),
                mycheck(mat, h, w, i, j+1),
                mycheck(mat, h, w, i+1, j-1),
                mycheck(mat, h, w, i+1, j),
                mycheck(mat, h, w, i+1, j+1)
                ])
            if(n == 0):
                ret = False


if flag :
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
H,W=map(int, input().split())
a = [input() for i in range(H)]

ans=0
cnt=0

for i in range(H-1):
    for j in range(W-1):
        if a[i][j] == '#' and a[i+1][j] == '#' and  a[i][j+1] == '#':
            cnt+=1
        elif a[i][j] == '#' and a[i+1][j] == '.' and  a[i][j+1] == '.':
            cnt+=1
        else:
            continue
print('Impossible' if cnt>0 else 'Possible')

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
mat_a = [ list(input()) for _ in range(h) ]

def check(i,j):
    if mat_a[i][j] == '.':
        return True

    count = 0
    try:
        if mat_a[i][j-1] == '#':
            count += 1
    except:
        pass

    try:
        if mat_a[i-1][j] == '#':
            count += 1
    except:
        pass

    try:
        if mat_a[i][j+1] == '#':
            count += 1
    except:
        pass

    try:
        if mat_a[i+1][j] == '#':
            count += 1
    except:
        pass

    if count == 2 or count == 4:
        return True
    else:
        return False    


ans = True
for i in range(h):
    for j in range(w):
        if not check(i,j):
            if i+1 == h and j+1 == w:
                continue
            if i == 0 and j == 0:
                continue
            ans = False
            break

if ans:
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
H,W=map(int, input().split())
a = [input() for i in range(H)]

ans=0
cnt=0

for i in range(H-1):
    for j in range(W-1):
        if a[i][j] == '#' and a[i+1][j] == '#' and  a[i][j+1] == '#':
            cnt+=1
            break
        elif a[i][j] == '#' and a[i+1][j] == '.' and  a[i][j+1] == '.':
            cnt+=1
            break
        else:
            continue

print('Impossible' if cnt>0 else 'Possible')

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
mat_a = [ list(input()) for _ in range(h) ]


ans = 'Possible'
ans = 'Impossible'

def check(i,j):
    if mat_a[i][j] == '.':
        return True

    count = 0
    try:
        if mat_a[i][j-1] == '#':
            count += 1
    except:
        pass

    try:
        if mat_a[i-1][j] == '#':
            count += 1
    except:
        pass

    try:
        if mat_a[i][j+1] == '#':
            count += 1
    except:
        pass

    try:
        if mat_a[i+1][j] == '#':
            count += 1
    except:
        pass

    if count == 2 or count ==4:
        return True
    else:
        return False    


ans = True
for i in range(h):
    for j in range(w):
        if not check(i,j):
            if i+1 == h and j+1 == w:
                continue
            if i == 0 and j == 0:
                continue
            ans = False
            break

if ans:
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
mat_a = [ list(input()) for _ in range(h) ]


ans = 'Possible'
ans = 'Impossible'

def check(i,j):
    if mat_a[i][j] == '.':
        return True

    b_fg = False
    a_fg = False
    try:
        if mat_a[i][j-1] == '#':
            b_fg = True
    except:
        pass

    try:
        if mat_a[i-1][j] == '#':
            if b_fg:
                b_fg = False
            else:
                b_fg = True
    except:
        pass

    try:
        if mat_a[i][j+1] == '#':
            a_fg = True
    except:
        pass

    try:
        if mat_a[i+1][j] == '#':
            if a_fg:
                a_fg = False
            else:
                a_fg = True
    except:
        pass
    
    if a_fg and b_fg:
        return True
    else:
        return False


ans = True
for i in range(h):
    for j in range(w):
        if not check(i,j):
            if i+1 == h and j+1 == w:
                continue
            if i == 0 and j == 0:
                continue
            ans = False
            break

if ans:
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
h, w =list(map(int, input().split())) 
mat = []
for i in range(h):
    s = input()
    mat.append([s[x] for x in range(w)])

flag = True
for i in range(h-1):
    for j in range(w-1):
        if mat[i][j] == '#':
            if( (mat[i+1][j]=='#')& (mat[i][j+1]=='#') ):
                flag = False
if flag :
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
mat_a = [ list(input()) for _ in range(h) ]


ans = 'Possible'
ans = 'Impossible'

def check(i,j):
    if mat_a[i][j] == '.':
        return True

    b_fg = False
    a_fg = False
    try:
        if mat_a[i][j-1] == '#':
            b_fg = True
    except:
        pass

    try:
        if mat_a[i-1][j] == '#':
            if b_fg:
                b_fg = False
            else:
                b_fg = True
    except:
        pass

    try:
        if mat_a[i][j+1] == '#':
            a_fg = True
    except:
        pass

    try:
        if mat_a[i+1][j] == '#':
            if a_fg:
                a_fg = False
            else:
                a_fg = True
    except:
        pass
    
    if a_fg and b_fg:
        return True
    elif a_fg == False and b_fg == False:
        return True
    else:
        return False


ans = True
for i in range(h):
    for j in range(w):
        if not check(i,j):
            if i+1 == h and j+1 == w:
                continue
            if i == 0 and j == 0:
                continue
            ans = False
            break

if ans:
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
ban = [list(input()) for _ in range(H)]
cnt = 0
for i in range(H):
    cnt = ban[i].count("#")
if cnt == H + W - 1:
    print("Possible")
else:
    print("Impossible")