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 = list(map(int, input().split()))
A = []

for i in range(H):
    s = input()
    A.append(list(s))




di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

ans = True
for i in range(H):
    for j in range(W):
        
        
        if A[i][j] == '
            ul = 0  
            rd = 0  
            for k in range(4):
                ni = i + di[k]
                nj = j + dj[k]
                if 0 <= ni < H and 0 <= nj < W:
                    if A[ni][nj] == '
                        if k == 0 or k == 1:
                            ul += 1
                        else:
                            rd += 1
            
            if i == 0 and j == 0:
                if not (ul == 0 and rd == 1):
                    ans = False
            elif i == H-1 and j == W-1:
                if not (ul == 1 and rd == 0):
                    ans = False
            else:
                if not (ul == 1 and rd == 1):
                    ans = False

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

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

ans = "Impossible"

cnt = 0
for a in A:
    cnt += a.count("

if cnt == H + W - 1:
    ans = "Possible"

print(ans)

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

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

fie = [list(input())for i in range(h)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]


cant = 0
que = Queue()
que.put([0,0])

while not que.empty():
        px, py = que.get()
        fie[px][py] = "."
        under = right = 0
        for i in range(4):
                if 0<=px+dx[i]<h and 0<=py+dy[i]<w and fie[px+dx[i]][py+dy[i]]=="
                        if i==2 or i==3: cant = 1
                        else:
                                if i==0: under = 1
                                elif i==1: right = 1
                                que.put([px+dx[i],py+dy[i]])
        if under and right: cant = 1

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

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

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

Solution (Python):





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

h = 0
w = 0
A[0][0]="."

while not(h==H-1 and w==W-1):
    
    if h<H-1 and w<W-1 and A[h+1][w]=="
        print("Impossible")
        break

    elif h<H-1 and A[h+1][w]=="
        h += 1
        A[h][w] = "."

    elif w<W-1 and A[h][w+1]=="
        w += 1
        A[h][w] = "."
    else:
        print("Impossible")
        break

else:
    flg = 0
    for h in range(H):
        for w in range(W):
            if A[h][w]=="
                flg = 1
                break
    else:
        if flg:
            print("Impossible")
        else:    
            print("Possible")

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 inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

h,w = inpl()
s = [list(input()) for i in range(h)]
cnt = 0
for i in s:
    cnt += i.count('
if cnt != h+w-1:
    print('Impossible')
    quit()
for fl in itertools.combinations(range(h+w-2),h-1):
    nx = 0; ny = 0
    for i in range(h+w-2):
        if i in fl:
            ny += 1
        else:
            nx += 1
        if s[ny][nx] == '
            continue
        break
    else:
        print('Possible')
        break
else:
    print('Impossible')

Solution (Python):
if __name__ == "__main__":
    h, w = map(int, input().split())
    a = list()
    for i in range(h):
        a.append(input())

    count = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == '
                count += 1

    if count == h + w - 1:
        print('Possible')
    else:
        print('Impossible')

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

sp = 0
for line in A:
  if line.find("
    print("Impossible")
    exit()
  sp = line.rfind("
print("Possible")

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

cnt = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '
            cnt += 1

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

Solution (Python):
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    cnt = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == "
                cnt += 1
    if H+W-1 == cnt:
        print("Possible")
    else:
        print("Impossible")


if __name__ == '__main__':
    main()

Solution (Python):
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
max_h=0
max_w=0

for i in range(h):
    for j in range(w):
        if a[i][j]=="
            if max_h>i or max_w>j:
                print('Impossible')
                exit()
            else:
                max_h=max(max_h,i)
                max_w=max(max_w,j)
print('Possible')

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

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

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

Solution (Python):
from sys import stdin,setrecursionlimit
from itertools import groupby
setrecursionlimit(10**7)
h,w = map(int,stdin.readline().rstrip().split())
li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]
now = 0
last = 0
for i in range(h):
    flag = True
    for j in range(w):
        lin = []
        for key, value in groupby(li[i]):
            lin.append(key)
        if lin.count("
            print("Impossible")
            exit()
        if li[i][j] == "
            flag = False
            now = j
        if i >= 1 and flag == False and now != last:
            print("Impossible")
            exit()
        if (flag == False and li[i][j] == "."):
            last = j-1
            break
        if  (not flag and j == w-1):
            last = j
            break
if last == w-1:
    print("Possible")
else:
    print("Impossible")

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

Solution (Python):








n,m=map(int,input().split())
s = [list(input()) for i in range(n)]
def dfs(x,y):
    c=False
    s[x][y]='.'
    for i in range(0,2):
        for j in range(0,2):
            if i==1 and j==1:
                continue
            nx=i+x
            ny=j+y
            if 0<=nx<n and 0<=ny<m and s[nx][ny]=='
                
                c=True
                dfs(nx,ny)
            if c:
                break
        if c:
            break
ans=0
for i in range(n):
    for j in range(m):
        if s[i][j]=='
            
            
            dfs(i,j)
            ans+=1
            
if ans<=1:
    print("Possible")
else:
    print("Impossible")

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

min_ = 0
max_ = 0
for i in range(h):
    flag = 1
    for j in range(w):
        if flag == 1 and A[i][j] == '
            min_ = j
            if min_ < max_:
                print('Impossible')
                exit()
            flag = 0
        if flag == 0 and A[i][j] == '
            max_ = j
else:
    print('Possible')

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip("\n") for _ in range(H)]
    q = deque()
    q.append((0, 0))
    visited = [[False] * W for _ in range(H)]
    possible = True
    while q:
        nh, nw = q.popleft()
        if not visited[nh][nw]:
            visited[nh][nw] = True
            count = 0
            if 0 <= nh + 1 < H and A[nh + 1][nw] == "
                if 0 <= nw - 1 and A[nh+1][nw-1] == "
                    possible = False
                    break
                q.append((nh+1, nw))
                count += 1
            if 0 <= nw + 1 < W and A[nh][nw+1] == "
                if 0 <= nh - 1 and A[nh-1][nw+1] == "
                    possible = False
                    break
                q.append((nh, nw+1))
                count += 1
            if count == 2:
                possible = False
                break
    else:
        if not visited[H-1][W-1]: possible = False
    print("Possible" if possible else "Impossible")

    return 0

if __name__ =="__main__":
    solve()

Solution (Python):
h,w=map(int,input().split())
num=0
s=[str(input()) for i in range(h)]
for i in range(h):
  num+=s[i].count("
if num>h+w-1:
  print("Impossible")
  exit()
print("Possible")

Solution (Python):
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    seen = [[0]*W for i in range(H)]

    def bfs(sy, sx):
        que = deque()

        seen[sy][sx] = 1
        que.append((sy, sx))
        d = ((1, 0), (0, 1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if seen[next_y][next_x] != 0:
                    continue
                if c[next_y][next_x] == '.':
                    continue
                seen[next_y][next_x] = 1
                que.append((next_y, next_x))
                break
    bfs(0, 0)
    num = 0
    cnt = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == "
                num += 1
            if seen[h][w] == 1:
                cnt += 1
    
    if seen[-1][-1] == 1 and num == cnt:
        print("Possible")
    else:
        print("Impossible")


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for _ in range(H)]
    cnt = sum([1 if A[i][j]=='

    ans = False
    stack = [(0, 0, 1)]
    while stack:
        i, j, d = stack.pop()
        if i == H-1 and j == W-1:
            if d == cnt:
                ans = True
            break
        for di, dj in [(0,1), (1,0)]:
            ni, nj = i+di, j+dj
            if ni >= H or nj >= W: continue
            if A[ni][nj] != '
            stack.append((ni, nj, d+1))
    print('Possible' if ans else 'Impossible')

if __name__ == '__main__':
    main()

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
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)]
nextstrtj = 0
for i in range(h):
    flag1 = False 
    flag2 = False 
    for j in range(nextstrtj):
        if a[i][j] == '
            print('Impossible')
            exit()
    for j in range(nextstrtj, w):
        if flag1 and a[i][j] == '
            print('Impossible')
            exit()
        elif a[i][j] == '
            flag2 = True
            nextstrtj = j
        elif flag2 and a[i][j] == '.':
            flag1 = True
    if not flag2:
        print('Impossible')
        exit()

print('Possible')

Solution (Python):



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

cnt = 0
for _ in range(H):
    cnt += list(input()).count("

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

Solution (Python):
h,w=map(int,input().split())
s=[list(input())for _ in range(h)]
ok=[w*[0]for _ in range(h)]
ok[0][0]=1
for i in range(h):
  for j in range(w):
    if i==0:
      if j!=0:
        if s[i][j]=="
    else:
      if s[i][j]=="
      if j==0:continue
      if s[i][j]=="
co=sum(i.count("
if co!=h+w-1:print("Impossible")
elif ok[-1][-1]:print("Possible")
else:print("Impossible")

Solution (Python):


h, w = map(int, input().split())
grid = []
sharp_count = 0
for i in range(h):
    grid.append(list(input()))
    sharp_count += grid[i].count('
if sharp_count != h+w-1:
    print("Impossible")
else:
    print("Possible")

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

field = [list(input()) for _ in range(H)]
count = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '
            count += 1
            
if count <= (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('
print("Possible" if cnt == H + W - 1 else "Impossible")

Solution (Python):

h,w = map(int,input().split())
a = []
count = 0

for i in range(h):
    a.append(list(map(str,input().split())))

for j in range(h):
    c = str(a[j])

    count += c.count("


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

Solution (Python):
def main():
    h, w = map(int, input().split())
    a = [["." for j in range(w+2)] for i in range(h+2)]
    for i in range(h):
        s = list(input().rstrip())
        for j in range(w):
            a[i+1][j+1] = s[j]
    y, x = 1, 1
    f = True
    while y != h or x != w:
        a[y][x] = "."
        if a[y-1][x] == "
            f = False
            break
        else:
            if a[y+1][x] == "
                y += 1
            else:
                x += 1
    if a[y-1][x] == "
        f = False
    if f:
        print("Possible")
    else:
        print("Impossible")

if __name__ == "__main__":
    main()

Solution (Python):
H, W = map(int, input().split())
bl = 0
br = 0
for i in range(H):
    line = input().strip()
    foot = []
    for j in range(W):
        if line[j] == '
            foot.append(j)
    nl = foot[0]
    nr = foot[-1]
    if nl < br:
        print('Impossible')
        exit()
    bl, br = nl, nr
print('Possible')

Solution (Python):
H, W = map(int, input().split())
moves = 0
for h in range(H):
  S = str(input())
  for s in S:
    if s == '
      moves += 1

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

Solution (Python):
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')

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

x,y = 0,0
while True:
    maze[y][x] = "."
    if x == w-1 and  y == h-1:
        break
    if x != w-1 and maze[y][x+1]== "
        x += 1
        continue
    if y != h-1 and maze[y+1][x]=="
        y += 1
        continue
    break
from pprint import pprint

f= True
for i in range(h):
    if maze[i].count("
        f = False
print("Impossible" if not f else "Possible")

Solution (Python):
n, m = map(int, input().split())
mat = [input() for _ in range(n)]
i = 0
j = 0

while i != n-1 or j != m-1:
    down = '.'
    right = '.'
    downleft = '.'
    rightup = '.'
    if i != n-1:
        down = mat[i+1][j]
        if j != 0:
            downleft = mat[i+1][j-1]
    if j != m-1:
        right = mat[i][j+1]
        if i != 0:
            rightup = mat[i-1][j+1]
    
    if down == right:
        print('Impossible')
        exit()
    elif down == '
        if downleft == down:
            print('Impossible')
            exit()
        i+=1
    else: 
        if rightup == right:
            print('Impossible')
            exit()
        j+=1

print('Possible')

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

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

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

i = 0
j = 0
while i < H or j < W:
    if i < H-1 and A[i+1][j] == "
        i += 1
        A[i][j] = "."
    elif j < W-1 and A[i][j+1] == "
        j += 1
        A[i][j] = "."
    else:
        break

cnt = 0
for i in range(H):
    cnt += A[i].count("
if cnt == 1 and i == H-1 and j == W-1:
    print("Possible")
else:
    print("Impossible")

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

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

rc = 0
for _ in range(h):
  rc += input().count('

if rc == w+h-1:
  print('Possible')
else:
  print('Impossible')

Solution (Python):
h,w=map(int,input().split())
data=[]
for i in range(h):
    a=input()
    data.append(a)
ans="Possible"
r=0
for i in range(h):
    for j in range(w):
        if data[i][j]=="
            if j<r:
                ans="Impossible"
                break
            else:
                r=j
    if ans=="Impossible":
        break
print(ans)

Solution (Python):

h,w=map(int,input().split())
flag=True
dif=[]
for i in range(h):
    s=input()
    lists=[]
    for i in range(w):
        if s[i]=="
            lists.append(i+1)
    for i in range(len(lists)-1):
        if lists[i+1]-lists[i]>1:
            flag=False
            break
    dif.append((lists[0],lists[-1]))
if flag:
    subflag=True
    for i in range(h-1):
        if dif[i+1][0]!=dif[i][1]:
            subflag=False
            break
    if subflag:
        print("Possible")
    else:
        print("Impossible")
else:
    print("Impossible")

Solution (Python):



from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe




def printargs2err(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' : '+repr(arg) for arg in args),file=sys.stderr)
def debug(x):
    print(x,file=sys.stderr)
def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)

def pin(type=int):
    return map(type,input().split())



def modular_w_binary_method (n,m,p):
    ans=1 if n>0 else 0
    while(p>0):
        if p%2==1:
            ans=(ans*n)%m
        n=(n**2)%m
        p//=2
    return ans

"""
    フェルマーの小定理より a**(p)%p==a isTrue
    これを利用すれば a**(p-2)%p==a**(-1) isTrue
    元と逆元とをかけてpで割れば1が余るよ！
"""
def modular_inverse(a,prime):
    return(modular_w_binary_method(a,prime,prime-2))

def conbination(n,a,mod=10**9+7):
    
    res=1 
    for s in range(a):
        res=(res*(n-s)*(modular_inverse(s+1,mod)))%mod

        
    return res

"""
"""




H,W=pin()
h=0
for i in range(H):
    t=list(input())
    for j in t:
        if j=="
            h+=1

print(["Impossible","Possible"][h==(H+W-1)])



"""


"""
"""
お前カッコ閉じるの忘れてるだろ
"""

Solution (Python):
H,W=map(int, input().split())
A="".join(input() for _ in range(H))
print("Possible" if H+W-1==A.count("

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

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

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

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

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

flag = True


x,y=0,0
for _ in range(h+w-2):
    
    if x+1 < h and A[x+1][y] == '
        
        x += 1
        continue
    
    if y+1 < w and A[x][y+1] == '
        
        y += 1
        continue
    
    flag = False
    break

flag = flag and (sum(x.count('
ans = 'Possible' if flag else 'Impossible'
print(ans)

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

cnt = 0
for i in range(H):
    cnt += tb[i].count('

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

Solution (Python):
import numpy as np

h, w = [int(i) for i in input().split()]
a = np.array([list(input()) for _ in range(h)])

print("Possible" if np.count_nonzero(a == '

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

r = 0
for j in range(W):
    if map[0][j] == "
        r = j
for i in range(1,H):
    flag = 1
    for j in range(W):
        if flag and map[i][j] == "
            if r != j:
                print('Impossible')
                exit()
            flag = 0
        elif map[i][j] == "
            r = j

print('Possible')

Solution (Python):
from collections import deque


dis_x = [1, 0]
dis_y = [0, 1]


max_h, max_w = map(int, input().split())

s = []
av_count = 0
for _ in range(max_h):
    line = input()
    av_count += line.count("
    
    s.append(list(".{}.".format(line)))


s = [list("." * (max_w + 2))] + s + [list("." * (max_w + 2))]



dist = [ [0] * (max_w + 2) for _ in range(max_h+2)]


que = deque([(1, 1)])


while que:
    
    h, w = que.popleft()

    for i in range(2):
        
        dx, dy = dis_x[i], dis_y[i]
        if s[h+dy][w+dx] == '
            
            dist[h+dy][w+dx] = dist[h][w] + 1
            
            que.append((h+dy, w+dx))
            break

dist[1][1] = 1

dis = 0
for line in dist:
  dis += len(list(filter(lambda x : x != 0, line)))

print("Possible" if av_count == dis else "Impossible")

Solution (Python):
from collections import deque
H,W = 0,0
A,cost = [],[]
INF = float('inf')

def dfs(x,y):
    global H,W,A,cost,INF
    q = deque([[x,y]])
    dx = [1,0]
    dy = [0,1]
    while len(q) != 0:
        tmp = q.pop()
        x,y = tmp[0],tmp[1]
        for i in range(2):
            if 0 <= x+dy[i] < H and 0 <= y+dx[i] < W:
                if A[x+dy[i]][y+dx[i]] == "
                    cost[x+dy[i]][y+dx[i]] = cost[x][y]+1
                    q.append([x+dy[i],y+dx[i]])
                    break


def main():
    global H,W,A,cost,INF
    H,W = map(int,input().split())
    A = [list(input()) for _ in range(H)]
    cost = [[INF]*W for _ in range(H)]
    cost[0][0] = 0
    dfs(0,0)
    ans = "Possible"
    flag = False
    for i in range(H):
        if flag:
            break
        for j in range(W):
            if A[i][j] == "
                ans = "Impossible"
                flag = True
                break
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

h, w = list(map(int, input().split()))
num = sum(Counter(input())['
print('Possible' if w + h - 1 == num else 'Impossible')

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

cnt_j = 0
for i in range(H):
    for j in range(W):
        if(A[i][j] == "
            if(cnt_j <= j):
                cnt_j = j
            else:
                print("Impossible")
                quit()
else:
    print("Possible")

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

grid = [[1 if i == '

total = 0
for i in grid:
  total += sum(i)
  
  
if total == (h+w-1):
  print('Possible')
else:
  print('Impossible')

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

for i in range(H+W-1):
  if i < W:
    x = i
    y = 0
  else:
    x = W-1
    y = i-x
  cnt = 0
  while(x >= 0 and y < H):
    if A[y][x] == '
      cnt += 1
    
    if cnt > 1:
      print('Impossible')
      exit()
    x -= 1
    y += 1
print('Possible')

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

al = []

for _ in range(h):
   a = list(input())
   al.append(a)

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

for i in range(h):
    for j in range(w):
        if al[i][j] == '
            print("Impossible")
            exit()
print("Possible")

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

dy = [0, 1]
dx = [1, 0]

stack = [[0 for _ in range(w)] for _ in range(h)]

def dfs(y, x):
    stack[y][x] = 1
    if x == w-1 and y == h-1:
        return
    for i in range(2):
        ny = y + dy[i]
        nx = x + dx[i] 
        if ny < 0 or ny >= h or nx < 0 or nx >= w:
            continue
        if a[ny][nx] == "
            dfs(ny, nx)
            break
    return

dfs(0, 0)
for i in range(h):
    for j in range(w):
        if a[i][j] == "
            print('Impossible')
            exit()
print('Possible')

Solution (Python):
import sys

h,w=map(int,input().split())
m=[list(input()) for _ in range(h)]

s=[]

i_b,j_b=0,0
for i in range(h):
    for j in range(w):
        if m[i][j] =="
            if i<i_b or j<j_b:
                print("Impossible")
                sys.exit()
            else:
                i_b,j_b=i,j
print("Possible")

Solution (Python):

si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
from collections import deque
def bfs(sy,sx):
    q = deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x = q.popleft()
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if ny<0 or ny>h-1 or nx<0 or nx>w-1 or a[ny][nx]==".":
                continue
            if a[ny][nx]=="
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])
    ret=-1
    for i in range(h):
        for j in range(w):
            ret=max(visited[i][j],ret)
    return ret
h,w=nm()
a=[input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
dist=0
dist=bfs(0,0)
cnt=0
for aa in a:
    cnt+=aa.count('
if dist==h+w-2 and dist==cnt-1:
    print('Possible')
else:
    print('Impossible')

Solution (Python):

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    h, w = map(int, input().split())

    cou = 0
    for _ in range(h):
        cou += input().count('
    if cou == h+w-1:
        print('Possible')
        exit(0)
    print('Impossible')


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000)
H, W = map(int, input().split())
A = [input() for _ in range(H)]
homon = [[False]*W for _ in range(H)]
dx = [0, 1]
dy = [1, 0]

def dfs(x, y):
    homon[y][x] = True
    if x == W-1 and y == H-1:
        return
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if A[ny][nx] == '
            dfs(nx, ny)
            break
    return 

if __name__ == '__main__':
    dfs(0, 0)
    for i in range(H):
        for j in range(W):
            if A[i][j] == '
                print('Impossible')
                exit()
    print('Possible')

Solution (Python):
H,W = map(int, input().split())
A = [list(map(str, input())) for _ 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")

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

q = [[0,0]]

while q != []:
	ans = 0
	cx,cy = q.pop()
	A[cx][cy] = "."

	if [cx,cy] == [H-1,W-1]:
		ans = 1
		for i in range(H):
			for j in range(W):
				if A[i][j] == "
					ans = 0
		break

	nps = [[cx+1,cy],[cx,cy+1]]
	for nx,ny in nps:
		if 0 <= nx < H and 0 <= ny < W:
			if A[nx][ny] == "
				q.append([nx,ny])
				break

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

Solution (Python):
H, W = map(int, input().split())
X = [[1 if a == "

Q = [0]
D = [[0] * W for _ in range(H)]
D[0][0] = 1
while Q:
    x = Q.pop()
    i, j = x//W, x%W
    for di, dj in ((1, 0), (0, 1)):
        ni, nj = i+di, j+dj
        if ni < H and nj < W and X[ni][nj]:
            if D[ni][nj] == 0:
                D[ni][nj] = 1
                Q.append(ni*W + nj)
if D[-1][-1] and sum([sum(x) for x in X]) == H + W - 1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
H, W = map(int, input().split())
matrix = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
  inp = input()
  for j, square in enumerate(inp):
    if square == '
      matrix[i][j] = 1
      
hw = [0, 0]
matrix[0][0] = 0
while True:
  
  if hw[1] + 1 < W and matrix[hw[0]][hw[1] + 1] == 1:
    matrix[hw[0]][hw[1] + 1] = 0
    hw = [hw[0], hw[1] + 1]
    continue
  
  
  if hw[0] + 1 < H and matrix[hw[0] + 1][hw[1]] == 1:
    matrix[hw[0] + 1][hw[1]] = 0
    hw = [hw[0] + 1, hw[1]]
    continue
  
  
  else:
    break
    
flag = sum([sum(row) for row in matrix])
print("Impossible" if flag else "Possible")

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

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

Solution (Python):

H,W = map(int, input().split())
ans = 0
for h in range(H):
    S = str(input())
    for s in S:
        if s=="
            ans+=1
if (ans==H+W-1):
    print ("Possible")
else:
    print ("Impossible")