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):

def check(A, h, w):
    cnt = 0
    if A[h-1][w] == "
        cnt += 1
    if A[h][w-1] == "
        cnt += 1
    if A[h][w+1] == "
        cnt += 1
    if A[h+1][w] == "
        cnt += 1
    return cnt

def main():
    H, W = map(int, input().split())
    A = ["." * (W+2)]
    for i in range(H):
        A.append("." + input() + ".")
    A.append("." * (W + 2))
    
    ans = "Possible"
    for w in range(1, W+1):
        for h in range(1, H+1):
            if A[h][w] == "
                if w == h == 1:
                    if check(A, h, w) != 1:
                        ans = "Impossible"
                elif h == H and w == W:
                    if check(A, h, w) != 1:
                        ans = "Impossible"
                elif check(A, h, w) == 2:
                    if A[h-1][w] == A[h+1][w] == "
                        pass
                    elif A[h-1][w] == A[h+1][w] == "." and A[h][w-1] == A[h][w+1] == "
                        pass
                    elif A[h-1][w] == A[h][w+1] == "
                        pass
                    elif A[h+1][w] == A[h][w-1] == "
                        pass
                    else:
                        ans = "Impossible"
                else:
                    ans = "Impossible"
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):


H, W = list(map(int, input().split()))
a_table = []

for _ in range(H):
    a_list = list(input())
    a_table.append(a_list)

if a_table[0][0] != "
    is_ok = False
else:
    
    section_list = []
    is_ok = True
    for j in range(H):
        exist_section = False
        end_section = False
        start_idx = None
        end_idx = None
        for i in range(W):
            if a_table[j][i] == "
                if end_section:
                    
                    is_ok = False
                    break
                elif exist_section:
                    
                    continue
                else:
                    
                    exist_section = True
                    start_idx = i
            else:
                if exist_section and (not end_section):
                    end_section = True
                    end_idx = i - 1
                    section_list.append((start_idx, end_idx))
                else:
                    
                    continue

        if exist_section and (not end_section):
            end_idx = W - 1
            section_list.append((start_idx, end_idx))
        elif not exist_section:
            is_ok = False

        if is_ok:
            if j != 0:
                if section_list[-2][1] != section_list[-1][0]:
                    is_ok = False

        if not is_ok:
            break

ans = "Possible" if is_ok else "Impossible"
print(ans)

Solution (Python):
def main():
    n,m = map(int,input().split())
    maze=[]
    for _ in range(n):
        maze.append(list(input()))
    cnt=0
    for i in range(n):
        for j in range(m):
            if maze[i][j]=="
                cnt+=1
    if cnt==n+m-1:print("Possible")
    else:print("Impossible")
    
main()

Solution (Python):
import sys
import os

H, W = map(int,input().split())
cntS = 0
for i in range(H):
    cntS += list(input()).count("

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

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

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

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

cnh = 0
cnb = 0
for i in range(h):
    s = input()
    for j in range(w):
        if(s[j]=='
            cnh +=1
        else:
            cnb+=1
            
ch = 1
if( cnh == h+w-1):
    ch = 1
else:
    ch = 0

    
if(ch==1):
    print("Possible")
else:
    print("Impossible")

Solution (Python):
h,w = map(int,input().split())
g = [['.'] * (w+2) for i in range(h+2)]
ss = set() 
for i in range(h):
  g[i+1][1:-1] = list(input())
  for j in range(w):
    if g[i+1][j+1] == '
      ss.add((i+1,j+1))
if g[1][1] == '.':
  print('Impossible')
  exit()
cur = (1,1)
ts = set() 
ts.add(cur)
while cur != (h,w):
  if g[cur[0]+1][cur[1]] == '
    cur = (cur[0]+1,cur[1])
    ts.add(cur)
  elif g[cur[0]][cur[1]+1] == '
    cur = (cur[0],cur[1]+1)
    ts.add(cur)
  else:
    print('Impossible')
    exit()
if ts == ss:
  print('Possible')
else:
  print('Impossible')

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


def dfs(x, y):
    A[x][y] = '.'

    if x == h-1 and y == w-1:
        return
    elif x+1 < h and A[x+1][y] == '
        dfs(x+1, y)
    elif y+1 < w and A[x][y+1] == '
        dfs(x, y+1)
    else:
        return


dfs(0, 0)
if A == [['.'] * w] * h:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
h,w=map(int,input().split())
r=[]
for i in range(h):
    r.append(list(input()))
t=[]
for i in range(h):
    for j in range(w):
        if r[i][j]=='
            t.append([i,j])
op=[[[0,0]]]
for i in range(h+w-2):
    tmp=[]
    for j in op:
        tmp.append(j+[[j[-1][0]+1,j[-1][1]]])
        tmp.append(j+[[j[-1][0],j[-1][1]+1]])
    op=tmp
for i in op:
    if sorted(i)==sorted(t):
        print('Possible')
        exit()
print('Impossible')

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

here = 0
for i in A:
    if here != i.find('
        print('Impossible')
        exit()
    else:
        here = i.rfind('
else:
    print('Possible')

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

def bfs(y,x):
    a[y][x]='.'
    
    if y+1<h and x+1<w:
        if a[y+1][x]=='
            bfs(y+1,x)
        elif a[y][x+1]=='
            bfs(y,x+1)
    elif x+1<w:
        if a[y][x+1]=='
            bfs(y,x+1)
    elif y+1<h:
        if a[y+1][x]=='
            bfs(y+1,x)
    
bfs(0,0)

ans='Possible'
for i in a:
    if '
        ans='Impossible'
        
print(ans)

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

grid = [[0] for h in range(H)]

for h in range(H):
    line = list(input())
    grid[h] = line

last = 0
for h in range(H):
    if '
        print('Impossible')
        sys.exit()
    for w in range(last, W - 1):
        if grid[h][w] == '.' and grid[h][w + 1] == '
            print('Impossible')
            sys.exit()
    for w in range(W):
        if grid[h][w] == '
            print('Impossible')
            sys.exit()
        elif grid[h][w] == '
            last = w
print('Possible')

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

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



def a():
    c = -1
    for i in range(len(A)):
        c += A[i].count("
    
    s = [0, 0]
    while s != [h-1, w-1]:
        
        if s[1]+1 < w and A[s[0]][s[1]+1] == "
            s[1] += 1
            c -= 1
        elif s[0]+1 < h and A[s[0]+1][s[1]] == "
            s[0] += 1
            c -= 1
        else:
            return "Impossible"
    if c == 0:
        return "Possible"
    else:
        return "Impossible"

print(a())

Solution (Python):

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

num = 0

for i in range(H):

    A = input()

    for a in A:

        if a == "
            num += 1

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

Solution (Python):
def slove():
    import sys
    input = sys.stdin.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]
    cnt = 0
    for i in range(h):
        cnt += a[i].count("
    print("Possible" if cnt == (h + w - 1) else "Impossible")


if __name__ == '__main__':
    slove()

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

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

Solution (Python):
h,w=map(int,input().split())
a=[]
point=0
for _ in range(h):
	x=input()
	a.append(x)
	point+=x.count("
cnt=[[10**10 for _ in range(w)] for _ in range(h)]
for i in range(h):
	for j in range(w):
		if a[i][j]==".":
			cnt[i][j]="."
cnt[0][0]=0
lis=[[0,0]]
p=1
while len(lis)!=0:
	x=list()
	for _ in range(len(lis)):
		k=lis.pop(0)
		if k[0]!=0:
			if cnt[k[0]-1][k[1]]==10**10:
				cnt[k[0]-1][k[1]]=p
				x.append([k[0]-1,k[1]])
		if k[1]!=0:
			if cnt[k[0]][k[1]-1]==10**10:
				cnt[k[0]][k[1]-1]=p
				x.append([k[0],k[1]-1])
		if k[0]!=h-1:
			if cnt[k[0]+1][k[1]]==10**10:
				cnt[k[0]+1][k[1]]=p
				x.append([k[0]+1,k[1]])
		if k[1]!=w-1:
			if cnt[k[0]][k[1]+1]==10**10:
				cnt[k[0]][k[1]+1]=p
				x.append([k[0],k[1]+1])
	lis=x
	p+=1
if cnt[-1][-1]==h+w-2==point-1:
	print("Possible")
else:
	print("Impossible")

Solution (Python):
H, W = map(int,input().split())
S = [input() for _ in range(H)]
endSh = 0
for i in S:
  startSh = i.find("
  if startSh != endSh:
    print("Impossible")
    exit()
  endSh = i.rfind("
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 = [input() for _ in range(H)]

confilm = [[False] * W for _ in range(H)]
confilm[0][0] = True

nH, nW = 0, 0
while True:
    isMoved = False
    while nW < W - 1 and A[nH][nW + 1] == '
        nW += 1
        confilm[nH][nW] = True
        isMoved = True
    while nH < H - 1 and A[nH + 1][nW] == '
        nH += 1
        confilm[nH][nW] = True
        isMoved = True

    if not isMoved:
        break

for h in range(H):
    for w in range(W):
        if A[h][w] == '
            if confilm[h][w]:
                continue
            else:
                print('Impossible')
                exit()
        else:
            if confilm[h][w]:
                print('Impossible')
                exit()
            else:
                continue

print('Possible')

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

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = list(map(int, sys.stdin.readline().split()))
A = [list(sys.stdin.readline().rstrip()) for _ in range(H)]


def ok(h, w):
    return 0 <= h < H and 0 <= w < W


def dfs(h, w):
    A[h][w] = '.'
    dh = [0, 1, 0, -1]
    dw = [1, 0, -1, 0]
    cnt = 0
    for i, j in zip(dh, dw):
        cnt += ok(h + i, w + j) and A[h + i][w + j] == '
    if cnt == 1:
        for i, j in zip(dh, dw):
            if ok(h + i, w + j) and A[h + i][w + j] == '
                return dfs(h + i, w + j)
    return cnt == 0 and h == H - 1 and w == W - 1


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

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

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

for h in range(H):
  for w in range(W):
    flag1 = 0
    flag2 = 0
    if grid[h][w] == "
      if 0 <= h-1 < H:
        if grid[h-1][w] == "
          flag1 += 1
      if 0 <= w-1 < W:
        if grid[h][w-1] == "
          flag1 += 1
      if 0 <= h+1 < H:
        if grid[h+1][w] == "
          flag2 += 1
      if 0 <= w+1 < W:
        if grid[h][w+1] == "
          flag2 += 1

      if (h == 0 and w == 0):
        if flag1 == 0 and flag2 == 1:
          continue
        else:
          print("Impossible")
          exit()
      if (h == H-1 and w == W-1):
        if flag1 == 1 and flag2 == 0:
          continue
        else:
          print("Impossible")
          exit()
      else:
        if flag1 == 1 and flag2 == 1:
          continue
        else:
          print("Impossible")
          exit()
else:
  print("Possible")

Solution (Python):

def main():
    H, W, *A = open(0).read().split()
    H, W = int(H), int(W)
    flg = ("".join(A)).count("
    print("Possible" if flg else "Impossible")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    a = [input().strip() for i in range(H)]
    check = [[False] * W for i in range(H)]
    
    x, y = 0, 0
    check[y][x] = True
    while True:
        fin = True
        for nx, ny in [(x+1, y), (x, y+1)]:
            if 0 <= nx and nx < W and 0 <= ny and ny < H:
                if a[ny][nx] == "
                    check[ny][nx] = True
                    fin = False
                    x, y = nx, ny
                    break
        if fin:
            break
    
    ok = False
    if x == W-1 and y == H-1:
        ok = True
        for i in range(H):
            for j in range(W):
                if a[i][j] == "
                    ok = False
                    break
            if not ok:
                break

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



if __name__ == "__main__":
    main()

Solution (Python):
import sys
input=sys.stdin.readline

def main():
    H,_ = map(int, input().split())
    a = input().strip()
    for _ in range(H-1):
        b = input().strip()
        if a.rfind("
            print("Impossible")
            return
        a = b
    print("Possible")

if __name__ == '__main__':
    main()

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

prev_left = 0
prev_right = 0

for i in range(H):
    left = A[i].find('
    right = A[i].rfind('
    if prev_right == left:
        prev_left = left
        prev_right = right
    elif right == W-1:
        right = W
        break
    elif prev_left == left and prev_right == right:
        break

if right == W-1:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
H, W = map(int, input().split())
A = []
c = 0
for i in range(H):
  As = input()
  A.append(As)
  c += As.count("
if c != H+W-1:
  print("Impossible")
  exit()
ok = True
i, j = (0, 0)
for k in range(H+W-2):
  fR = j+1 < W and A[i][j+1] == "
  fD = i+1 < H and A[i+1][j] == "
  if not fR ^ fD:
    ok = False
    break
  if fR:
    j += 1
  if fD:
    i += 1
if ok:
  print("Possible")
else:
  print("Impossible")

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

count=0

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

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

Solution (Python):
H,W=map(int,input().split());print(["Imp","P"][H+W-1==sum(input().count("

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


sw=0
for i in range(H):
  tmp=0
  for j in range(W-1):
    if A[i][j]=="
      tmp=1
    if tmp==1 and A[i][j]=="." and A[i][j+1]=="
      sw=1


if sw==1:
  print("Impossible")
else:
  l=[]
  r=[]
  for i in range(H):
    ll=0
    for j in range(W-1):
      if A[i][j]=="." and A[i][j+1]=="
        ll=j+1
        break
    l.append(ll)
    
    rr=W-1
    for j in range(W-1):
      if A[i][j]=="
        rr=j
        break
    r.append(rr)



  sw2=0
  for i in range(len(r)-1):
    if r[i]!=l[i+1]:
      sw2=1
  print("Impossible" if sw2==1 else "Possible")

Solution (Python):
def resolve():
    h, w = map(int, input().split())
    a = list(input() for _ in range(h))
    c = sum([ai.count("
    print("Possible" if c == h + w - 1 else "Impossible")


if __name__ == "__main__":
    resolve()

Solution (Python):
H, W = map(int,input().split())
A = [list(input()) for _ in range(H)]
first = 0
a = A[0]
a = list(reversed(a))
last = W - a.index('
if A[0][first:last+1] == ['
    pass
else:
    print('Impossible')
    exit()

for i in range(1, H):
    a = A[i]
    if last == a.index('
        first = last
    else:
        print('Impossible')
        exit()
    a = list(reversed(a))
    last = W - a.index('
    if A[i][first:last+1] == ['
        pass
    else:
        print('Impossible')
        exit()
print('Possible')

Solution (Python):
h, w = list(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
if cnt==(h+w)-1:
  print("Possible")
else:
  print("Impossible")

Solution (Python):
def slove():
    import sys
    input = sys.stdin.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    cnt = 0
    for i in range(h):
        cnt += str(input().rstrip('\n')).count("
    print("Possible" if cnt == (h + w - 1) else "Impossible")


if __name__ == '__main__':
    slove()

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

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

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

Solution (Python):
H,W=map(int, input().split())
A=[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):
import pprint

H, W = list(map(int, input().split()))
A = []
for h in range(H):
    A.append([s for s in input()])
x, y = 0, 0
goal_x, goal_y = W - 1, H - 1
count = 0
while not (x == goal_x and y == goal_y):
    for diff_x, diff_y in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        tmp_x = x + diff_x
        tmp_y = y + diff_y
        if tmp_x < 0 or tmp_x >= W or tmp_y < 0 or tmp_y >= H:
            continue
        if A[tmp_y][tmp_x] == "
            if diff_x == -1 or diff_y == -1:
                print("Impossible")
                exit()
            A[y][x] = "."
            x += diff_x
            y += diff_y
            
            
            break
    count += 1
    if (W + H - 2) < count:
        print("Impossible")
        exit()

A[goal_y][goal_x] = "."


for h in range(H):
    for w in range(W):
        if A[h][w] == "
            print("Impossible")
            exit()
print("Possible")

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    h,w = LI()
    a = SR(h)
    d = [(1,0),(0,1)]
    bfs = [[1]*w for i in range(h)]
    for y in range(h):
        for x in range(w):
            if a[y][x] == "
                bfs[y][x] = 0
                q = deque([(y,x)])
                while q:
                    i,j = q.popleft()
                    k = 0
                    for dy,dx in d:
                        ni = i+dy
                        nj = j+dx
                        if 0 <= ni < h and 0 <= nj < w:
                            if a[ni][nj] == "
                                if k:
                                    print("Impossible")
                                    return
                                k = 1
                                bfs[ni][nj] = 0
                                q.append((ni,nj))
                for i in range(h):
                    for j in range(w):
                        if a[i][j] == "
                            print("Impossible")
                            return
                print("Possible")
                return
    return


def B():

    return


def C():

    return


def D():

    return


def E():

    return


def F():

    return


if __name__ == "__main__":
    A()

Solution (Python):
def main():
    H, W = map(int, input().split())
    A = []
    for _ 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:
        return "Possible"
    return "Impossible"

if __name__ == '__main__':
    print(main())

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

if s == x:
	print("Possible")
else:
	print("Impossible")

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

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

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

Solution (Python):


import sys


tmp = input().split()
h,w = list(map(lambda a: int(a), tmp))


map = [[0 for i in range(w+2)] for j in range(h+2)]

for i in range(0,h):
	hoge = input()
	for j in range(0,w):
		map[i+1][j+1]=hoge[j]

for i in range(1,h+1):

	for j in range(1,w+1):
		if(map[i][j]=="
			if(((map[i+1][j]=="

				if(i!=h or j!=w):
					print("Impossible")
					sys.exit()
			if(((map[i-1][j]=="

				if(i!=1 or j!=1):
					print("Impossible")
					sys.exit()
print("Possible")

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


if __name__ == "__main__":
    main()

Solution (Python):
H, W = map(int, input().split())
now = 0
for _ in range(H):
    A = input()
    for i in range(W):
        a = A[i]
        if a == "
            if i < now:
                print("Impossible")
                exit()
            now = i
        else:
            if i == now:
                print("Impossible")
                exit()
print("Possible")

Solution (Python):


YES = "Possible"  
NO = "Impossible"  


def main():
    h, w = map(int, input().split())
    c = sum([input().count("
    print("Possible" if h + w - 1 == c else "Impossible")

if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
c = sum([input().count("
print("Possible" if h + w - 1 == c else "Impossible")

Solution (Python):


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

a+=[['.']*w]

g=(h,w-2)
cnt=0

i,j=1,1
while i<h or j<w:
    a[i][j]='@'
    if a[i-1][j]=='
        ans='Impossible'
        break

    if (i,j)==g:
        ans='Possible'
        break
        
    if (a[i+1][j]=='
        if a[i+1][j]=='
            i+=1
        else:
            j+=1
    else:
        ans='Impossible'
        break

print(ans)

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

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

count = 0
for i in A:
    count += i.count('

if count != H + W - 1:
    print ('Impossible')
    exit()

def move(i, j): 
    if A[i][j] == '.': 
        return False
    if i == H - 1 and j == W - 1: 
        return True
    if i == H - 1: 
        return move(i, j + 1)
    if j == W - 1: 
        return move(i + 1, j)
    if A[i + 1][j] == A[i][j + 1]: 
        return False 
    if A[i + 1][j] == '
        return move(i + 1, j)
    if A[i][j + 1] == '
        return move(i, j + 1)

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

Solution (Python):
h,*a=open(0);print(("Imp"*(sum(x.count("

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

Solution (Python):
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
x = y = 0
a[0][0] = "."
while True:
    if x + 1 < w and y + 1 < h:
        if a[y][x+1] == a[y+1][x]:
            print("Impossible")
            exit()
        elif a[y][x+1] == "
            x += 1
            a[y][x] = "."
        elif a[y+1][x] == "
            y += 1
            a[y][x] = "."
    elif y + 1 >= h:
        x += 1
        if a[y][x] != "
            print("Impossible")
            exit()
        else:
            a[y][x] = "."
    elif x + 1 >= w:
        y += 1
        if a[y][x] != "
            print("Impossible")
            exit()
        else:
            a[y][x] = "."
    if x == w - 1 and y == h - 1:
        for i in range(h):
            for j in range(w):
                if a[i][j] == "
                    print("Impossible")
                    exit()
        print("Possible")
        exit()

Solution (Python):
h,w=map(int,input().split())
l=[]
for i in range(h):
  l.append(input())
for i in range(h-1):
  for j in range(w-1):
    if l[i][j]=='
      print('Impossible')
      exit()
    if l[i][j]=='.'and l[i][j+1]=='
      print('Impossible')
      exit()
    if l[i][j]=='
      print('Impossible')
      exit()
print('Possible')

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
m = [list(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('Possible')
else:
    print('Impossible')

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

Solution (Python):
H,W = map(int,input().split())
m = []
k = 0
for _ in range(H):
    a = list(input())
    k += a.count('
    m.append(a)
if k == H+W-1:
    sx = sy = 0
    for i in range(H+W-1):
        if   (sx+1<W) and (m[sy][sx+1] == '
        elif (sy+1<H) and (m[sy+1][sx] == '
        else:
            if (sx==W-1) and (sy==H-1):print('Possible')
            else:print('Impossible',sx,sy)
            exit(0)
else:
    print('Impossible')

Solution (Python):
H, W = map(int, input().split())
A = [[] for i in range(H+2)]
for i in range(H):
    A[i+1] = list(input())
    A[i+1].insert(0,'.')
    A[i+1].append('.')

A[0] = list('.' * (W+2))
A[H+1] = list('.' * (W+2))

for i in range(H+2):
    A[i] = ''.join(A[i])
    



check = 0

for i in range(1,H+1):
    for j in range(1, W+1):
        if i == 1 and j ==1 :
            if A[i][j] == '
                if A[i+1][j] == '.' and A[i][j+1] == '
                    pass
                elif A[i+1][j] == '
                    pass
                else:
                    check = 1
                pass
            else:
                check = 1

        elif i == H and j ==W :
            if A[i][j] == '
                if A[i-1][j] == '.' and A[i][j-1] == '
                    pass
                elif A[i-1][j] == '
                    pass
                else:
                    check = 1
                pass
            else:
                check = 1

        else:
            if A[i][j] == '
                if A[i+1][j] == '.' and A[i][j+1] == '
                    pass
                elif A[i+1][j] == '
                    pass
                elif A[i+1][j] == '.' and A[i][j+1] == '
                    pass
                elif A[i+1][j] == '
                    pass
                else:
                    check = 1

if check == 0:
    print('Possible')
else:
    print('Impossible')

Solution (Python):

def end_impossible():
    print("Impossible")
    exit()


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

if A[0][0] == ".":
    end_impossible()

seen.append([0, 0])
h, w = 0, 0

while h != H - 1 or w != W - 1:
    if h < H - 1 and A[h + 1][w] == "
        h += 1
    elif w < W - 1 and A[h][w + 1] == "
        w += 1
    else:
        end_impossible()
    seen.append([h, w])

for i in range(H):
    for j in range(W):
        if A[i][j] == "
            end_impossible()

print("Possible")