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):
na = lambda: list(map(int, input().split()))
h, w = na()
a = [input() for _ in range(h)]

migi = 0
ans = 1
for s in a:
    for cnt, i in enumerate(s):
        if cnt < migi and i == "
            ans = 0
        if i == "
            migi = cnt
print("Possible" if ans else "Impossible")

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

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

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W = inpl()
MAP = [['.']*(W+2)]
for i in range(H):
	MAP.append(['.'] + list(input()) + ['.'])
MAP.append(['.']*(W+2))

x = y = 1
while x < W or y < H:
	ri = MAP[y][x+1]
	do = MAP[y+1][x]
	le = MAP[y][x-1]
	up = MAP[y-1][x]
	if ri == do or [ri,do,le,up].count('
		print('Impossible')
		sys.exit()
	else:
		if ri == '
			x += 1
		else:
			y += 1


ri = MAP[y][x+1]
do = MAP[y+1][x]
le = MAP[y][x-1]
up = MAP[y-1][x]

if [ri,do,le,up].count('
	print('Impossible')
else:
	print('Possible')

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

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

Solution (Python):
h,w=map(int,input().split());print(["Impossible","Possible"][sum([list(input()).count('

Solution (Python):
H, W = [int(x) for x in input().split()]
A = [input() for i in range(0, H)]
i, j = 0, 0
H, W = H-1, W-1
moveX = [1, 0, -1, 0]
moveY = [0, 1, 0, -1]
while True:
    count = 0
    for k in range(0, 4):
        ii = i+moveX[k]
        jj = j+moveY[k]
        if 0 <= ii and ii <= H and 0 <= jj and jj <= W:
            if A[ii][jj] == '
                count += 1
    invalid = 2 if (not (i==0 and j==0)) and (not(i==H and j==W)) else 1  
    if count > invalid:
        print("Impossible")
        break
    if i < H and A[i+1][j] == '
        i = i+1
        continue
    if j < W and A[i][j+1] == '
        j = j+1
        continue
    if i == H and j == W:
        print("Possible")
        break
    else:
        print("Impossible")
        break

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

def solve(H, W, A):
    ssum = sum(row.count("
    if ssum != H + W - 1:
        return False
    x, y = 0, 0
    if A[y][x] != "
        return False
    while 1:
        if y == H - 1 and x == W - 1:
            return True
        if (x + 1) < W and A[y][x + 1] == "
            x += 1
        elif (y + 1) < H and A[y + 1][x] == "
            y += 1
        else:
            return False

result = solve(H, W, A)

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

Solution (Python):
def chk_ent(r, c, arr):   
    chk_up = (arr[r-1][c] == '
    chk_left = (arr[r][c-1] == '
    
    return (chk_up, chk_left)

def chk_exit(r, c, arr):
    my_h = len(arr)
    my_w = len(arr[0])
    
    chk_down = (arr[r+1][c] == '
    chk_right = (arr[r][c+1] == '
    
    return (chk_down, chk_right)


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

r = 0
c = 0
while True:
    up, left = chk_ent(r, c, a)
    if (not(up or left) and not((r == 0) and (c == 0))) or (up and left):
        flg = False
        break
    down, right = chk_exit(r, c, a)
    if not(down or right):
        if((r == (h - 1)) and (c == (w - 1))):
            flg = True
            break
        else:
            flg = False
            break
    elif (down and right):
        flg = False
        break
    elif right:
        c += 1
    elif down:
        r += 1
print('Possible' if flg else 'Impossible')

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

if a.count("
	print("Possible")
else:
	print("Impossible")

Solution (Python):
h,w=map(int,input().split())
a=[list(input()).count('
print(["Imp","P"][sum(a)==h+w-1]+"ossible")

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

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

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

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

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

    x, flg = (0, -1), False
    for i in range(h):
        for j in range(w):
            if a[i][j] == "
                if i == x[0] and j == x[1] + 1 or i == x[0] + 1 and j == x[1]:
                    x = i, j
                else:
                    break

        else:
            continue
        break

    else:
        flg = True

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


if __name__ == '__main__':
    main()

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

import sys

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

def is_sharp(i, j):
    
    if i<0 or j<0 or i>=H or j>=W:
        return False
    if A[i][j] == "
        return True
    else:
        return False

def ok(i,j):
    if is_sharp(i-1, j) and is_sharp(i,j-1):
        return False
    if is_sharp(i+1, j) and is_sharp(i,j+1):
        return False
    return True

for i in range(H):
    for j in range(W):
        if is_sharp(i,j) and (not ok(i,j)):
            print("Impossible")
            sys.exit(0)
print("Possible")

Solution (Python):
H,W=map(int,input().split())
M=[input() for x 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())
s=[list(input())for i in range(h)]
cnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]=="
            cnt+=1
if cnt<h+w:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
def read():
    return [int(x) for x in str.split(raw_input())]

n, m = read()
st = []
cnt = 0

for i in range(n):
    st.append(raw_input())
    for j in range(m):
        if (st[i][j] == '
            cnt = cnt+1
            
def can_down(st, x, y):
    return x+1 < n and st[x+1][y] == '

def can_right(st, x, y):
    return y+1 < m and st[x][y+1] == '

def dfs(st, x, y, c):
    if (x == n-1 and y == m-1):
        return c == cnt
    down, right = can_down(st, x, y), can_right(st, x, y)
    if (down and right):
        return 0
    if ((not down) and (not right)):
        return 0
    if (down):
        return dfs(st, x+1, y, c+1)
    if (right):
        return dfs(st, x, y+1, c+1)

if (dfs(st, 0, 0, 1) == 1):
    print("Possible")
else:
    print("Impossible");

Solution (Python):
import sys
H,W = [int(i) for i in input().split()]
A = [list(input().strip()) for j in range(H)]

q = [(0,0)]
while q:
  h,w = q.pop()
  if (h,w) == (H-1,W-1):
    A[h][w] = '.'
    break
  for dh,dw in [(1,0),(0,1)]:
    nh,nw = h+dh,w+dw
    if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '
      q.append((nh,nw))
      A[h][w] = '.'
      break
  else:
    print('Impossible')
    sys.exit()

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

Solution (Python):






if __name__ == '__main__':
    h, w = list(map(int, input().split()))
    board = [input() for i in range(h)]
    count = sum([board[i].count('

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

Solution (Python):
def sarch(s):
    key = 0
    for i in range(len(s)):
        if s[i] == "
            key = i
    return key

def judge(s):
    key = 0
    for i in s:
        if i == "
            key = 1
            break
    return key

H, W = map(int, input().split())
A = [["0" for i in range(W)] for j in range(H)]
for i in range(H):
    S = input()
    for j in range(W):
        A[i][j] = S[j]
key = "Possible"
for i in range(1, H):
    if judge(A[i][0:sarch(A[i - 1])]) != 0:
        key = "Impossible"
        break
print(key)

Solution (Python):
h,w=[int(i) for i in input().split()]
s=0
l=0
for i in range(h):
  sf=True
  lf=False
  a=list(input().strip())
  for j in range(w):
    if a[j]=="
      s=j
      sf=False
      if s!=l and i!=0:
        print("Impossible")
        exit()
    if a[j]=="
      print("Impossible")
      exit()
    if a[j]=="." and sf==False and lf==False:
      l=j-1
      lf=True
  if sf==True:
    print("Impossible")
    exit()
  if lf==False:
    l=w-1
else:
  print("Possible")

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

Solution (Python):
H, W = map(int, input().split())
a = ['.'*(W+2)]
for i in range(H):
    a.append('.'+input()+'.')
a.append('.'*(W+2))
x, y = 1, 1
d = [0, 1], [1, 0]


while True:
    
    a[x] = a[x][:y] + '*' + a[x][y+1:]
    
    if [x, y] == [H, W]:
        break
    
    
    for d_i in d:
        if a[x+d_i[0]][y+d_i[1]]=='
            x, y = x+d_i[0], y+d_i[1]
            break
    
    else:
        break
    
    

end = 0
for r_i in a:
    for j in r_i:
        if j == '
            print('Impossible')
            end = 1
            break
    if end == 1:
        break
else:
    print('Possible')

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

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

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

print("Possible")

Solution (Python):
from queue import Queue
import numpy as np

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

B = []
for i in range(H):
    B_sub = []
    for j in input():
        if j == "
        else: B_sub.append(-1)
    B.append(B_sub)
    
qy,qx = Queue(),Queue()
qy.put(0)
qx.put(0)

isok = True
while(isok):
    if qy.empty() and qx.empty(): break
    else:
        y,x = qy.get(),qx.get()
        if y==0 and x==0: B[y][x] = 0

        if y<H-1 and B[y+1][x]==5:
            B[y+1][x] = 0
            qy.put(y+1)
            qx.put(x)
            if 5 in B[y]: isok = False
        elif x<W-1 and B[y][x+1]==5:
            B[y][x+1] = 0
            qy.put(y)
            qx.put(x+1)
            if 5 in np.array(B).T[x]: isok = False
            
            
if isok:
    print("Possible")
else:
    print("Impossible")

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

count = h+m

for i in range(h):
    b =(list(input()))
    count -= b.count('
if count == 1:
    print('Possible')
else:
    print('Impossible')

Solution (Python):


import sys, math, copy




HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def main():
    h, w = map(int, input().split())
    su = 0
    for i in range(h):
        line = input()
        su += line.count("
    print("Possible" if su == h + w - 1 else "Impossible")

main()

Solution (Python):





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

x=0
for i in range(h):
    for j in range(x,w):
        
        if m[i][j] == '
            
            m[i][j]='.'
            x=j
        else:
            break
result="Possible"
for i in range(h):
    for j in range(w):
        if m[i][j] == '
            result="Impossible"

print(result)

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

shortest = (H-1) + (W-1)
tmp = -1
for i in range(H):
    tmp += input().count("

print("Possible" if tmp == shortest else "Impossible")

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

    
    
    
    p = [0] * (H + W - 2)

    def dfs(i):
        if i == H + W - 2:
            
            if p.count(1) != H-1 or p.count(0) != W-1:
                return False

            b = [
                ["."] * W
                for _ in range(H)
            ]
            x, y = (0, 0)
            b[0][0] = "
            for c in p:
                if c == 1:
                    y += 1
                else:
                    x += 1
                b[y][x] = "

            return A == b

        p[i] = 0
        if dfs(i + 1):
            return True
        p[i] = 1
        if dfs(i + 1):
            return True

        return False

    if dfs(0):
        print("Possible")
    else:
        print("Impossible")


if __name__ == '__main__':
    main()

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


def enclose_field(field, outline="
    """
    迷路等の外周をoutlineで埋めることで、IndexErrorを回避できます。
    [0, 0] → [1, 1]、[H-1, W-1] → [H, W]となります。
    """
    for i in range(len(field)):
        field[i] = [outline] + field[i] + [outline]
    field.append([outline] * (len(field[0])))
    field.insert(0, [outline] * (len(field[0])))
    return field


A = enclose_field(A, outline=".")
i = j = 1
while True:
    if A[i+1][j] == "
        A[i][j] = "."
        i += 1
        continue

    if A[i][j+1] == "
        A[i][j] = "."
        j += 1
        continue

    if i==H and j == W:
        A[i][j] = "."
        break

    print("Impossible")
    exit()

for a in A:
    if "
        print("Impossible")
        break
else:
    print("Possible")

Solution (Python):
import sys


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

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

Solution (Python):
h,w = map(int,input().split())
meiros = [['' for x in range(w)] for y in range(h)]
for i in range(h):
  tmp = input().rstrip()
  for j in range(w):
    meiros[i][j] = tmp[j]
nowh,noww = 0,0
queue = [(0,0)]
flg = True
while 1:
  L = len(queue)
  if L == 0:
    break
  for z in range(L):
    nowh,noww = map(int,queue[0])
    queue.pop(0)
    if nowh + 1 < h:
      if meiros[nowh+1][noww] == '
        queue.append((nowh+1,noww))
    if noww + 1 < w:
      if meiros[nowh][noww+1] == '
        queue.append((nowh,noww+1))
    meiros[nowh][noww] = '.'
  if nowh != (h-1) and noww != (w-1) and len(queue) != L:
    flg = False
    break
for mairo in meiros:
  if '
    flg = False
    break
if flg:
  print('Possible')
else:
  print('Impossible')

Solution (Python):
h,w = map(int,input().split())
x = 0
y = 0
time = 0
cou = 0
lis = ""
for i in range(h):lis += str(input())
for i in range(h * w):
    if lis[i] == "
        cou += 1
for i in range(h):
    while lis[i * w + x] == "
        x += 1
        time += 1
        if x == w:
            x -= 1
            y = 1
    if i == h-1 and time == (h + w)-1 and time == cou:
        print("Possible")
        exit()
    time += 1
print("Impossible")

Solution (Python):
def isAble(a, r, c):
    lastC = 1
    for i in xrange(r):
        lowbit = a[i]&-a[i]
        if popcount(a[i]+lowbit)!=1:
            return False
        if lowbit!=lastC:
            return False
        lastC = (a[i]+lowbit)>>1
    if lastC!=(1<<(c-1)):
        return False
    return True

def popcount(x):
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f)
    x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff)
    x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff)
    return x

def main():
    r, c = [int(x) for x in raw_input().strip().split()]
    a = []
    for i in xrange(r):
        row = raw_input().strip()
        foo = 0
        for j in xrange(c):
            if row[j]=='
                foo |= 1<<j
        a.append(foo)
    if isAble(a, r, c):
        print 'Possible'
    else:
        print 'Impossible'

if __name__ == '__main__':
    main()

Solution (Python):
H, W = map(int, input().split())
A = [[i for i in input()]for j in range(H)]
B = [["." for i in range(W)]for i in range(H)]
B[0][0] = "
x = 0; y = 0
while(True):
    if x == H-1 and y<W-1:
        if A[x][y+1] == "
            y += 1
        else:
            break
    elif x<H-1 and y == W-1:
        if A[x+1][y] == "
            x += 1
        else:
            break
    elif x==H-1 and y==W-1:
        B[x][y] = "
        break
    else:
        if A[x][y+1] == "
            y += 1
        elif A[x+1][y] == "
            x += 1
        else:
            break
    B[x][y] = "
for i in range(H):
    for j in range(W):
        if A[i][j]!=B[i][j]:
            print("Impossible")
            exit()
print("Possible")

Solution (Python):
from collections import Counter
H,W = map(int,input().split())
src = [input() for i in range(H)]
ctr = Counter()
for row in src:
    ctr.update(row)
print('Possible' if ctr['

Solution (Python):

H, W = map(int, input().split())
cnt = ''.join([input() for _ in range(H)]).count('
print(('Impossible', 'Possible')[cnt == H + W - 1])

Solution (Python):

H, W = map(int, input().split())
a = [''] * H
cnt = 0
for i in range(H):
    a[i] = list(input())
    cnt += len(list(filter(lambda x: x == '

ans = False
if cnt == H + W - 1:
    y, x = 0, 0
    d = [1, 0, 1]
    for i in range(cnt):
        if y == H - 1 and x == W - 1:
            ans = True
            break
        for j in range(2):
            ny = y + d[j]
            nx = x + d[j + 1]
            if ny < H and nx < W and a[ny][nx] == '
                y, x = ny, nx
                break



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

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

A = [input() for _ in range(H)]
length = sum([a.count('

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

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

A = [list(input()) for _ in range(H)]
length = 0
for a in A:
    for s in a:
        if s == '
            length += 1


def dfs(i, j, cnt):
    if i == H - 1 and j == W - 1:
        return cnt == length - 1
    else:
        if i < H - 1 and A[i + 1][j] == '
            return dfs(i + 1, j, cnt + 1)
        elif j < W - 1 and A[i][j + 1] == '
            return dfs(i, j + 1, cnt + 1)
        else:
            return False


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

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


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


if __name__ == '__main__':
    main()

Solution (Python):

h, w = map(int, input().split())
a = [ input() for _ in range(h) ]
result = ''.join(a).count('
print(['Impossible', 'Possible'][result])

Solution (Python):
def shik_stone():
	h, w = map(int, raw_input().split(" "))
	m = []
	for i in range(h):
		m.append(str(raw_input()))
	current_most_right_index = 0
	for row in m:
		indices = [i for i, ltr in enumerate(row) if ltr == '
		if min(indices)==current_most_right_index:
			if len(indices)!=(max(indices)-min(indices)+1):
				print "Impossible"
				return
			else:
				current_most_right_index = max(indices)
		else:
			print "Impossible"
			return
	print "Possible"


if __name__ == "__main__":
	shik_stone()

Solution (Python):

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

cnt = 0
for h in range(H):
    for w in range(W):
        if m[h][w] == '
            cnt += 1

def rec(x, y):
    if x == W - 1 and y == H - 1:
        return True

    if m[y][x] != '
        return False
    dx = [0, 1]
    dy = [1, 0]

    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < W and \
           0 <= ny and ny < H:
            ret = rec(nx, ny)
            if ret:
                return ret
    return False


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

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

Solution (Python):
h,w = map(int, raw_input().split())
m = [raw_input() for _ in range(h)]
possible = True
for y in range(h):
    for x in range(w):
        if m[y][x] == '
            p = 0
            if y > 0 and m[y-1][x] == '
                p += 1
            if x > 0 and m[y][x-1] == '
                p += 1
            if not(y == 0 and x == 0) and p != 1:
                possible = False
                break
            n = 0
            if y < h-1 and m[y+1][x] == '
                n += 1
            if x < w-1 and m[y][x+1] == '
                n += 1
            if not(y == h-1 and x == w-1) and n != 1:
                possible = False
                break
    if not possible:
        break
if possible:
    print 'Possible'
else:
    print 'Impossible'

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

    l = H + W - 1
    sharp = 0
    i = 0
    while i < H:
        A = str(input())
        sharp += A.count('
        i += 1

    if l == sharp:
        print('Possible')
    else:
        print('Impossible')

main()

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

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

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

Solution (Python):
H, Y = map(int, input().split())
P = 0
out = "Possible"
for i in range(H):
	inp = input()
	for j in range(Y):
		if inp[j] == "
			P = j
		if inp[j] == "
			out = "Impossible"
print(out)

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

for i in range(h):
    for j in range(w):
        if a[i][j] == '
            a[i][j] = '.'
            break

for i in range(1,w):
    for j in range(h):
        if a[j][i] == '
            a[j][i] = '.'
            break

def check():
    for i in range(h):
        for j in range(w):
            if a[i][j] == '
                return 0;
    return 1;

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

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

def fun(aa,x,y):
    a=copy.deepcopy(aa)

    if h<=y or w<=x:
        return False

    if y==h-1 and x==w-1:
        count = 0
        for i in a:
            count += i.count('
        if count==1:
            return True
        else:
            return False

    if a[y][x]!="
        return False

    a[y][x]="."

    if fun(a,x+1,y) or fun(a,x,y+1):
        return True

    return False

a=[["" for i in range(w)] for j in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        a[i][j]=s[j]



print("Possible" if fun(a,0,0) else "Impossible")

Solution (Python):
def feasible():
    n, m = map(int, raw_input().split())
    g = [ raw_input().strip() for r in range(n) ]
    start = 0
    for row in g:
        in_row = False
        found_row = False
        for c, ch in enumerate(row):
            if ch == '.':
                in_row = False
                continue
            if c < start:
                return False
            if not in_row and found_row:
                return False
            in_row = True
            found_row = True
            start = c
    return True
                
print('Possible' if feasible() else 'Impossible')

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

def dfs(i, j):
    if(i == h-1 and j == w-1):
        return 'Possible'
    if(i < h-1 and A[i+1][j] == '
        return dfs(i+1, j)
    if(j < w-1 and A[i][j+1] == '
        return dfs(i, j+1)
    return 'Impossible'

if sum([a.count('
    print('Impossible')
else:
    print(dfs(0, 0))

Solution (Python):


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

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

arr=[]
arr.append([".","
for _ in range(h):
    arr.append(["."]+list(input())+["."])
arr.append(["."]*w+["



for i in range(h):
    for j in range(w):
        if arr[i+1][j+1]=='
            if arr[i][j+1]==arr[i+1][j] or arr[i+2][j+1]==arr[i+1][j+2]:
                print("Impossible")
                exit(0)

print("Possible")

Solution (Python):
list = input().split()
h = int(list[0])
w = int(list[1])

k = 0
for i in range (0,h):
   k += input().count("

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

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

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7


def f():
    h,w = list(map(int, input().split()))
    a = [input() for _ in range(h)]
    c = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == '
                c += 1
    if c == h + w -1:
        return 'Possible'
    return 'Impossible'


print(f())

Solution (Python):
h,w=map(int,input().split());print("Possible"if sum([input().count("

Solution (Python):
h,w=map(int,input().split())
sharp=0
for i in range(h):
    row=str(input())
    sharp += row.count('

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

Solution (Python):
def dfs(l,x,y):
    
    if x+1 is w and y+1 is h:
        return l
    
    
    if w > x+1:
        if "

            l2 = list(l)
            l2[y][x+1] = "."

            return dfs(l2,x+1,y)

    
    if h > y+1:
        if "
            l3 = list(l)
            l3[y+1][x]= "."
            return  dfs(l3,x,y+1)



h,w = map(int,raw_input().split())


l = []
for i in range(h):
    l.append(list(raw_input()))


l[0][0] = "."
l2 = dfs(l,0,0)

if l2:
    if "
        print "Impossible"
    else:
        print "Possible"
else:
    print "Impossible"

Solution (Python):
import sys
h, w = map(int, input().split())
i = 0
pos = 0
while h > i:
    s = input()
    l = s.find('
    r = s.rfind('
    if (l == pos and r >= pos):
        pos = r
        i += 1
    else:
        print('Impossible')
        sys.exit()
print('Possible')

Solution (Python):
from sys import stdin

nbLig,nbCol=map(int,stdin.readline().split())
grille=[]
possible=[[-1]*nbCol for i in range(nbLig)]
possible[0][0]=0
for i in range(nbLig):
    ligne=stdin.readline()
    grille.append(ligne)
compteur=0
cases=0
for lig in range(nbLig):
    for col in range(nbCol):
        if grille[lig][col]=="
            cases+=1
            maximum=-1
            if lig>0:
                maximum=max(maximum,possible[lig-1][col])
            if col>0:
                maximum=max(maximum,possible[lig][col-1])
            possible[lig][col]=maximum+1

if cases==possible[nbLig-1][nbCol-1]:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
import sys
lines = sys.stdin.readlines()
sizes = lines[0].split(" ")
H = int(sizes[0])
W = int(sizes[1])
field = []
for line in lines[1:]:
    field.append(line.rstrip())


count=0
for f in field:
    for i in range(W):
        s = f[i:i+1]
        if s=="
            count+=1


posQ = [[0,0]]

now = [0,0]
before = [-1,0]

while(now[0]+1<H or now[1]+1<W):
    if (before==now):
        break
    
    if now[1]+1<W:
        if field[now[0]][now[1]+1:now[1]+2] == "
            posQ.append([now[0],now[1]+1])
    if now[0]+1<H:
        if field[now[0]+1][now[1]:now[1]+1] == "
            posQ.append([now[0]+1,now[1]])
    before = now
    now = posQ[len(posQ)-1]

"""
now = [0,0]

if field[now[0]][now[1]+1:now[1]+2] == "
    posQ.append([now[0],now[1]+1])
if field[now[0]+1][now[1]:now[1]+1] == "
    posQ.append([now[0]+1,now[1]])

now = posQ[len(posQ)-1]

if field[now[0]][now[1]+1:now[1]+2] == "
    posQ.append([now[0],now[1]+1])
if field[now[0]+1][now[1]:now[1]+1] == "
    posQ.append([now[0]+1,now[1]])


"""



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