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 = map(int, input().split())
al = [input() for _ in range(h)]

for hi in range(h-1):
    for wi in range(w-1):
        if al[hi][wi]==al[hi+1][wi]==al[hi][wi+1]=="#":
            print("Impossible")
            exit()

hi,wi = 0,0
while True:
    if hi+1<h and al[hi+1][wi]=="#":
        hi += 1
    elif wi+1<w and al[hi][wi+1]=="#":
        wi += 1
    else:
        print("Impossible")
        exit()
    
    if hi==h-1 and wi==w-1:
        break

print("Possible")

Submission status: Wrong Answer

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

for hi in range(h-1):
    for wi in range(w-1):
        if al[hi][wi]==al[hi+1][wi]==al[hi][wi+1]==al[hi+1][wi+1]=="#":
            print("Impossible")
            exit()

hi,wi = 0,0
while hi<h and wi<w:
    if hi+1<h and al[hi+1][wi]=="#":
        hi += 1
    elif wi+1<w and al[hi][wi+1]=="#":
        wi += 1
    else:
        print("Impossible")
        exit()
    
    if hi==h-1 and wi==w-1:
        break

print("Possible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = ['.'*(w+2)]
for _ in range(h):
  a.append('.' + input() + '.')
a.append('.'*(w+2))
ans = 'Possible'
for i in range(1,h+1):
  for j in range(1,w+1):
    if a[i][j] == '#':
      right = a[i][j+1]
      below = a[i+1][j]
      if (right=='#' and below!='#') or (right!='#' and below=='#'):
        continue
      else:
        if i == h and j == w:
          continue
        else:
          ans = 'Impossible'
          break
print(ans)

Submission status: Wrong Answer

Solution code:
# AGC 007: A – Shik and Stone
H, W = [int(s) for s in input().split()]
A = [input() for _ in range(H)]

isExact = 'Possible'

i, j = 0, 0

while i < H - 1 and j < W - 1:
    A[i] = A[i][:j] + '.' + A[i][j + 1:]

    if (i + 1 < H and A[i + 1][j] != '#') and (j + 1 < W and A[i][j + 1] != '#'):
        isExact = 'Impossible'
        break
    if j + 1 < W and A[i][j + 1] == '#':
        j += 1
    elif i + 1 < H and A[i + 1][j] == '#':
        i += 1

if isExact == 'Possible':
    A[H - 1] = A[H - 1][:W - 1] + '.'

    for line in A:
        if '#' in line:
            isExact = 'Impossible'
            break

print(isExact)

Submission status: Wrong Answer

Solution code:
# AGC 007: A – Shik and Stone
H, W = [int(s) for s in input().split()]
A = [input() for _ in range(H)]

isExact = 'Possible'

i, j = 0, 0

while i < H - 1 and j < W - 1:
    A[i] = A[i][:j] + '.' + A[i][j + 1:]

    print(i, j)

    if (i + 1 < H and A[i + 1][j] != '#') and (j + 1 < W and A[i][j + 1] != '#'):
        isExact = 'Impossible'
        break
    if j + 1 < W and A[i][j + 1] == '#':
        j += 1
    elif i + 1 < H and A[i + 1][j] == '#':
        i += 1

if isExact == 'Possible':
    A[H - 1] = A[H - 1][:W - 1] + '.'

    for line in A:
        if '#' in line:
            isExact = 'Impossible'
            break

print(isExact)

Submission status: Wrong Answer

Solution code:
# AGC 007: A – Shik and Stone
H, W = [int(s) for s in input().split()]
A = [input() for _ in range(H)]

isExact = 'Possible'

i, j = 0, 0

while i < H - 1 or j < W - 1:
    A[i] = A[i][:j] + '.' + A[i][j + 1:]

    if (i - 1 > 0 and A[i - 1][j] == '#') or (j - 1 > 0 and A[i][j - 1] == '#'):
        isExact = 'Impossible'
        break
    elif j + 1 < W and A[i][j + 1] == '#':
        j += 1
    elif i + 1 < H and A[i + 1][j] == '#':
        i += 1

print(isExact)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [input() for _ in range(H)]
A = [a+'.' for a in A]
A.append(['.']*W)

i=j=0
flg=False
while True:
    if (A[i][j+1]=='#' and A[i+1][j]=='.'):
        j += 1
    elif (A[i][j+1]=='.' and A[i+1][j]=='#'):
        i += 1
    else:
        break
    
    if i==H-1 and j==W-1:
        flg=True
        break

ans = 'Possible' if flg else 'Impossible'
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = [input() for i in range(H)]
ans = 'Possible'
for i in range(H):
    for j in range(W):
        if i == H-1 and j == W-1:
            continue
        if A[i][j] == '#':
            c = 0
            if i+1 <= H-1 and A[i+1][j] == '#':
                c += 1
            if j+1 <= W-1 and A[i][j+1] == '#':
                c += 1
            if c != 1:
                ans = 'Impossible'
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = [input() for i in range(H)]
ans = 'Possible'
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] == '#':
            ans = 'Impossible'
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'.'
    a=list(a)
    for i in a:
        if i == '#':
            count += 1
    ab.append(a)
ab.append(list('.'*w))

if count != h*2:
    print('Impossible')
    exit()
            
step = [[0, 0]]
 
while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print('Possible')
        exit()
    if ab[y+1][x] == '#' :
        step.append([y+1, x])
    if ab[y][x+1] == '#' :
        step.append([y, x+1])

print('Impossible')

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
c = [input() for _ in range(H)]
dist = [[-1]*W for _ in range(H)]

now = 0
for h in range(H):
    if c[h][now]!="#":
        print("Impossible")
        exit()
    for w in range(now,W):
        if c[h][w]==".":
            now = w-1
            break
        else:
            dist[h][w]=0

for h in range(H):
    for w in range(W):
        if c[h][w]=="#" and dist[h][w]==-1:
            print("Impossible")
            exit()
            
if c[H-1][W-1]=="#":
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
c = [input() for _ in range(H)]
dist = [[-1]*W for _ in range(H)]

now = 0
for h in range(H):
    if c[h][now]!="#":
        print("Impossible")
        exit()
    for w in range(now,W):
        if c[h][w]==".":
            now = w-1
            break
        else:
            dist[h][w]=0

for h in range(H):
    for w in range(W):
        if c[h][w]=="#" and dist[h][w]==-1:
            print("Impossible")
            exit()
print("Possible")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    count = 0
    for row in list(input().rstrip()):
        count += row.count("#")
    if count == H + W - 1:
        print("Possible")
    else:
        print("Impossible")

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for _ in range(H)]
    parx = -1
    pary = -1
    x = 0
    y = 0
    while x != H-1 or y != W-1:
        if x - 1 >= 0:
            if x-1 != parx and A[x-1][y] == "#":
                print("Impossible")
                sys.exit()
        if y - 1 >= 0:
            if y-1 != pary and A[x][y-1] == "#":
                print("Impossible")
                sys.exit()
        if x + 1 <= H - 1:
            if A[x+1][y] == "#":
                parx = x
                pary = y
                x = x + 1
                continue
        if y + 1 <= W - 1:
            if A[x][y+1] == "#":
                parx = x
                pary = y
                y = y + 1
                continue
    print("Possible")
            
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
h,w = map(int,input().split())
A = [list(input()) for i in range(h)]
que = collections.deque()
que.append((0,0))
while que:
  i,j = que.popleft()
  A[i][j] = "."
  if 0 <= i+1 < h:
    if A[i+1][j] == "#":
      que.append((i+1,j))
  continue
  if 0 <= j + 1 < w:
    if A[i][j+1] == "#":
      que.append((i,j+1))
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      print("Impossible")
      exit()
print("Possible")
# print(*A,sep="\n")

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W=map(int, input().split())
A=[]
for i in range(H):
    a=list(input())
    A.append(a)

A=np.array(A)
ok=True
for h in range(H):
    for w in range(W):
        if h==0 and w==0:
            continue
        lu=0
        rd=0
        if A[h,w]=="#":
            if 0<=h-1 and h-1<H:
                if A[h-1,w]=="#":
                    lu+=1
            if 0<=w-1 and w-1<W:
                if A[h,w-1]=="#":
                    lu+=1
            if lu!=1:
                ok=False
if ok:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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

i = j = 0

def dp(i, j):
    global H, W
    if i == H - 1 and j == W - 1: return True
    #
    if i + 1 >= H:
        d = False
    else:
        d = (A[i + 1][j] == '#')
    #
    if j + 1 >= W:
        r = False
    else:
        r = (A[i][j + 1] == '#')
    #
    if d and not r:
        return dp(i + 1, j)
    elif not d and r:
        return dp(i, j + 1)
    else:
        return False

if dp(0, 0):
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
*t,=open(0)
print(["Imp", "P"][int(t[0][0])+int(t[0][2])-1==sum(s.count("#")for s in t[1:])]+"oosible")

Submission status: Wrong Answer

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

ans = True
h = 0
w = 0
while (ans) and not (h == H - 1 and w == W - 1):
    if h == H - 1:
        if A[h][w + 1] == '.':
            ans = False
        else:
            w += 1
    elif w == W - 1:
        if A[h + 1][w] == '.':
            ans = False
        else:
            h += 1
    else:
        sh = A[h + 1][w]
        sw = A[h][w + 1]
        if sh == '#' and sw == '#':
            ans = False
        elif sh == '.' and sw == '.':
            ans = False
        elif sh == '#' and sw == '.':
            h += 1
        else:
            w += 1

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

Submission status: Wrong Answer

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

ans = True
for i in range(0, H):
    for j in range(0, W):
        if A[i][j] == '.' or (i == H - 1 and j == W - 1):
            continue
        s1 = '.'
        s2 = '.'
        if i < H - 1:
            s1 = A[i + 1][j]
        if j < W - 1:
            s2 = A[i][j + 1]
        if (s1 == '.' and s2 == '#') or (s1 == '#' and s2 == '.'):
            continue
        else:
            ans = False
            break

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
sum = 0
for i in range(h):
    a = input()
    sum += a.count('#')
if sum == h + w - 1:
    print("Possible")
else:
    print("impossible")

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
f = [input()for _ in range(h)]
res = 0
for  i in range(h):
    res += f[i].count('#')
if res  == h+w-1:print('Yes')
else:print('No')

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
field = [input()for _ in range(h)]
vec = [(1,0),(0,1),(-1,0),(0,-1)]
stack = [(0,0)]
visited = [[0]*w for i in range(h)]
ok = True
while stack:
    next = []
    for x,y in stack:
        cnt = 0
       
        for tx,ty in vec:
            nx = x+tx
            ny = y +ty
            if nx > h-1 or ny > w-1 or nx <0 or ny < 0:continue
            if visited[nx][ny] :continue
            if (not visited[nx][ny]) and (x < nx or y < ny):
                ok = False
                break
            visited[nx][ny] = 1
            if field[nx][ny] == '#':
                cnt+=1
                next.append((nx,ny))
            
        if cnt == 2:
            ok = False
            break
    stack = next
if not (x ==h-1 and y == w-1):ok = False
if ok :print('Possible')
else:print('Impossible')

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
field = [input()for _ in range(h)]
vec = [(1,0),(0,1)]
stack = [(0,0)]
ok = True
while stack:
    next = []
    for x,y in stack:
        cnt = 0
       
        for tx,ty in vec:
            nx = x+tx
            ny = y +ty
            if nx > h-1 or ny > w-1:continue
            if field[nx][ny] == '#':
                cnt+=1
                next.append((nx,ny))
        if (x != h-1 or y!= w-1) and cnt%2 == 0:
            ok = False
            break
    stack = next
if not (x ==h-1 and y == w-1):ok = False
if ok :print('Possible')
else:print('Impossible')

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
field = [input()for _ in range(h)]
vec = [(1,0),(0,1)]
stack = [(0,0)]
ok = True
while stack:
    next = []
    for x,y in stack:
        cnt = 0
       
        for tx,ty in vec:
            nx = x+tx
            ny = y +ty
            if nx > h-1 or ny > w-1:continue
            if field[nx][ny] == '#':
                cnt+=1
                next.append((nx,ny))
        if cnt%2 == 0:
            ok = False
            break
    stack = next
if not (x ==h-1 and y == w-1):ok = False
if ok :print('Possible')
else:print('Impossible')

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
field = [input()for _ in range(h)]
vec = [(1,0),(0,1)]
stack = [(0,0)]
ok = True
while stack:
    next = []
    for x,y in stack:
        cnt = 0
       
        for tx,ty in vec:
            nx = x+tx
            ny = y +ty
            if nx > h-1 or ny > w-1:continue
            if field[nx][ny] == '#':
                cnt+=1
                next.append((nx,ny))
        if cnt == 2:
            ok = False
            break
    stack = next
if not (x ==h-1 and y == w-1):ok = False
if ok :print('Possible')
else:print('Impossible')

Submission status: Wrong Answer

Solution code:

def dfs(x, y): 
    if x == h-1 and y == w-1:
        a[x][y] = "."
        # print(a)
        for i in range(h):
            if "#" in a[i]:
                print("Impossible")
                exit()
        print("Possible")
        exit()
    
    if a[x][y] == "#":
        a[x][y] = "."

    if y+1 < w and a[x][y+1] != ".":
        dfs(x, y+1)#右
    
    if x+1 < h and a[x+1][y] != ".":
        dfs(x+1, y)#下

h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(list(input()))

dfs(0, 0)

# print(a)

for i in range(h):
    if "#" in a[i]:
        print("Impossible")
        exit()
print("Possible")

Submission status: Wrong Answer

Solution code:

def dfs(x, y): 
    if x == h-1 and y == w-1:
        a[x][y] = "."
        print(a)
        for i in range(h):
            if "#" in a[i]:
                print("Impossible")
                exit()
        print("Possible")
        exit()
    
    if a[x][y] == "#":
        a[x][y] = "."

    if y+1 < w and a[x][y+1] != ".":
        dfs(x, y+1)#右
    
    if x+1 < h and a[x+1][y] != ".":
        dfs(x+1, y)#下

h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(list(input()))

dfs(0, 0)

print(a)

for i in range(h):
    if "#" in a[i]:
        print("Impossible")
        exit()
print("Possible")

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
cnt=0
for h in range(h):
    for w in range(w):
        if a[h][w] == "#":
            cnt += 1
if cnt == h+w-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [['.'] + [c for c in input()] + ['.'] for _ in range(H)]
A = [['.']*(W+2)] + A + [['.']*(W+2)]

x, y = 1, 1
goal = [H, W]

def printA(A):
    for r in A:
        print(''.join(r))

while [x, y] != goal:
    A[x][y] = 'f'
    #printA(A)
    #print()
    if A[x-1][y]=='#' or A[x][y-1]=='#':
        print('Impossible')
        exit()
    elif A[x+1][y]=='#' and A[x][y+1]=='#':
        print('Impossible')
        exit()
    elif A[x+1][y]=='#':
        x +=1
    else:
        y += 1

print('Possible')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

visited = [[False for _ in range(W)] for _ in range(H)] 

def dfs(h, w):
    # print(h, w)
    if h == 0 and w == 0:
        visited[h][w] = True
        return True
    elif h == 0 and w > 0:
        if A[h][w] == '.':
            return False
        else:
            visited[h][w] = True
            return dfs(h, w - 1)
    elif h > 0 and w == 0:
        if A[h][w] == '.':
            return False
        else:
            visited[h][w] = True
            return dfs(h - 1, w)
    else:
        if A[h][w] == '.':
            return False
        else:
            visited[h][w] = True
            return dfs(h - 1, w) or dfs(h, w - 1)

flag = dfs(H - 1, W - 1)
if flag:
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' and not visited[h][w]:
                print("Impossible")
                exit()
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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

A = []

for i in range(h):
    B = list(input())
    B.append('.')
    A.append(B)
A.append(['.'] * (w + 1))


x = 0
y = 0
ans = 0
for j in range(h+w):
    if A[x][y] == '#':
        if A[x][y+1] == '#' and A[x+1][y] == '#':
            print("Impossible")
            ans = 1
            break
        else:
            if A[x][y+1] == '#':
                y += 1
            elif A[x+1][y] == '#':
                x += 1
    else:
        print("Impossible")
        ans = 1
        break
    if x == h-1 and y == w-1:
        print("Possible")
        ans = 1
        break

if ans == 0:
    print("Impossible")

Submission status: Wrong Answer

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

A = []

for i in range(h):
    B = list(input())
    B.append('.')
    A.append(B)
A.append(['.'] * (w + 1))


x = 0
y = 0
ans = 0
for j in range(h+w):
    if A[x][y] == '#':
        if A[x][y+1] == '#' and A[x+1][y] == '#':
            print("Impossible")
            ans = 1
            break
        else:
            if A[x][y+1] == '#':
                y += 1
            elif A[x+1][y] == '#':
                x += 1
    if x == h-1 and y == w-1:
        print("Possible")
        ans = 1
        break

if ans == 0:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
H, W = map(int, input().split())
grid = [input() for _ in range(H)]
dx = [1,0]
dy = [0,1]
seen = [[False for _ in range(W)] for _ in range(H)]
def dfs(h,w):
    seen[h][w] = True
    for i in range(2):
        nh = h + dy[i]
        nw = w + dx[i]
        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if grid[nh][nw] == '.':
            continue
        if seen[nh][nw]:
            continue
        dfs(nh,nw)
dfs(0,0)
for h in range(H):
    for w in range(W):
        if seen[h][w] == False and grid[h][w] == '#':
            print('Impossible')
            exit()
print('Possible')

Submission status: Wrong Answer

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

if H + W == sum(a.count('#') for a in A):
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
h, w = map(int,input().split())
a = [list(input()) for _ in range(h)]

#print(a)
i = 0
j = 0
ans = "Possible"
while i < h - 1 or j < w - 1:
    flag1 = [False for _ in range(2)]
    flag2 = [False for _ in range(2)]
    #print(i, j+1)
    #print(a)
    #print(a[i][j+1])
    if i == 0 and j == 0:
        flag2[0] = True
    if i + 1 < h and a[i + 1][j] == '#':
        flag1[0] = True
    if j + 1 < w and a[i][j + 1] == '#':
        flag1[1] = True
    if i - 1 >= 0 and a[i - 1][j] == '#':
        flag2[0] = True
    if j - 1 >= 0 and a[i][j - 1] == '#':
        flag2[1] = True
    #print(flag1, flag2)
    if len(set(flag1)) == 2 and len(set(flag2)) == 2:
        if flag1[0]:
            i += 1
        if flag1[1]:
            j += 1
    else :
        ans = "Impossible"
        break
if a[h - 2][j - 1] == '#' and a[h - 1][j - 2] == '#':
    ans = "Impossible"
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
h, w = map(int,input().split())
a = [list(input()) for _ in range(h)]

#print(a)
i = 0
j = 0
ans = "Possible"
while i < h - 1 or j < w - 1:
    flag1 = [False for _ in range(2)]
    flag2 = [False for _ in range(2)]
    #print(i, j+1)
    #print(a)
    #print(a[i][j+1])
    if i == 0 and j == 0:
        flag2[0] = True
    if i + 1 < h and a[i + 1][j] == '#':
        flag1[0] = True
    if j + 1 < w and a[i][j + 1] == '#':
        flag1[1] = True
    if i - 1 >= 0 and a[i - 1][j] == '#':
        flag2[0] = True
    if j - 1 >= 0 and a[i][j - 1] == '#':
        flag2[1] = True
    #print(flag1, flag2)
    if len(set(flag1)) == 2 and len(set(flag2)) == 2:
        if flag1[0]:
            i += 1
        if flag1[1]:
            j += 1
    else :
        ans = "Impossible"
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
a = [[1 if i == '#' else 0 for i in STR()] for _ in range(h)]
s = 0
for i in range(h):
    s += sum(a[i])
if s != h + w:
    print('Impossible')
    exit()
y = 0
x = 0
while y < h - 1 or x < w - 1:
    flag1 = False
    flag2 = False
    if y + 1 < h and a[y + 1][x] == 1:
        flag1 = True
    if x + 1 < w and a[y][x + 1] == 1:
        flag2 = True
    if (flag1 and flag2) or (not flag1 and not flag2):
        print('Impossible')
        exit()
    if flag1:
        y += 1
    if flag2:
        x += 1
print('Possible')

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
a = [STR() for _ in range(h)]
y = 0
x = 0
if a[h - 1][w - 1] != '#':
    print('Impossible')
    exit()
while y < h - 1 or x < w - 1:
    flag1 = False
    flag2 = False
    if y + 1 < h and a[y + 1][x] == '#':
        flag1 = True
    if x + 1 < w and a[y][x + 1] == '#':
        flag2 = True
    if (flag1 and flag2) or (not flag1 and not flag2):
        print('Impossible')
        exit()
    if flag1:
        y += 1
    if flag2:
        x += 1
print('Possible')

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
a = [STR() for _ in range(h)]
y = 0
x = 0
while y < h - 1 or x < w - 1:
    flag1 = False
    flag2 = False
    if y + 1 < h and a[y + 1][x] == '#':
        flag1 = True
    if x + 1 < w and a[y][x + 1] == '#':
        flag2 = True
    if (flag1 and flag2) or (not flag1 and not flag2):
        print('Impossible')
        exit()
    if flag1:
        y += 1
    if flag2:
        x += 1
print('Possible')

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
a = [STR() for _ in range(h)]
y = 0
x = 0
while y < h or x < w:
    flag1 = False
    flag2 = False
    if y + 1 < h and a[y + 1][x] == '#':
        flag1 = True
    if x + 1 < w and a[y][x + 1] == '#':
        flag2 = True
    if (flag1 and flag2) or (not flag1 and not flag2):
        print('Impossible')
        exit()
    if flag1:
        y += 1
    if flag2:
        x += 1
print('Possible')

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
a = [[1 if i == '#' else 0 for i in STR()] for _ in range(h)]
y = 0
x = 0
while y < h and x < w:
    flag1 = False
    flag2 = False
    if y + 1 < h and a[y + 1][x] == 1:
        flag1 = True
    if x + 1 < w and a[y][x + 1] == 1:
        flag2 = True
    if (flag1 and flag2) or (not flag1 and not flag2):
        print('Impossible')
        exit()
    if flag1:
        y += 1
    if flag2:
        x += 1
print('Possible')

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
a = [[1 if i == '#' else 0 for i in STR()] for _ in range(h)]
y = 0
x = 0
while y < h and x < w:
    flag1 = False
    flag2 = False
    if y + 1 < h and a[y + 1][x] == 1:
        flag1 = True
    if x + 1 < w and a[y][x + 1] == 1:
        flag2 = True
    if flag1 and flag2 or not flag1 and not flag2:
        print('Impossible')
        exit()
    if flag1:
        y += 1
    if flag2:
        x += 1
print('Possible')

Submission status: Wrong Answer

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

ans = 0
for i in range(H):
  ans += A[i].count("#")
print("Possible" if ans == H * 2 else "Impossible")