Problem:
 Score : 200 points    Problem Statement  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

Solution (Python):
h,w=map(int,input().split())
a=[]
for i in range(h):
  at=list(str(input()))
  a.append(at)
i=0
j=0
t=0
while True:
  if j!=w-1:
    if a[i][j+1]=="
      for k in range(i+1,h):
        if a[k][j]=="
          t=1
          break
      else:
        j=j+1
  if i!=h-1:
    if a[i+1][j]=="
      for k in range(j+1,w):
        if a[i][k]=="
          t=1
          break
      else:
        i=i+1
  if t==1:
    print("Impossible")
    break
  elif i==h-1 and j==w-1:
    print("Possible")
    break

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = map(int, input().split())
a = [None]*h
for i in range(h):
    a[i] = input()
cx = 0
cy = 0
d = set()
while (cx,cy)!=(h-1, w-1):
    val = 0

    for dx, dy in [(1,0), (0,1)]:
        ccx = cx+dx
        ccy = cy+dy
        if ccx>=h or ccy>=w or a[ccx][ccy]==".":
            continue
        nx, ny = ccx, ccy
        val += 1
    if val>=2 or val==0:
        ans = "Impossible"
        break
    cx, cy = nx, ny
else:
    vv = sum(sum(item=="
    if vv==h+w-1:
        ans = "Possible"
    else:
        ans = "Impossible"
print(ans)

Solution (Python):
h, w = map(int, input().split())
count = 0
for i in range(h):
    a = input()
    for char in a:
        if char == '
            count += 1
print('Possible' if count == h + w - 1 else 'Impossible')

Solution (Python):
h, w = map(int, input().split())
area = [[] for i in range(h)]

for i in range(h):
    area[i] = input()
num = 0

for i in range(h):
    for j in range(w):
        if area[i][j] == '
            print('Impossible')
            exit()
        elif area[i][j] == '
            num = j

print('Possible')

Solution (Python):
h,w=map(int, input().split())
s=[list(input()) for _ in range(h)]
c=0
for i in range(h):
  for j in range(w):
    if s[i][j]=="
      c+=1
if c==h+w-1:
  print("Possible")
else:
  print("Impossible")

Solution (Python):
h, w = map(int, input().split())
fld = ''.join([input()for _ in range(h)])
if fld.count('
    print('Possible')
else:
    print('Impossible')

Solution (Python):
h,w = map(int,input().split())
a = [input() for _ in range(h)]
b = 0
check = True
for i in range(h):
  for j in range(w):
    if b == j:
      if a[i][j] == ".":
        check = False
    elif b+1 == j:
      if a[i][j] == "
        b = j
    else:
      if a[i][j] == "
        check = False
  if not check:
    break
if check:
  print("Possible")
else:
  print("Impossible")

Solution (Python):
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
a = [input()+'.' for i in range(h)]
a.append("."*(w+1))
i = j = 0
b = [['.']*(w+1) for i in range(h+1)]

if a[0][0] == '.':
        print("Impossible")
        exit()
else:
        while i < h or j < w:
                b[i][j] = '
 
                if a[i][j] == a[i+1][j] == a[i][j+1] == a[i+1][j+1] == '
                        print("Impossible")
                        exit()

                if i == h-1 and j == w-1:
                        break
                elif a[i+1][j] == '
                        i += 1
                elif a[i][j+1] == '
                        j += 1
                else: 
                        print("Impossible")
                        exit()

        for i in range(h):
                for j in range(w):
                        if a[i][j] != b[i][j]:
                                print("Impossible")
                                exit()
        print("Possible")

Solution (Python):
def main2():
    H, W = map(int, input().split())

    count = 0
    for i in range(H):
        count += input().count("

    if count == (H + W - 1):
        print("Possible")
    else:
        print("Impossible")

if __name__ == "__main__":
    main2()

Solution (Python):
def main():
    H, W = map(int, input().split())
    board = list()

    for i in range(H):
        board.append(list(input()))

    stat = [[False for i in range(W)] for j in range(H)]

    go = True
    i = j = 0
    stat[i][j] = True
    while go:

        if (i < H) and (j + 1 < W) and board[i][j + 1] == "
            j = j + 1
            stat[i][j] = True
        elif (i + 1 < H) and (j < W) and board[i + 1][j] == "
            i = i + 1
            stat[i][j] = True
        else:
            break

    ans = True
    for i in range(H):
        for j in range(W):
            if board[i][j] == "
                ans = False

    if ans:
        print("Possible")
    else:
        print("Impossible")
        
if __name__ == "__main__":
    main()

Solution (Python):
H, W=map(int, input().split())
cnt=0
for _ in range(H):
  a=list(input())
  cnt+=a.count("
if cnt==(H+W-1):
  print("Possible")
else:
  print("Impossible")

Solution (Python):
h,w = map(int, input().split())
cnt = 0
for i in range(h):
    cnt += input().count("

if h + w - 1 == cnt:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
h,w=map(int,input().split())
a=[]
flg=True
for i in range(h):
    a.append(list(input()))
tmp=0
for i in range(h):
    for j in range(w):
        if a[i][j]=="
            if j<tmp:
                flg=False
            else: tmp=j
if flg:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
H,W=(map(int,input().split()))
count=0
for i in range(H):
    a=list(input())
    for i in a:
        if i=='
            count+=1
if count==H+W-1:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
H, W = map(int, input().split())
count = 0
for _ in range(H):
    a = input()
    count += a.count('
 
if count == H + W - 1:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
H, W = map(int, input().split())
count = 0
for _ in range(H):
    a = input()
    count += a.count('

if count == H + W - 1:
    print('Possible')
else:
    print('Impossible')

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

seen = [[False for i in range(W)] for j in range(H)]
h, w = 0, 0
while h < H and w < W:
    seen[h][w] = True

    if a[h][w + 1] == a[h + 1][w]:
        print('Impossible')
        exit()

    if a[h][w + 1] == '
        w += 1
    else:
        h += 1

    if a[h - 1][w] == '
        print('Impossible')
        exit()

    if h == H - 1 and w == W - 1:
        print('Possible')
        exit()
print('Impossible')

Solution (Python):
h, w = map(int,input().split())
a = [list(input()) for _ in range(h)]
c = 0
for p in a :
    for q in p:
        if q=="
            c +=1
 
if c == h + w - 1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
import sys

H,W=map(int,input().split())

A=["."*(W+2)]
T=0
for _ in range(H):
    G=input()
    A.append("."+G+".")
    T+=G.count("
    
A.append("."*(W+2))

x,y=1,1
U=1
while x<W or y<H:
    p=(A[y+1][x]=="
    q=(A[y][x+1]=="

    if p^q:
        if p:
            y=y+1
        else:
            x=x+1
        U+=1
    else:
        print("Impossible")
        sys.exit()

if T==U:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
H, W = map(int, input().split())
sp_cnt = 0
for _ in range(H):
    sp_cnt += input().count("
if sp_cnt == H+W - 1:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
H, W = map(int, input().split())

A = []
for _ in range(H):
    A.append(list(input()))

cnt = 0
for aa in A:
    for aaa in aa:
        if aaa == '
            cnt += 1

if cnt == H + W - 1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
x,y = list(map(int, input().split()))
l = []
for i in range (x):
   l.append(list(input()))
val = 0
for j in range (x):
   val += l[j].count('
print('Possible' if x + y - 1 == val else 'Impossible')

Solution (Python):
H,W=map(int,input().split())
A = []
for _ in range(H):
    a = input()
    A.append(a)
count=0
for val in A:
    for query in val:
        if query=="
            count +=1
if count == H+W-1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
def dfs(grid, start, wall, h, w):
    stack = []
    push, pop = stack.append, stack.pop
    push(start)
    grid[start[0]][start[1]] = wall
    dxy = [(0,1), (1,0)]

    while stack:
        h, w = pop()
        cnt = 0
        for dx,dy in dxy:
            x, y = w+dx, h+dy
            if grid[y][x] == wall:
                continue
            push((y,x))
            grid[y][x] = wall
            cnt += 1
        if cnt > 1:
            return False
    for i in range(1, h+1):
        for j in range(1, w+1):
            if grid[i][j] != wall:
                return False
    return True


def resolve():
    h, w = map(int, input().split())
    grid = {}
    wall = '.'
    edges = [wall] * (w+2)
    grid = [edges]
    for i in range(h):
        s = input()
        grid.append([wall] + list(s) + [wall])
    grid.append(edges)
    print("Possible" if dfs(grid, (1, 1), wall, h, w) else "Impossible")

if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for i in range(H)]
    CNT = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == '
                CNT += 1
    if CNT == H+W-1:
        print('Possible')
    else:
        print('Impossible')

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
h,w = map(int,input().split())

Map = []
Cnt = 0
for i in range(h):
    tmp = list(input())
    Cnt += tmp.count('
    Map.append(tmp)
q = deque()
q.append((0,0,0,True))
while q:
    y,x,cnt,flag= q.pop()
    if flag ==False:
        continue
    if y<0 or y>=h or x<0 or x>=w:
        continue
    if Map[y][x]!='
        continue
    cnt += 1
    if cnt==Cnt and y==h-1 and x == w-1:
        if flag:
            print('Possible')
        exit()
    q.append((y+1,x,cnt,flag))
    q.append((y,x+1,cnt,flag))
    flag = False
    q.append((y-1,x,cnt,flag))
    q.append((y,x-1,cnt,flag))

print('Impossible')

Solution (Python):
import sys
import math
import numpy as np
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

H,W = I()
maze = [list(s()) for _ in range(H)]
visited = [[0]*W for _ in range(H)]
def dfs(x,y):
    if x < 0 or y < 0 or x >= H or y >= W:
        return
    if maze[x][y] == '.':
        return
    visited[x][y] = 1
    dfs(x+1,y)
    dfs(x,y+1)
dfs(0,0)
if visited[H-1][W-1] == 1:
    cnt = 0
    for i in range(H):
        cnt += maze[i].count('
    if cnt == H+W-1:
        print('Possible')
    else:
        print('Impossible')
else:
    print('Impossible')

Solution (Python):
H,W=map(int,input().split())
S=[]
for _ in range(H):
    s=input()
    s=[a for a in s]
    S.append(s)
visited=[[-1 for _ in range(W)] for _ in range(H)]
visited[0][0]=1
stack=[[0,0]]
answer=0
S[0][0]='.'
while len(stack)>0:
    h,w=stack.pop()
    number=0
    for x,y in ([0,1],[0,-1],[1,0],[-1,0]):
        new_w=w+x
        new_h=h+y
        if new_w<0 or new_w>=W or new_h<0 or new_h>=H:
            continue
        elif visited[new_h][new_w]==-1 and S[new_h][new_w]=='
            number+=1
            visited[new_h][new_w]=1
            S[new_h][new_w]='.'
            stack.append([new_h,new_w])
            if x==-1 and y==0:
                answer=1
                break
            elif x==0 and y==-1:
                answer=1
                break
        if number>1:
            answer=1
            break
if answer==0:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["
                if a[i+1][j] == '
                    print("Impossible")
                    exit()
        for k in range(1,w):
            if a[i][k] == "
                if a[i+1][k-2:k] == ["
                    print("Impossible")
                    exit()
    if a[h-2][-1] == "
        if a[h-1][-2] == "
            print("Impossible")
            exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
H,W = map(int,input().split())
A = [list(input().strip()) for _ in range(H)]
x = [0,0]
A[0][0] = "."
while True:
    if x[0]==H-1 and x[1]==W-1:break
    if x[0]<H-1 and A[x[0]+1][x[1]]=="
        A[x[0]+1][x[1]]="."
        x = [x[0]+1,x[1]]
    elif x[1]<W-1 and A[x[0]][x[1]+1]=="
        A[x[0]][x[1]+1]="."
        x = [x[0],x[1]+1]
    elif (x[0]<H-1 and A[x[0]+1][x[1]]==".") and (x[1]<W-1 and A[x[0]][x[1]+1]=="."):
        break
    elif (x[0]==H-1 and x[1]<W-1 and A[x[0]][x[1]+1]==".") or (x[1]==W-1 and x[0]<H-1 and A[x[0]+1][x[1]]=="."):
        break
flag = 0
for i in range(H):
    for j in range(W):
        if A[i][j]=="
            flag = 1
            break
    if flag==1:break
if flag==0:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
from collections import deque
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
def BFS(x,y):
  flag=False
  qu=deque([])
  qu.append([x,y])
  
  while len(qu)!=0:
    d=qu.popleft()
    now_x,now_y=d[0],d[1]
    
    
    a[now_y][now_x]="."
    if now_x==w-1 and now_y==h-1:
      flag=True
      return flag
      
    if now_y<h-1 and a[now_y+1][now_x]=="
      qu.append([now_x,now_y+1])
    if now_x<w-1 and a[now_y][now_x+1]=="
      qu.append([now_x+1,now_y])
    if now_y<h-1 and a[now_y+1][now_x]=="
      return flag
  return flag
flag=BFS(0,0)
for i in a:
  for j in i:
    if j=="
      flag=False
if flag:
  print("Possible")
else:
  print("Impossible")

Solution (Python):
H,W = map(int,input().split())
step = H+W-2
A = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  A.append(temp)
cnt = 0
for i in range(H):
  for j in range(W):
    if A[i][j] == "
      cnt += 1
if cnt == step+1:
  print("Possible")
else:
  print("Impossible")

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def err():
    print('Impossible')
    quit()
n,m = inpl()
g = [list(input()) for _ in range(n)]
su = 0
for i in range(n):
    for j in range(m):
        if g[i][j] == '
            su += 1 
if g[0][0] == '.' or su != n+m-1:
    err()
for fl in itertools.permutations(range(n+m-2), n-1):
    
    now = [0,0]
    for i in range(n+m-2):
        if i in fl:
            now[0] += 1
        else:
            now[1] += 1
        y,x = now
        if g[y][x] == '.':
            break
    else:
        print('Possible')
        quit()
err()

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

no = "Impossible"
h, w = 0, 0
while h < H-1 or w < W-1:
    if A[h][w] == ".":
        print(no)
        break
    A[h][w] = "."
    if h > 1:
        if A[h-1][w] == "
            print(no)
            break
    if w > 1:
        if A[h][w-1] == "
            print(no)
            break
    
    if h < H-1:
        if A[h+1][w] == "
            h += 1
            continue

    if w < W-1:
        if A[h][w+1] == "
            w += 1
            continue

else:
    A[H-1][W-1] = "."
    for i in range(H):
        if A[i].count("
            print(no)
            break
    else:
        print("Possible")

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
M = [list(str(input())) for _ in range(H)]

cnt = 0
for i in range(H):
    for j in range(W):
        if M[i][j]=="
            cnt += 1
if cnt!=H+W-1:
    print("Impossible")
else:
    def dfs(x, y):
        if x==W-1 and y==H-1:
            return 1
        ret = 0
        if x+1<W and M[y][x+1]=='
            ret += dfs(x+1, y)
        if y+1<H and M[y+1][x]=="
            ret += dfs(x, y+1)
        return ret
    
    if dfs(0, 0)>0:
        print('Possible')
    else:
        print('Impossible')

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    
    N, M = map(int, input().split())
    
    
    S = tuple(tuple(input()) for i in range(N)) 

    mi=-1
    for s in S:
        f=0
        for i,si in enumerate(s):
            if f==0 and si=="
                if i >=mi:
                    mi=i
                    f=1
                else:
                    print('Impossible')
                    return
            elif f==1 and si==".":
                f=2
            elif f==1 and si=="
                mi=i
            elif f==2 and si=="
                print('Impossible')
                return

    print('Possible')






if __name__ == "__main__":
    main()

Solution (Python):
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

h,w=mp()
ans=0
for i in range(h):
    ans+=input().count("
if ans==h+w-1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
H,W=map(int,input().split())
A= [list(input()) for _ in range(H)]
cnt=0
for p in A:
    for q in p:
        if q=="
            cnt +=1

if cnt == H+W-1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
x,y=map(int,input().split())
failflag=0
m=[]
for i in range(x):
  m.append(input())
for i in range(x):
  for j in range(y):
    if m[i][j]=='
      if i<x-1 and j>0:
        if m[i+1][j-1]=='
          failflag=1
if failflag==0:
  print('Possible')
else:
  print('Impossible')

Solution (Python):
H,W=map(int,input().split())
P=sum([list(input()).count('
if P==H+W-1:
  print('Possible')
else:
  print('Impossible')

Solution (Python):
h,w=map(int,input().split())
a=[input()for _ in range(h)]
c=0
for i in a:
  for j in i:
    if j=="
if c==h+w-1:print("Possible")
else:print("Impossible")

Solution (Python):





import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_ints(): return list(map(int, read().split()))


def read_map_as(H, replace={'
    '''
    文字列のmapを置換して読み込み。デフォでは
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            
            
    else:  
        ret = [[pad] * (W + 2)]  
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce



H, W = read_ints()
A = read_map_as(H)
n_sharp = reduce(add, reduce(add, A))
print('Possible' if n_sharp == H + W - 1 else 'Impossible')

Solution (Python):

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_ints(): return list(map(int, read().split()))


def read_map_as(H, replace={'
    '''
    文字列のmapを置換して読み込み。デフォでは
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            
            
    else:  
        ret = [[pad] * (W + 2)]  
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce



H, W = read_ints()
A = read_map_as(H)
i, j = 0, 0
A[i][j] = 0
while i != H - 1 or j != W - 1:
    if i + 1 < H and j + 1 < W and A[i + 1][j] and A[i][j + 1]:
        print('Impossible')
        exit()
    ni = i
    nj = j
    if i + 1 < H and A[i + 1][j]:
        ni = i + 1
    if j + 1 < W and A[i][j + 1]:
        nj = j + 1
    if ni == i and nj == j:
        print('Impossible')
        exit()
    A[ni][nj] = 0  
    i, j = ni, nj

res = reduce(add, reduce(add, A))


print('Possible' if res == 0 else 'Impossible')

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

    tmp = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == '
                tmp += 1

    if tmp == H + W - 1:
        print('Possible')
    else:
        print('Impossible')


if __name__ == "__main__":
    main()

Solution (Python):
A,B = list(map(int, input().split()))
L = []
for i in range (A):
   L.append(list(input()))
k = 0
for j in range (A):
   k += L[j].count('
print('Possible' if A + B - 1 == k else 'Impossible')

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

H,W = I()
maze = [list(s()) for _ in range(H)]
visited = [[-1]*W for _ in range(H)]

def dfs(x,y):
    if x < 0 or y < 0 or x >= H or y >= W:
        return
    if visited[x][y] != -1:
        return
    if maze[x][y] == '.':
        return
    visited[x][y] = 1
    dfs(x+1,y)
    dfs(x,y+1)

dfs(0,0)
cnt = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '
            cnt += 1
if visited[-1][-1] == -1:
    print('Impossible')
elif cnt == H+W-1:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
h = 0
w = 0
ans = 'Possible'
for i in range(H):
  for j in range(W):
    if A[i][j] == '
      if (i == h and j - w < 2) or (i - h < 2 and j == w):
        h = i
        w = j
      else:
        ans = 'Impossible'
print(ans)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W = map(int, readline().split())
n = read().count(b'
print('Possible' if n == H + W - 1 else 'Impossible')

Solution (Python):
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
a=[]
for i in range(h):
    sub=input().rstrip()
    a.append(sub)
check=True
for i in range(h):
    for j in range(w):
        if a[i][j]=='
            for k in range(h):
                for l in range(w):
                    if (i>k and j<l) or (i<k and j>l):
                        if a[k][l]=='
                            check=False
if check:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
from itertools import permutations

h,w = map(int,input().split())
nec = []
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == "
            nec.append([i,j])

if len(nec) == h+w-1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
def check(grid, h, w):
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '
                return False
    return True


def main():
    h, w = map(int, input().split())

    grid = []
    for _ in range(h):
        grid.append(list(input()))
    
    dy = [0, 1]
    dx = [1, 0]
    stack = [[0, 0]]
    grid[0][0] = 'D'
    while stack:
        y, x = stack.pop()
        for i in range(2):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if 0 <= next_y < h and 0 <= next_x < w and grid[next_y][next_x] == '
                grid[next_y][next_x] = 'D'
                stack.append([next_y, next_x])
                break
    if check(grid, h, w):
        print('Possible')
        return
    print('Impossible')

if __name__ == "__main__":
    main()

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

def dfs(h,w,c):
  if h == H - 1 and w == W - 1:
    return c + 1

  if H - 1 < h or W -1 < w:
    return 0
  
  if GRID[h][w] != "
    return 0
  
  
  right = dfs(h+1,w,c+1)
  down = dfs(h,w+1,c+1)

  return max(right,down)

NUM = sum([GRID[x].count("

n = dfs(0,0,0)

if n == NUM:
  print("Possible")
else:
  print("Impossible")

Solution (Python):
H,W = map(int,input().split())
c = 0
for i in range(H):
  A = input()
  c += A.count("
if c == H+W-1:
  print("Possible")
else:
  print("Impossible")

Solution (Python):
h,w = map(int,input().split())
l = []
for _ in range(h):
    a = list(map(str,input()))
    l.append(a)

tmp = 0

for i in range(h):
    for j in range(w):
        if l[i][j] == "
            if j < tmp:
                print("Impossible")
                exit()
            else:
                tmp = j


print("Possible")

Solution (Python):
from collections import deque

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

slst = [[] for _ in range(H)]
for i in range(H):
  for j in range(W):
    if Map[i][j] == '
      slst[i].append(j)

m = 0
for i in range(1,H):
  if slst[i-1][-1] != slst[i][0]:
    print('Impossible')
    exit()
    
print('Possible')

Solution (Python):
h,w = map(int,input().split())
maze = [input() for _ in range(h)]
total = 0
for maz in maze:
    for m in maz:
        if m == "
            total += 1

ans = False
def search(x,y,count):
    global ans
    if x == w-1 and y == h-1 and maze[y][x] == "
        ans = True
        return
    if x < w-1 and maze[y][x+1] == "
        search(x+1,y,count+1)
    if y < h-1 and maze[y+1][x] == "
        search(x,y+1,count+1)

if maze[0][0] == "
    search(0,0,1)
if ans:print("Possible")
else:print("Impossible")