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())
As = [list(input()) for i in range(h)]

x,y = 0,0

ans = "Possible"

while True:
    cnt = 0
    tmpX,tmpY = x,y
    
    if (x > 0 and As[y][x-1] == "
        ans = "Impossible"
        break
    
    
    if x < w - 1 and As[y][x+1] == "
        ans = "Impossible"
        break
    
    
    if x < w - 1 and As[y][x+1] == "
        As[y][x] = "."
        x += 1
    
    if y < h - 1 and As[y+1][x] == "
        As[y][x] = "."
        y += 1
        
    
    if x == w - 1 and y == h - 1:
        As[y][x] = "."
        break

    
    if x == tmpX and y == tmpY:
        ans = "Impossible"
        break
        
for A in As:
    if "
        ans = "Impossible"

print(ans)

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

count = 0
for i in range(H):
  for j in range(W):
    if L[i][j] == '
      count += 1
      
if count == W + H - 1:
  print('Possible')
else:
  print('Impossible')

Solution (Python):
input_nums = [int(c) for c in input().split(" ")]
h = input_nums[0]
w = input_nums[1]

count = 0

for i in range(h):
	for c in input():
		if c == "
			count += 1

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

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

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

Solution (Python):


import sys


INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    h, w = LI()
    B = [SI() + '.' for _ in range(h)]
    B.append('.' * w)

    for y in range(h):
        for x in range(w):
            if B[y][x] == '.':
                continue
                
            
            
            
            if B[y][x + 1] == '
                return 'Impossible'
            
            
            
            
            
            if min(y, x) != 0:
                if B[y - 1][x] == '.' and B[y][x - 1] == '.':
                    return 'Impossible'

    return 'Possible'


print(main())

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

Solution (Python):
h,w = map(int, input().split())
aaa = [input().replace('

ans = 'Impossible'
for i in range(h-1):
    
    updown = bin(int(aaa[i],2) & int(aaa[i+1],2))
    if updown.count('1') >1:
        
        break
    
    
    if aaa[i+1].index('1') < aaa[i].rindex('1'):
    
        
        break
else:
    ans = 'Possible'
print(ans)

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

def dfs(i,j):
    if (i,j) == (H-1,W-1): return True
    if i >= H or j >= W or A[i][j] == '.': return
    return dfs(i+1,j) or dfs(i,j+1)

if dfs(0,0) and nS == (H+W-1): print('Possible')
else: print('Impossible')

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

for i in range(h-1):
    for j in range(w-1):
        if board[i][j+1] == "
            print("Impossible")
            exit()
        
print("Possible")

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

l = 1
x = 0
for i in range(H):
    while x<W-1 and A[i][x+1] == '
        x += 1
        l += 1
    if i+1<H and A[i+1][x] == '.':
        print('Impossible')
        exit()
    elif i+1<H:
        l += 1

c = sum(row.count('
print('Possible' if c==l else 'Impossible')

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

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

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

i = 0
j = 0
memo[i][j] = 1
while i < h-1 and j < w-1:
    if a[i+1][j] == "
        print("Impossible")
        exit()
    elif a[i+1][j] == "
        i += 1
        memo[i][j] = 1
    elif a[i][j+1] == "
        j += 1
        memo[i][j] = 1
    else:
        print("Impossible")
        exit()

if i == h-1:
    while j < w-1:
        if a[i][j+1] == ".":
            print("Impossible")
            exit()
        j += 1
        memo[i][j] = 1
else:
    while i < h-1:
        if a[i+1][j] == ".":
            print("Impossible")
            exit()
        i += 1
        memo[i][j] = 1

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

print("Possible")

Solution (Python):
def inpl(): return list(map(int, input().split()))

H, W = inpl()
A = []
for _ in range(H):
    A.append([x=="

A.append([False] * (W+1))

Q = [[0, 0]]
visited = [[False]*(W+1) for _ in range(H+1)]
visited[0][0] = True

while Q:
    h, w = Q.pop()
    for dh, dw in [[0, 1], [1, 0]]:
        nh, nw = h+dh, w+dw
        if A[nh][nw] and not visited[nh][nw]:
            visited[nh][nw] = True
            Q.append([nh, nw])

plength = sum([sum(a) for a in A])

if plength == (H+W-1) and visited[H-1][W-1]:
    print("Possible")
else:
    print("Impossible")

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

Solution (Python):
h, w = map(int, input().split())
c = []
for i in range(h):
    c.append([str(m) for m in list(input())])
pcnt = 0
qcnt = 0
for i in range(h):
    for j in range(w):
        if c[i][j] == "
            for p in range(i + 1, h):
                if c[p][j] == "
                    pcnt = 1
            for q in range(j + 1, w):
                if c[i][q] == "
                    qcnt = 1
            if pcnt == 1 and qcnt == 1:
                print("Impossible")
                exit()
            pcnt = 0
            qcnt = 0
print("Possible")

Solution (Python):

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

print(["Impossible", "Possible"]["".join(A).count("

Solution (Python):
h,w = (int(i) for i in input().split())
a = []
ct = 0
for i in range(h):
  s = input()
  a.append(s)
  ct += s.count('
queue = [(0,0)]
check = []
if a[0][0] == '.':
 print('Impossible')
 exit()
while queue != []:
 i,j = queue[0]
 queue.pop(0)
 if not (i,j) in check:
  if i+1 < h:
   if a[i+1][j] =='
    queue.append((i+1,j))
  if j+1 < w: 
   if a[i][j+1] =='
    queue.append((i,j+1))
  check.append((i,j))
  if i+1 < h and j+1 < w: 
    if a[i+1][j] =='
      break
  if queue != []:
   if queue[0] == (h-1,w-1) and a[h-1][w-1] == '
     if h+w-1 == ct:
      print('Possible')
      exit()
print('Impossible')

Solution (Python):

from collections import deque
H, W = map(int, input().split())
sy,sx = 1,1
gy,gx = H,W
sy-=1
sx-=1
gy-=1
gx-=1
con = [[1,0],[0,1],[-1,0],[0,-1]]
m=[]
d = [[0]*W for _ in range(H)]
for i in range(H):
    a= input()
    m.append(a)
q = deque()
q.append((sy,sx))
d[sy][sx] = 1
s = 0
while len(q)>0:
    y,x = q.popleft()
    if y == gy and x == gx:
        break
    for dx,dy in con:
        if  y+dy>=0 and x+dx >= 0 and y+dy < H and x+dx < W:
            if d[y+dy][x+dx] == 0 and m[y+dy][x+dx] =="
                q.append((y+dy,x+dx))
                d[y+dy][x+dx]+=d[y][x]+1
for i in range(H):
    for j in range(W):
        if m[i][j] == "
if H+W < d[gy][gx] or s > d[gy][gx]:
    print("Impossible")
else:print("Possible")

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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

Solution (Python):


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

cnt = 0
for i in range(H):
    row = input()
    cnt += row.count('

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

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

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

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

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):
def dask(x,y):
  if(a[x][y]=="."):
    return [0,0,False]
  if(a[x+1][y]=="
    for i in range(w):
      if(i>y and a[x][i]=="
        return [0,0,False]
    return [x+1,y,True]
  if(a[x][y+1]=="
    for i in range(h):
      if(i>x and a[i][y]=="
        return [0,0,False]
    return [x,y+1,True]
  return [0,0,False]
h,w=map(int,input().split())
a=[input()+"." for _ in[0]*h]+["."*(w+1)]
x=0
y=0
fl=True
while(fl and (x<h-1 or y<w-1)):
  x,y,fl=dask(x,y)
print("Possible" if fl else "Impossible")

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):
H, W = map(int, input().split())

A = []

for i in range(H):
    tmp = input()
    A.append(tmp)
    
c = 0
    
for i in range(H):
    for j in range(W):
        if A[i][j]=='
            c = c+1
            
if not c==H+W-1:
    print('Impossible')
else:
    print('Possible')

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

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

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

x = 0
y = 0

counts = 0
for item in inputs:
    counts += item.count('

if counts != (H + W - 1):
    ans = 'Impossible'
else:
    for _ in range(H + W - 2):
        if x + 1 < W and inputs[y][x + 1] == '
            x += 1
        elif y + 1 < H and inputs[y + 1][x] == '
            y += 1
    ans = 'Possible' if y == H - 1 and x == W - 1 else 'Impossible'

print(ans)

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

y = 0
x = 0

goal_y = H - 1
goal_x = W - 1

counts = 0
for item in inputs:
    counts += item.count('

if counts != (H + W - 1):
    print('Impossible')
else:
    for _ in range(H + W - 2):
        if x + 1 < W and inputs[y][x + 1] == '
            x += 1
        elif y + 1 < H and inputs[y + 1][x] == '
            y += 1
    print('Possible' if y == goal_y and x == goal_x else 'Impossible')

Solution (Python):
from itertools import combinations
H, W = map( int, input().split())
A = [ list( input()) for _ in range(H)]
for X in combinations([i for i in range(H+W-2)], H-1):
    I = [0]*(H+W-2)
    for i in range(H-1):
        I[X[i]] = 1
    B = [ ["."]*W for _ in range(H)]
    B[0][0] = "
    nowx = 0
    nowy = 0
    for i in range(H+W-2):
        if I[i] == 1:
            if A[nowx+1][nowy] == "
                nowx += 1
        else:
            if A[nowx][nowy+1] == "
                nowy += 1
        B[nowx][nowy] = "
    if nowx == H-1 and nowy == W-1:
        break
ans = "Possible"
for i in range(H):
    for j in range(W):
        if not A[i][j] == B[i][j]:
            ans = "Impossible"

print(ans)

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

x = y = p = 0
while x < W-1 or y < H-1:
    if x < W-1 and src[y][x+1] == '
        p += 1
        x += 1
    elif y < H-1 and src[y+1][x] == '
        p += 1
        y += 1
    else:
        print('Impossible')
        exit()

c = 0
for row in src:
    c += row.count('
print('Possible' if p+1==c else 'Impossible')

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h,w = li()
grid = [lc() for _ in range(h)]

black = 0
for row in grid:
    black += row.count("
                       
print("Possible") if black == h+w-1 else print("Impossible")

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

Solution (Python):

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
route = ""
for _ in range(H):
    route += input()

print("Possible" if route.count("

Solution (Python):
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W] = [int(input_raw[0]), int(input_raw[1])]
    field = []
    for i in range(H):
        input_raw = read_func().strip()
        field.append(input_raw)

    pre_last = -1
    for i in range(H):
        first = -1
        last = -1
        for j in range(W):
            if field[i][j] == '
                if first == -1:
                    first = j
                last = j
        if pre_last > first:
            print "Impossible"
            return
        pre_last = last

    pre_last = -1
    for j in range(W):
        first = -1
        last = -1
        for i in range(H):
            if field[i][j] == '
                if first == -1:
                    first = j
                last = j
        if pre_last > first:
            print "Impossible"
            return
        pre_last = last

    print "Possible"

if __name__ == '__main__':
    main()

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

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



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

    counter = 0
    for _ in range(h):
        s = str(input())
        counter += s.count("

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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

def dfs(maze, cnt, x, y):
    global H, W, count, can
    if x == H-1 and y == W-1:
        if cnt == count:
            can = "Possible"
    for dx, dy in ([1, 0], [0, 1]):
        new_x , new_y = x + dx, y + dy
        if new_x < 0 or new_x >= H or new_y < 0 or new_y >= W:
            continue
        elif maze[new_x][new_y] == '
            cnt += 1
            dfs(maze, cnt, new_x, new_y)
            cnt -= 1

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = []
    for _ in range(H):
        a = [c for c in input()]
        maze.append(a)
    count = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '
                count += 1
    cnt = 1 
    can = "Impossible"
    dfs(maze, cnt, 0, 0)
    print(can)

Solution (Python):
import sys
H,W = map(int, input().split())
x_pos = 0
for _ in range(H):
    a = input()
    for i in range(W):
        if i<x_pos and a[i]=="
            print("Impossible")
            sys.exit()
        if a[i]=="
            x_pos = max(x_pos, i)
print("Possible")

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

def solve():
    for x in range(1, H + 1):
        for y in range(1, W + 1):
            if Ass[x][y] == '.': continue
            isOK_pX = Ass[x - 1][y] == '
            isOK_pY = Ass[x][y - 1] == '
            isOK_nX = Ass[x + 1][y] == '
            isOK_nY = Ass[x][y + 1] == '
            if isOK_pX == isOK_pY or isOK_nX == isOK_nY:
                print('Impossible')
                return
    print('Possible')

solve()

Solution (Python):
H, W = map(int, input().split())
A = [[] for i in range(H)]
check1 = 0
check2 = 1
now = [0, 0]
flag = True

for i in range(H):
    A[i] = input()
    check1 += A[i].count('
    
for iii in range(30000):
    lim = 0
    for dy, dx in [1, 0], [0, 1]:
        lim += 1
        if now[0] + dy <= H-1 and now[1] + dx <= W-1:
            if A[now[0] + dy][now[1] + dx] == '
                check2 += 1
                now[0] += dy
                now[1] += dx
                break
                
        if lim == 2:
            break
                
if check2 == check1:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
h, w = [int(i) for i in input().split()]
adj = [["" for _ in range(w)] for j in range(h)]
for i in range(h):
    _tmp = input()
    for j in range(w):
        adj[i][j] = _tmp[j]

    
for i in range(h):
    for j in range(w):
        if (i > 0 or j > 0) and adj[i][j] == "
            okFlag = False
            if i > 0 and adj[i - 1][j] == "
                okFlag = True
                adj[i - 1][j] = "."
            elif j > 0 and adj[i][j - 1] == "
                okFlag = True
                adj[i][j - 1] = "."
            if not okFlag:
                print("Impossible")
                
                exit()
print("Possible")

Solution (Python):
H, W, A = open(0).read().split(maxsplit=2)
if A.count('
    print('Possible')
else:
    print('Impossible')

Solution (Python):
H, W = map(int, input().split())
pos = 0
for _ in range(H):
    row = input()
    for c in row[:pos]:
        if c == '
            print('Impossible')
            exit()
    for i in range(pos, W):
        if row[i] == '
            pos = i
        else:
            break
    for c in row[pos + 1:]:
        if c == '
            print('Impossible')
            exit()
if pos + 1 == W:
    print('Possible')
else:
    print('Impossible')

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

queue = [(0, 0, 1)]
depth = 0
while queue:
    q = queue.pop(0)
    depth = max(depth, q[2])
    if A[q[0]][q[1]] == ".":
        continue
    if (q[0], q[1]) == (H-1, W-1):
        break
    if(q[0]+1 < H):
        queue.append((q[0]+1, q[1], q[2]+1))
    if(q[1]+1 < W):
        queue.append((q[0], q[1]+1, q[2]+1))

print("Possible" if depth==count else "Impossible")

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


def parse(x, y):
    A[x][y] = '.'
    cand_OK = []
    cand_NG = []
    if x < H - 1:
        cand_OK += [[x + 1, y]]
    if y < W - 1:
        cand_OK += [[x, y + 1]]
    if x > 0:
        cand_NG += [[x - 1, y]]
    if y > 0:
        cand_NG += [[x, y - 1]]
    if any([A[i][j] == '
        return False
    if sum([A[i][j] == '
        return False
    if sum([A[i][j] == '.' for i, j in cand_OK]) == 2:
        return False
    if x == H - 1 and y == W - 1:
        return True
    for i, j in cand_OK:
        if A[i][j] == '
            return parse(i, j)


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

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

x = 0
y = 0

c = 0
a[0][0] = '.'
while x != w-1 or y != h-1:
    r = 0
    if x <= w-2:
        if a[y][x+1] == '
            r = 1
            a[y][x+1] = '.'
    if y <= h-2:
        if a[y+1][x] == '
            r += 2
            a[y+1][x] = '.'
    if x >= 1:
        if a[y][x-1] == '
            r = 0
    if y >= 1:
        if a[y-1][x] == '
            r = 0
    if r == 2:
        y += 1
    if r == 1:
        x += 1
    if x == w-1 and y == h-1:
        if a[y-1][x] == '.' and a[y][x-1] == '.':
            c = 1
    if r == 0 or r == 3:
        c = -1
        x = w-1
        y = h-1

    

    
if c == 1:
    print('Possible')
else:
    print('Impossible')

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

Solution (Python):
h,w = map(int, input().split())
x = 0
for i in range(h):
    cells = input()
    if cells.find('
        x = cells.rfind('
    else:
        print('Impossible')
        exit()
print('Possible')

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

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

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

Solution (Python):
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
x,y=0,0
while(x<h and y<w):
    a[x][y]='.'
    if y+1<w and a[x][y+1]=="
        y+=1
    elif x+1<h and a[x+1][y]=="
        x+=1
    else:
        break
j=True
for b in a:
    for t in b:
        if t=="
            j=False
            break
print("Possible" if j else "Impossible")

Solution (Python):
H,W = map(int,input().split())
h = 0
w = 0
flag = 0
ans = 0
counter = 0
L = []
for i in range(H) :
    l = input()
    counter += l.count("
    L.append(l)

while flag == 0 :
    if h == (H-1) and w == (W-1) :
        ans = 1
        flag = 1
    else :
        if w == (W-1) :
            if L[h+1][w] == "
                h += 1
            else :
                flag = 1
        elif h == (H-1) :
            if L[h][w+1] == "
                w += 1
            else :
                flag = 1
        else :
            if L[h+1][w] == "
                flag = 1
            else :
                if L[h+1][w] == "
                    h += 1
                elif L[h][w+1] == "
                    w += 1
                else :
                    flag = 1
                
if ans == 1 and ((H+W-1) == counter) :
    print("Possible")
else :
    print("Impossible")

Solution (Python):
height, width = map(int, input().split())

arr = []

for i in range(height):
    s = input()
    a = []
    for j in range(width):
        if s[j] == '
            a.append(1)
        else:
            a.append(0)
    arr.append(a)
    
h = 0
w = 0
f = 1

if arr[0][0] == 0:
    h = height-1
    w = width-1
    f = 0

while h < height-1 or w < width-1:
    if h == height-1:
        if arr[h][w+1] == 0:
            f = 0
            break
        else:
            arr[h][w+1] = 0
            w += 1
    elif w == width-1:
        if arr[h+1][w] == 0:
            f = 0
            break
        else:
            arr[h+1][w] = 0
            h += 1
    else:
        if arr[h][w+1] == 0:
            if arr[h+1][w] == 0:
                f = 0
                break
            else:
                arr[h+1][w] = 0
                h += 1
        else:
            if arr[h+1][w] == 1:
                f = 0
                break
            else:
                arr[h][w+1] = 0
                w += 1


if f == 0:
    print('Impossible')
else:
    extra = 0
    for i in range(height):
        for j in range(width):
            extra += arr[i][j]
    if extra > 1:
        print('Impossible')
    else:
        print('Possible')

Solution (Python):
import sys


def main() -> None:
    h, w = [int(next_str()) for _ in range(2)]
    cnt = 0
    for i in range(h):
        cnt += input().count("
    print(["Impossible", "Possible"][cnt == h + w - 1])


def next_str() -> str:
    result = ""
    while True:
        tmp = sys.stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


if __name__ == '__main__':
    main()

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

result = []

for i in range(H):
    a = input()
    result.append(a)

possibility = True

for i in range(H):
    for j in range(W):
        if j != W - 1 and i != H - 1:
            if result[i][j] == "
                possibility = False
        if i != 0 and j !=0:
            if result[i][j] == "
                possibility = False
if possibility:
    print("Possible")
else:
    print("Impossible")

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

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

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

judge = "Possible"
x = 0
y = 0
for i in range(H + W - 2):
	if x == W - 1:
		if A[y + 1][x] == "
			y += 1
		else:
			judge = "Impossible"
			break
	elif y == H - 1:
		if A[y][x + 1] == "
			x += 1
		else:
			judge = "Impossible"
			break

	else:
		if A[y + 1][x] == "
			if A[y][x + 1] == "
				judge = "Impossible"
				break
			else:
				y += 1
		else:
			if A[y][x + 1] == "
				x += 1
			else:
				judge = "Impossible"
				break

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

if s != H + W - 1:
	judge = "Impossible"

if A[0][0] != "
	judge = "Impossible"

if A[H - 1][W - 1] != "
	judge = "Impossible"

print(judge)

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

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(input()) for i in range(h)]
count=0
for i in a:
    count+=i.count('
if count==h+w-1:print('Possible')
else:print('Impossible')

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

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

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

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

a = []
count = 0

for i in range(h):
    a.append(list(input()))
    count += a[i].count("

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

Solution (Python):
t=open(0).read();print(('P'*(t.count('

Solution (Python):
t=open(0).read();print(('P'*(t.count('

Solution (Python):
h,w=map(int,input().split())
s=[input()for _ in[0]*h]
a=[['..','..'],['.
for i in range(h-1):
  for j in range(w-1):
    t=s[i][j:j+2]
    u=s[i+1][j:j+2]
    for b in a:
      if t==b[0]and u==b[1]:
        break
    else:
      print('Impossible')
      exit()
print('Possible')

Solution (Python):
import copy

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

list_check = copy.deepcopy(list_a)
for i in range(0,h):
    for j in range(0,w):
        list_a[i][j] = "."

i = 0
j = 0
while True:
    if i == h-1 and j == w-1:
        list_a[i][j] = "
        break
    if list_check[i][j] == "
        list_a[i][j] = "
        if i != h-1:
            i += 1
        else:
            j += 1
    else:
        i -= 1
        j += 1
        if j > w-1:
            ans = "Impossible"
            break
        if list_check[i][j] == ".":
            ans = "Impossible"
            break
if list_a == list_check:
    ans = "Possible"
else:
    ans = "Impossible"
print(ans)

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

Solution (Python):
H,W = (int(i) for i in input().split())

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

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

Solution (Python):
h, w = map(int, input().split())
A = [input().count('

print('Impossible' if h + w - 1 != sum(A) else 'Possible')