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())
cnt = 0
for i in range(h):
    cnt += list(input()).count("

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

Solution (Python):
def dfs(x, y): 
    if x == h-1 and y == w-1:
        a[x][y] = "."
        judge()

    if a[x][y] == "
        a[x][y] = "."

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

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

dfs(0, 0)

Solution (Python):

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

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

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

dfs(0, 0)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

x,y = m()

co = 0

for i in range(x):
    po = input()
    co += po.count("
print("Possible" if x+y - 1 == co else "Impossible")

Solution (Python):
h,w = list(map(int, input().split()))
a = [input() for _ in range(h)]
ftpcount = 0
for i in a:
    ftpcount += i.count('

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

Solution (Python):
"""
def dfs(s):
    global ans
    for u in v:
        x = s[0] + u[0]
        y = s[1] + u[1]
        if x < h and y < w:
            b[x][y] = "
            dfs([x, y])
            b[x][y] = "."
    if a == b:
        ans = 1
    return

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
v = [[1, 0], [0, 1]]
b = [["."] * w for _ in range(h)]
b[0][0] = "
s = [0, 0]
ans = 0
dfs(s)
print("Possible" if ans == 1 else "Impossible")
"""

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
c = 1
for b in a:
    c += b.count("
print("Possible" if c == h + w else "Impossible")

Solution (Python):
def dfs(s):
    global ans
    for u in v:
        x = s[0] + u[0]
        y = s[1] + u[1]
        if x < h and y < w:
            b[x][y] = "
            dfs([x, y])
            b[x][y] = "."
    if a == b:
        ans = 1
    return

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
v = [[1, 0], [0, 1]]
b = [["."] * w for _ in range(h)]
b[0][0] = "
s = [0, 0]
ans = 0
dfs(s)
print("Possible" if ans == 1 else "Impossible")

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

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

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') 
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(sys.stdin.readline()) 
def ifn(): return float(sys.stdin.readline()) 
def isn(): return sys.stdin.readline().split() 
def imn(): return map(int, sys.stdin.readline().split()) 
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) 
def fmn(): return map(float, sys.stdin.readline().split()) 
def iln(): return list(map(int, sys.stdin.readline().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, sys.stdin.readline().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

H,W = imn()
A = [input() for _ in range(H)]

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

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

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

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

count = 0
for h in range(H):
    for w in range(W):
        if map[h][w] == "
            count += 1
if count == H + W - 1:
    print("Possible")
else:
    print("Impossible")

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

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

mvs = [(0,1),(1,0)]

from collections import deque
q = deque()
q.append((0,0))

cnt = 0
for f in fields:
    cnt += f.count("
if cnt != H + W - 1: 
    print("Impossible")
    exit()

while len(q) > 0:
    h,w = q.popleft()
    if h == H-1 and w == W-1:
        print("Possible")
        exit()
    for dh, dw in mvs:
        h_nx = h + dh
        w_nx = w + dw
        if h_nx >= H or w_nx >= W:continue
        if fields[h_nx][w_nx] == ".":continue
        q.append((h_nx,w_nx))
print("Impossible")

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

def dfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[float("inf")] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(1, 0), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist[gy][gx]

count = dfs(0, 0, H-1, W-1)+1
count2 = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '
            count2 += 1
if count == count2:
    print('Possible')
else:
    print('Impossible')

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

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

Solution (Python):
h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(list(input()))
f = False
c = 0
for i in range(h):
    for j in range(w):
        if (a[i][j] == "
            c += 1


def judge(x, y, l: set):
    global a, f
    l.add("{},{}".format(x, y))
    if (x != h - 1):
        if (a[x + 1][y] == "
            judge(x + 1, y, l.copy())
    if (y != w - 1):
        if (a[x][y + 1] == "
            judge(x, y + 1, l.copy())

    if (x == h - 1) and (y == w - 1):
        if (l.__len__() == c):
            f = True


judge(0, 0, set())

print("Possible" if f else "Impossible")

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

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

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

h, w = map(int, input().split())
a = [input().rstrip('\n') 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):
H, W = map(int, input().split())
A = [input() for _ in range(H)]

y, x = 0, 0
c = 0
while True:
    c += 1
    if y == H - 1 and x == W - 1:
        break
    if y < H - 1 and A[y + 1][x] == '
        y += 1
    elif x < W - 1 and A[y][x + 1] == '
        x += 1
    else:
        break

if c == sum(a.count('
    print('Possible')
else:
    print('Impossible')

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

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

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

h, w = MAP()
a = [input() for _ in range(h)]
y = 0
x = 0
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
while y < h and x < w:
    flag = [False for _ in range(4)]
    for i in range(4):
        if 0 <= y + dy[i] < h and 0 <= x + dx[i] < w and a[y + dy[i]][x + dx[i]] == '
            flag[i] = True
    if x == y == 0:
        flag[2] = True
    if x == w - 1 and y == h - 1:
        flag[0] = True
    if flag[0]:
        y += 1
    else:
        x += 1
    if not len(set(flag[0:2])) == len(set(flag[2:4])) == 2:
        print('Impossible')
        exit()
print('Possible')

Solution (Python):

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


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

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

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

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

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

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

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

Solution (Python):
from collections import deque
def bfs(sy,sx,gy,gx):
    q=deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x=q.popleft()
        if [y,x]==[gy,gx]:
            return visited[y][x]
        for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx=y+i,x+j
            if ny<0 or ny>h-1 or nx<0 or nx>w-1:continue
            if path[ny][nx]=="
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])
h,w=map(int,input().split())
path=[input() for i in range(h)]
visited=[[-1]*w for _ in range(h)]
c=0
for p in path:
    for pp in p:
        if pp=='
            c+=1

sy,sx=0,0
gy,gx=h-1,w-1
bfs(sy,sx,gy,gx)
if visited[gy][gx]==h+w-2 and c==h+w-1:
    print('Possible')
else:
    print('Impossible')

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

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

Solution (Python):
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
max_h=0
max_w=0
flag=True
for i in range(h):
    for j in range(w):
        if a[i][j]=="
            if i>max_h:
                max_h=i
            elif i<max_h:
                flag=False
            if j>max_w:
                max_w=j
            elif j<max_w:
                flag=False
print("Possible" if flag==True else 'Impossible')

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

total = sum([1 for a in A for s in a  if s=='
print('Possible' if total == W+H-1 else 'Impossible')

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

right = 0
for A in AA:
    left = A.index('
    if left < right:
        print('Impossible')
        break
    right = W - 1 - A[::-1].index('
else:
    print('Possible')

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

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w = na()
b = 0
for i in range(h):
    a = list(ns())
    b += a.count('

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

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

check = [['.'] * w for _ in range(h)]
check[0][0] = '

def dfs(x,y):
  global flag,check
  if x == h-1 and y == w-1:
    flag = True
    return
  if x != h-1 and maze[x+1][y] == '
    check[x+1][y] = '
    dfs(x+1,y)
    return
  if y != w-1 and maze[x][y+1] == '
    check[x][y+1]= '
    dfs(x,y+1)
    return
  return
dfs(0,0)
if maze == check:
    print('Possible')
else:
    print('Impossible')

Solution (Python):

H, W = map(int, input().split())
board = [['.']*W for i in range(H)]
v_board = [[True]*W for i in range(H)]
sign_count = 0
for i in range(H):
    s = input()
    for j in range(W):
        if s[j]=='
            sign_count += 1
        board[i][j] = s[j]

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

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

c = 0
for i in L:
    c += i.count('
    
if c == H + W - 1:
    print('Possible')
else:
    print('Impossible')

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

L = [list(input()) for i in range(H)]

cnt = 0
for i in L:
    c = i.count("
    cnt += c

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

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

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

r = 0
for i in range(H):
    for j in range(r):
        if A[i][j] == '
            print('Impossible')
            exit(0)

    flag = False
    for j in range(r+1, W):
        if not(flag):
            if A[i][j] == '
                r += 1
            else:
                flag = True
                r = j-1
        else:
            if A[i][j] == '
                print('Impossible')
                exit(0)

print('Possible')

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip("\n") for _ in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "
    if count + 1 == H + W: print("Possible")
    else: print("Impossible")


    return 0

if __name__ == "__main__":
    solve()

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

def func(y, x, cnt):
    if y == h - 1 and x == w - 1:
        cnt += 1
        return y, x, cnt
    if y < h - 1 and a[y + 1][x] == 1:
        cnt += 1
        return func(y + 1, x, cnt)
    if x < w - 1 and a[y][x + 1] == 1:
        cnt += 1
        return func(y, x + 1, cnt)
    if y < h - 1 and a[y + 1][x] == 0:
        return y, x, cnt
    if x < w - 1 and a[y][x + 1] == 0:
        return y, x, cnt

h, w = MAP()
a = [[1 if i == '
s = 0
for i in range(h):
    s += sum(a[i])
y, x, cnt = func(0, 0, 0)
if y == h - 1 and x == w - 1 and cnt == s:
    print('Possible')
else:
    print('Impossible')

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

q_ = 0
for i in range(h):
    flag = 0
    for j in range(w):
        if A[i][j] == '
            p = j
            q = j
            flag = 1
        elif A[i][j] == '
            q = j
        else:
            pass
    if p < q_:
        print('Impossible')
        exit()
    else:
        q_ = q
else:
    print('Possible')

Solution (Python):
from collections import deque

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

que = deque([(0, 0)])
while que:
    h, w = que.popleft()

    A[h][w] = '?'

    if h == H - 1 and w == W - 1:
        break

    if h + 1 < H and A[h + 1][w] == '
        que.append((h + 1, w))
        continue

    if w + 1 < W and A[h][w + 1] == '
        que.append((h, w + 1))
        continue

cnt = sum([a.count('
print('Possible' if cnt == 0 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 cnt == H+W-1:
        print("Possible")
    else:
        print("Impossible")


if __name__ == '__main__':
    main()

Solution (Python):
H, W = map(int, input().split())
A = [input() for _ in range(H)]
s = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == "
            s += 1

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

Solution (Python):
def main():
    height, width = map(int, input().split())
    grid = [list(input()) for _ in range(height)]
    count = 0
    for g in grid:
        count += g.count("
    print("Possible" if count == height + width - 1 else "Impossible")


if __name__ == '__main__':
    main()

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

def linput():
	return list(map(int,input().split()))

def pad(mxy, wall="
	w = len(mxy[0])
	gp = wall*(w+2)
	re = [gp,]
	re_app = re.append
	for vx in mxy:
		re_app(wall+vx+wall)
	re_app(gp)
	return re

def main():
	H,W = linput()
	mM = [input().rstrip() for _ in [0,]*H]
	mM = pad(mM,".")
	mV = [[0,]*(W+2) for _ in [0,]*(H+2)]
	
	vD = [(0,1),(1,0)]
	
	res = False
	cnt = 0
	
	vQ = []
	vQ_app, vQ_pop = vQ.append, vQ.pop
	if mM[1][1]=="
		vQ_app((1,1))
	while vQ:
		x,y = vQ_pop()
		
		if (x,y)==(W,H):
			res = True; mV[H][W] = 1; break
		
		
		t = 0
		for dx,dy in vD:
			nx,ny = x+dx, y+dy
			if mM[ny][nx]=="
			not mV[ny][nx]:
				t += 1
				vQ_app((nx,ny))
		
		if t>0:
			mV[y][x] = 1

		cnt += 1
		
		if cnt>999999: break
	
	if res:
		for vm,vv in zip(mM,mV):
			
			if not all(v for m,v in 
			  zip(vm,vv) if m=="
				res = False; break
	
	print(("Impossible","Possible")[res])
	

if __name__ == "__main__":
	main()

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

H, W = map(int, input().split())
G = [[] for i in range(H*W)]
S = [list(input()) for i in range(H)]
rs = 0
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] == "
        rs += 1
        if h < H-1 and S[h+1][w] == "
            j = (h+1)*W + w
            G[i].append(j)
        if w < W-1 and S[h][w+1] == "
            j = h*W + w+1
            G[i].append(j)

def bfs(s, g) :
    dist = [-1 for _ in range(H*W)]
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for next in G[now] :
            if dist[next] != -1 :
                continue
            else :
                dist[next] = dist[now] + 1
                q.append(next)
    return dist[g]

if bfs(0,H*W-1) == rs-1 :
    print("Possible")
else :
    print("Impossible")

Solution (Python):
h, w = map(int, input().split())
a = [list(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:
    ans = 'Possible'
else:
    ans = 'Impossible'
print(ans)

Solution (Python):

import sys
import copy

def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    H,W = MAP()
    S = [input() for _ in range(H)]
    answerLabel = [[S[i][j]=="

    def dfs(cur,isVisited):
        i,j = cur
        isVisited[i][j] = True
        v = copy.deepcopy(isVisited)
        v2 = copy.deepcopy(isVisited)
        
        if i == H-1 and j == W-1:
            if isVisited == answerLabel:
                print("Possible")
                sys.exit()
            return
        if i+1<H:
            dfs((i+1,j),v)
        
        if j+1<W:
            dfs((i,j+1),v2)
    
    dfs((0,0),[[False]*W for _ in range(H)])

    print("Impossible")
    return

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import copy

def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    H,W = MAP()
    S = [input() for _ in range(H)]
    answerLabel = [[S[i][j]=="

    def dfs(cur,isVisited):
        i,j = cur
        isVisited[i][j] = True
        v = copy.deepcopy(isVisited)
        v2 = copy.deepcopy(isVisited)
        
        if i == H-1 and j == W-1:
            if isVisited == answerLabel:
                print("Possible")
                sys.exit()
            return
        if i+1<H:
            dfs((i+1,j),v)
        
        if j+1<W:
            dfs((i,j+1),v2)
    
    dfs((0,0),[[False]*W for _ in range(H)])

    print("Impossible")
    return

if __name__ == '__main__':
    main()

Solution (Python):
H, W = map(int, input().split())
pos = [0, 0]
S = [input() for i in range(H)]
p = 1
def whiteout(Map, h, w):
  y = 0
  for i in range(h):
    for j in range(w):
      if Map[i][j] == '
        y += 1
  return y == 0

while pos != [H-1, W-1]:
  cnt = 0
  x, y = pos[0], pos[1]
  S[x] = S[x][:y] + '.' + S[x][y+1:]
  if x < H-1:
    if S[x+1][y] == '
      cnt += 1
      pos = [x+1, y]
  if y < W-1:
    if S[x][y+1] == '
      cnt += 1
      pos = [x, y+1]
  if cnt != 1:
    p = 0
    break
S[H-1] = S[H-1][:W-1] + '.'
if p == 1 and whiteout(S, H, W):
  print("Possible")
else:
  print("Impossible")

Solution (Python):
h, w = map(int, input().split())
A = []
for i in range(h):
    A.append(list(input()))
c = 0
for i in range(h):
    for j in range(w):
        if A[i][j] == "
            c += 1
if c > h+w-1:
    print("Impossible")
else:
    i = 0
    j = 0
    f = False
    for _ in range(h+w-1):
        if i + 1 < h  and A[i+1][j] == "
            i += 1
        elif j + 1 < w and A[i][j+1] == "
            j += 1
        if i == h-1 and j == w-1 and A[i][j] == "
            f = True
    print("Possible")

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


i = 0
j = 0

while True:
    if a[i+1][j] == "
        a[i][j] = "."
        i += 1
    elif a[i][j+1] == "
        a[i][j] = "."
        j += 1
    else:
        break
a[i][j] = "."
bl = True
for row in a:
    if "
        bl = False

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

Solution (Python):

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

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

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