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):
from collections import deque

H, W = map(int, input().split())
tiles = [list(input()) for _ in range(H)]
moves_cnt = 0
for h in range(H):
  for w in range(W):
    if tiles[h][w] == '
      moves_cnt += 1

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

moves = deque([(0, 0, 1)])
checked = [[False for _ in range(W)] for _ in range(H)]
checked[0][0] = True
ans = 0
while len(moves) > 0:
  h, w, m = moves.pop()
  if h == H-1 and w == W-1:
    ans = m
    break
  for dh, dw in dhw:
    if h+dh < H and w+dw < W and tiles[h+dh][w+dw] == '
      moves.appendleft((h+dh, w+dw, m+1))
      checked[h+dh][w+dw] = True
if ans == moves_cnt:
  print('Possible')
else:
  print('Impossible')

Solution (Python):
h, w = map(int, input().split()); a = [input() for _ in range(h)]; z = 0
for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            if a[i+1][j] == "
        elif i == h-1 and j == w-1:
            if a[i-1][j] == "
        else:
            if a[i][j] == "
                x = y = 0
                if i != 0:
                    if a[i-1][j] == "
                if j != 0:
                    if a[i][j-1] == "
                if i != h-1:
                    if a[i+1][j] == "
                if j != w-1:
                    if a[i][j+1] == "
                if x != 1 or y != 1: print("Impossible"); z = 1; break
    if z == 1: break
else: print("Possible")

Solution (Python):









import os
import sys




def Possible_or_Impossible(visited, H, W):
    for v in visited:
        if -1 in v:
            return 0
    return 1



def DFS(visited, maze, H, W, u):
    visited[u[0]][u[1]] = 1
    if visited[u[0]+1][u[1]] == -1 and maze[u[0]+1][u[1]] == 1:
        if DFS(visited, maze, H, W, [u[0]+1, u[1]]) == 1:
            return 1
        visited[u[0]+1][u[1]] = -1

    if visited[u[0]][u[1]+1] == -1 and maze[u[0]][u[1]+1] == 1:
        if DFS(visited, maze, H, W, [u[0], u[1]+1]) == 1:
            return 1
        visited[u[0]][u[1]+1] = -1

    if Possible_or_Impossible(visited, H, W) == 1:
        return 1


def main():
    H, W = map(int, input().split())
    maze = [[0]*(W+2)]
    visited = [[0]*(W+2)]
    for _ in range(H):
        S = input()
        S = [0 if s == "." else 1 for s in S]
        V = [0 if s == 0 else -1 for s in S]
        S.insert(0, 0)
        V.insert(0, 0)
        S.append(0)
        V.append(0)
        maze.append(S)
        visited.append(V)
    maze.append([0]*(W+2))
    visited.append([0]*(W+2))
    if DFS(visited, maze, H, W, [1, 1]) == 1:
        print("Possible")
    else:
        print("Impossible")



if __name__ == "__main__":
    main()

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


H, W = list(map(int, input().split()))
A = [input() + '.' for _ in range(H)]
A.append('.' * (W + 1))

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):
from collections import deque
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(input())
num = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "
      num += 1
A = [[0 for j in range(W)] for i in range(H)]
d = deque([[0, 0]])
while len(d) > 0:
  x = d.pop()
  A[x[0]][x[1]] = 1
  if x[0] + 1 < H and S[x[0]+1][x[1]] == "
    d.append([x[0]+1, x[1]])
  if x[1] + 1 < W and S[x[0]][x[1]+1] == "
    d.append([x[0], x[1]+1])
if num == H + W - 1 and A[H-1][W-1] == 1:
  print("Possible")
else:
  print("Impossible")

Solution (Python):
H, W = map(int, input().split())
A = [''] * H
for i in range(H):
    A[i] = input()
x, y = 0, 0
while True:
    if (x < H-1 and A[x+1][y] == '
        print('Impossible')
        exit()
    elif (x > 0 and A[x-1][y] == '
        print('Impossible')
        exit()
    elif x == H-1 and y == W-1:
            print('Possible')
            exit()
    elif (x == H-1 or A[x+1][y] == '.') and (y == W-1 or A[x][y+1] == '.'):
        print('Impossible')
        exit()
    elif x < H-1 and A[x+1][y] == '
        x += 1
        continue
    elif y < W-1 and A[x][y+1] == '
        y += 1
        continue

Solution (Python):
import sys
h,w = map(int,input().split())
ls = [list(input()) for _ in range(h)]
i = 0
j = 0
while True:
    flag = False
    if i > 0:
        if ls[i-1][j] == "
            print("Impossible")
            sys.exit()
    if i < h-1:
        if ls[i+1][j] == "
            if flag == False:
                flag = True
                ls[i][j] = "."
                nx = [0,1,0,0]
            else:
                print("Impossible")
                sys.exit()
    if j > 0:
        if ls[i][j-1] == "
            print("Impossible")
            sys.exit()
    if j < w-1:
        if ls[i][j+1] == "
            if flag == False:
                flag = True
                ls[i][j] = "."
                nx = [0,0,0,1]
            else:
                print("Impossible")
                sys.exit()
    if i == h-1 and j == w-1:
        break
    if nx[1] == 1:
        i += 1
    else:
        j += 1
print("Possible")

Solution (Python):





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

for i in range(H):
    for j in range(W):

        if A[i][j] != "
            continue

        ul = 0
        dr = 0

        if i != 0:
            if A[i - 1][j] == "
                ul += 1
        if i != H - 1:
            if A[i + 1][j] == "
                dr += 1
        if j != 0:
            if A[i][j - 1] == "
                ul += 1
        if j != W - 1:
            if A[i][j + 1] == "
                dr += 1

        if dr > 1 or ul > 1:
            print("Impossible")
            exit()

print("Possible")

Solution (Python):
import sys
def input():
  return sys.stdin.readline().rstrip()

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

count=0
for _ in range(H):
  count+=input().count("
print("Possible" if count==H+W-1 else "Impossible")

Solution (Python):
H,W=list(map(int, input().split()))
A=[list(input()) for _ in range(H)]
for i in range(2**(H+W)):
  L=[['.']*W for _ in range(H)]
  L[0][0]='
  c,d=0,0
  for j in range(H+W):
    if (i>>j)&1:
      c+=1
    else:
      d+=1
    if 0<=c<H and 0<=d<W:
      L[c][d]='
    else:
      break
  for k in range(H):
    if A[k]!=L[k]:
      break
  else:
    print('Possible')
    exit()
else:
  print('Impossible')

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

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

def dfs(x,y):
    field[x][y]='.'
    dx=[0,1]
    dy=[1,0]
    for i in range(2):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx and nx<H and 0<=ny and ny<W and field[nx][ny]=="
            dfs(nx,ny)
            break
    return

dfs(0,0)

for i in range(H):
    for j in range(W):
        if field[i][j]=='
            print('Impossible')
            exit()
print('Possible')

Solution (Python):
h, w = map(int, input().split())
a = [input() for _ in range(h)]
right_limit = [0]*h
for j in range(w):
    if a[0][j] == "
        right_limit[0] = j

for i in range(1, h):
    for j in range(w):
        if right_limit[i-1] > j and a[i][j] == "
            print("Impossible")
            exit()
        if a[i][j] == "
            right_limit[i] = j
print("Possible")

Solution (Python):
import sys, math
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

H, W = mi()
A = [input() for i in range(H)]

s = sum(1 for i in range(H) for j in range(W) if A[i][j] == '
if s == H+W-1:
    print('Possible')
else:
    print('Impossible')

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

    a = []
    for i in range(h):
        a.append(input())

    count = 0

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

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


'''
    for i in range(h):
        a.append(input()+'.')

    a.append('.' * (w-1))

    print(a)
    i = 0
    j = 0
    while True:
        if last == 'up':
            if a[i+1][j] == '
                last = 'up'
                i += 1
            elif a[i+1][j] == '.' and a[i][j+1] == '
                last = 'left'
                j += 1
            else:
                print('Impossible')
                return 0
        if i == h-1 and j == w-1:
            break
        print(i, j)

    print('Possible')
    return 0
'''

if __name__ == "__main__":
    main()


'''

possible判定条件

前のコマの位置（左or上）以外は右or下のみに
コマの移動はすべて連続である
コマの移動数はH+W-1である

'''

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

Solution (Python):
H,W = map(int,input().split())
road = [input()for i in range(H)]
rightest = 0
bottomest = 0
for i in range(H):
    for j in range(W):
        if road[i][j] == '
            if j < rightest:
                print('Impossible')
                exit()
            rightest = j
print('Possible')

Solution (Python):
def dfs(cnt=0, y=0, x=0):
    if y == H-1 and x == W-1:
        if S == cnt+1:
            global naraba
            naraba = True
        return
    for dy, dx in [(1, 0), (0, 1)]:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == "
            V[ny][nx] = True
            dfs(cnt+1, ny, nx)
            V[ny][nx] = False


if __name__ == "__main__":
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    V = [[False]*W for _ in range(H)]
    S = 0
    for a in A:
        S += a.count("
    V[0][0] = True
    naraba = False
    dfs()
    if naraba:
        print("Possible")
    else:
        print("Impossible")

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

for i in range(h):
  for j in range(w):
    if c[i][j]=="
      s+=1
      
a = 1
x = 0
y = 0

while a<s:
  flg = True
  while x+1<w and c[y][x+1]=="
    x+=1
    a+=1
    flg = False
  while y+1<h and c[y+1][x]=="
    y+=1
    a+=1
    flg = False
  if flg:
    break
if a==s:
  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):
    A[i]=A[i]+"."
A.append("."*(W+1))
p,q=1,1
c=1
t=0
for i in A:
    t+=i.count("
if t!=H+W-1:
    c=0
for i in range(H+W-2):
    if A[p-1][q-1]==".":
        c=0
        break
    if A[p][q-1]=="." and A[p-1][q]=="
        q+=1
    elif A[p][q-1]=="
        p+=1
    else:
        c=0
        break
print("Possible" if c else "Impossible")

Solution (Python):
h,w=map(int,input().split());A=[list(input())for _ in "_"*h]
def f(x,y):
  A[x][y]="."
  if x<h-1 and A[x+1][y]<".":return f(x+1,y)
  if y<w-1 and A[x][y+1]<".":return f(x,y+1)
f(0,0);print(['P','Imp']['

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

maze = [[0] for _ in range(h)]
for i in range(h):
    maze[i] = list(input())

flag = True
prev = 0
for row in maze:
    if "
        flag = False
        break
    left = row.index("
    if prev != left:
        flag = False
        break
    for r in range(left,w):
        if row[r] == "
            right = r
        else:
            break
    check_r = w-1-row[::-1].index("
    if check_r != right:
        flag = False
        break
    prev = right
if flag:
    print('Possible')
else:
    print('Impossible')

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

Solution (Python):
h, w = map(int, input().split())
s = []
sh = 0
for i in range(h):
  t = input()
  sh += t.count('
  s.append(t)

visited = [[False for j in range(w)] for i in range(h)]

dx = [0,1]
dy = [1,0]
def dfs(x,y,cnt):
  visited[x][y] = True
  cnt += 1
  if x == h-1 and y == w-1:
    if cnt == sh:
      print ('Possible')
      exit()
    return
  for i in range(2):
    a = x+dx[i]
    b = y+dy[i]
    if a < 0 or b < 0 or a >= h or b >= w or visited[a][b] or s[a][b] == '.':
      continue
    dfs(a,b,cnt)

dfs(0,0,0)

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

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

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

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
H,W = map(int,input().split())
mp = [list(input()) for _ in range(H)]

dw = [1,0]
dh = [0,1]

seen = [[False]*W for _ in range(H)]
def dfs(h,w):
    seen[h][w] = True
    
    nxt_h = h 
    nxt_w = w + 1   
    
    if  not(-1<nxt_w<W) or mp[nxt_h][nxt_w] == '.':
        nxt_h = h + 1
        nxt_w = w 
    
    if not(-1<nxt_h<H):
        return
    if (seen[nxt_h][nxt_w] == True) or (mp[nxt_h][nxt_w] == '.'):
        return
    dfs(nxt_h,nxt_w)
        
dfs(0,0)

result = 'Possible'
for h in range(H):
    for w in range(W):
        if mp[h][w] == '
            if seen[h][w] == False:
                result = 'Impossible'
                break
print(result)

Solution (Python):
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

h, w = inintm()
grid = []
now = [0,0]
fw = 0
fh = 0

for i in range(h):
    grid.append(input())

while now != [h-1,w-1]:
    if now[0] == h-1:
        if fh == 0 and now[1] != 0:
            if grid[h-1][now[1]+1] == "
                now = [h-1, now[1]+1]
                fh = 1
        else:
            if grid[h-1][now[1]+1] == "
                now = [h-1, now[1]+1]
                fh = 1
            else:
                print("Impossible")
                exit()
    elif now[1] == w-1:
        if fw == 0 and now[0] != 0:
            if grid[now[0]+1][w-1] == "
                now = [now[0]+1, w-1]
                fw = 1
            else:
                print("Impossible")
                exit()
        else:
            if grid[now[0]+1][w-1] == "
                now = [now[0]+1, w-1]
                fw = 1
            else:
                print("Impossible")
                exit()
    else:
        if grid[now[0]+1][now[1]] == "
            now = [now[0]+1, now[1]]
        elif grid[now[0]+1][now[1]] == "." and grid[now[0]][now[1]+1] == "
            now = [now[0], now[1]+1]
        else:
            print("Impossible")
            exit()

if fh == 0 and grid[h-1][w-2] == "
    print("Impossible")
    exit()

print("Possible")

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 "Impossible")

Solution (Python):
def search(y,x,oy,ox,r):
    if y == h-1 and x == w-1:
        return r
    l = []
    for i,j in t:
        ny,nx = y+i,x+j
        if (0 <= ny < h and 0 <= nx < w) and not (ny == oy and nx == ox):
            if a[ny][nx] == "
                l.append((ny,nx))

    if 1 < len(l) or len(l) == 0:
        return r
    else:
        r.add((l[0][0],l[0][1]))
        return search(l[0][0],l[0][1],y,x,r)

h,w = map(int,input().split())
a = [list(input()) for i in range(h)]
t = ((0,1),(1,0))

s = search(0,0,0,0,set([(0,0),(h-1,w-1)]))
f = True
for i in range(h):
    for j in range(w):
        if a[i][j] == "
            print("Impossible")
            exit(0)
print("Possible")

Solution (Python):
def check(h, w):
  if A[h][w] != r:
    return True
  if h == H - 1 and w == W - 1:
    return True
  cnt = 0
  if h + 1 < H:
    cnt += A[h + 1][w] == r
  if w + 1 < W:
    cnt += A[h][w + 1] == r
  if cnt != 1:
    return False
  if h == 0 and w == 0:
    return True
  cnt = 0
  if h - 1 >= 0:
    cnt += A[h - 1][w] == r
  if w - 1 >= 0:
    cnt += A[h][w - 1] == r
  if cnt == 0:
    return False
  return True

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

for i in range(H):
  for j in range(W):
    if not check(i, j):
      print("Impossible")
      exit()

print("Possible")

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    h,w = LI()
    shortest = h+w-1
    cnt = 0
    for i in range(h):
        line = S()
        cnt += line.count("
    ans = shortest==cnt 
    print("Possible" if ans else "Impossible")
main()

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

tmp = 0

for i in range(h):
    for j in range(w):
        if l[i][j] == "
            if j < tmp:
                print("Impossible")
                exit()
            else:
                tmp = j


print("Possible")

Solution (Python):
H, W = map(int, input().split())
s = 0
for _ in range(H):
    S = input().rstrip() + "."
    a0 = "."
    A = []
    for i, a in enumerate(S):
        if a==a0:
            continue
        else:
            A.append(i)
        a0 = a
    if len(A) > 2:
        print("Impossible")
        exit()
    if s != A[0]:
        print("Impossible")
        exit()
    s = A[1]-1
print("Possible")

Solution (Python):

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

A = [[c=='

dp = [[False]*W for _ in range(H)]

dp[0][0] = True
def solve():

    s = sum(sum(l) for l in A)
    if s != H+W-1:
        return False

    for d in range(1,H+W):
        if d < W:
            dp[0][d] = dp[0][d-1] and A[0][d]
        if d < H:
            dp[d][0] = dp[d-1][0] and A[d][0]
        for i in range(1,d):
            j = d-i
            if i >= H or j >= W:
                continue
            dp[i][j] = A[i][j] and (dp[i-1][j] or dp[i][j-1])

    return dp[-1][-1]

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

Solution (Python):
import numpy as np
H,W = map(int,input().split())
A = ""
for i in range(H):
  A+=input()
print("Possible" if A.count("

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

h,w=map(int,input().split())
a=[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 or a[0][0]!="
    print("Impossible")
    exit()

now=[0,0]
for i in range(h+w-2):
    if now[0]+1<h and a[now[0]+1][now[1]]=="
        now[0]+=1
    elif now[1]+1<w and a[now[0]][now[1]+1]=="
        now[1]+=1
    else:
        print("Impossible")
        exit()
print("Possible")

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

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

x = 0
y = 0
while x < h or y < w:
    if x < h - 1 and grid[x + 1][y] == "
        grid[x][y] = "."
        x += 1
    elif y < w - 1 and grid[x][y + 1] == "
        grid[x][y] = "."
        y += 1
    else:
        break

if x != h - 1 or y != w - 1:
    print("Impossible")
else:
    grid[x][y] = "."
    for line in grid:
        if "
            print("Impossible")
            quit()
    print("Possible")

Solution (Python):
h,w=map(int,input().split())
s=[input() for _ in range(h)]
v=[[1]*w for _ in range(h)]
q=[(0,0)]
dxy=((-1,0),(0,-1),(1,0),(0,1))
while q:
  x,y=q.pop()
  v[x][y]=0
  cnt=0
  for dx,dy in dxy:
    nx=x+dx
    ny=y+dy
    if not(0<=nx<h and 0<=ny<w) or s[nx][ny]=='.':continue
    elif v[nx][ny] and ((dx==-1 or dy==-1)or cnt):
      print('Impossible')
      exit()
    elif v[nx][ny] :
      q+=[(nx,ny)]
      cnt=1
print(['Possible','Impossible'][v[h-1][w-1]])

Solution (Python):
H, W = map(int, input().split())
A = []
flags = []
for _ in range(H):
    A.append(list(input()))
    flags.append([False] * W)
x, y = 0, 0
flags[0][0] = True
while True:
    nx1, ny1 = x + 0, y + 1
    nx2, ny2 = x + 1, y + 0
    if x == W - 1 and y == H - 1:
        break
    if x == W - 1:
        if A[ny1][nx1] == '
            x, y = nx1, ny1
        else:
            print('Impossible')
            exit()
    elif y == H - 1:
        if A[ny2][nx2] == '
            x, y = nx2, ny2
        else:
            print('Impossible')
            exit()
    else:
        if A[ny1][nx1] == '
            x, y = nx1, ny1
        elif A[ny1][nx1] == '.' and A[ny2][nx2] == '
            x, y = nx2, ny2
        else:
            print('Impossible')
            exit()
    flags[y][x] = True

for x in range(W):
    for y in range(H):
        if A[y][x] == '
            print('Impossible')
            exit()
print('Possible')

Solution (Python):
H, W = map(int, input().split())
A = [list('.'+input()+'.') for _ in range(H)]
if sum(A[i].count('
    print('Impossible')
    exit()
A.append('.'*(W+2))
A.insert(0, '.'*(W+2))
h, w = 1, 1
for i in range(H+W-2):
    n = []
    for j in [(0,-1), (0,1), (-1,0), (1,0)]:
        if A[h+j[0]][w+j[1]] == '
            n.append(j)
    if i == 0 and len(n) != 1 or i > 0 and len(n) != 2:
        print('Impossible')
        exit()
    if i == 0 or hp != h+n[0][0] or wp != w+n[0][1]:
        j = 0
    else:
        j = 1
    hp, wp = h, w
    h, w = h+n[j][0], w+n[j][1]
if h == H and w == W:
    print('Possible')
else:
    print('Impossible')

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

g = []
cnt = 0
for _ in range(h):
    a = input() + "?"
    cnt += a.count("
    g.append(list(a))

if cnt != h+w-1:
    print("Impossible")
    exit()

g.append(["?"]*w)

y, x = 0, 0

for _ in range(h+w-2):
    if g[y+1][x] == "
        y += 1
    elif g[y][x+1] == "
        x += 1
    else:
        print("Impossible")
        exit()
print("Possible")

Solution (Python):
import sys
import queue
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = queue.Queue()
d.put([0, 0, 0])
vals = set()

while not d.empty():
    now = d.get()
    a[now[0]][now[1]] = '.'
    if now[2] in vals:
        print('Impossible')
        sys.exit()
    else:
        vals.add(now[2])
        
    if now[0] == h-1 and now[1] == w-1:
        a1 = [['.']*w for _ in range(h)]
        if a == a1:
            print('Possible')
        else:
            print('Impossible')
        sys.exit()
    else:
        if now[0]+1 < h:
            if a[now[0]+1][now[1]] == '
                d.put([now[0]+1, now[1], now[2]+1])
        if now[1]+1 < w:
            if a[now[0]][now[1]+1] == '
                d.put([now[0], now[1]+1, now[2]+1])        
print('Impossible')

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

Solution (Python):

import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


h, w = LI()
a = []
for _ in range(h):
    a.append(list(S()))

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

count = 0
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == '
            a[j] = 1
        else:
            a[j] = 0
    count += sum(a)
    
if count == w + h - 1:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
h,w=map(int,input().split())
table=[]
for _ in range(h):
  a=input()
  b=[]
  for i in range(w):
    if a[i]=='
      b.append(1)
    else:
      b.append(0)
  table.append(b)
ans=0
for i in range(h):
  ans+=sum(table[i])
if ans==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()) + ["."])
l[-1][w-1] = "g"
l.append(["."]*(w+1))

def dfs(x, y):
    if x == w or y == h or l[y][x] == ".":
        return
    elif l[y][x] == "g":
        print("Possible")
        exit()
    else:
        dfs(x+1, y)
        dfs(x, y+1)

cnt = 0
for i in l:
    for j in i:
        if j == "
            cnt += 1

if cnt == h + w - 2:
    dfs(0, 0)
print("Impossible")

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

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

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

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

Solution (Python):










from collections import deque

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

q = deque()
q.append([0, 0])
visited = [[False]*W for _ in range(H)]
adjacents = [[1, 0], [0, 1]]
while len(q):
    ny, nx = q.popleft()
    
    visited[ny][nx] = True
    if (ny+1 != H and gridgraph[ny+1][nx] == "
        break
    if (ny+1 != H and gridgraph[ny+1][nx] != "
        break
    for dy, dx in adjacents:
        if ny+dy == H or nx+dx == W:
            continue
        if gridgraph[ny+dy][nx+dx] == "
            q.append([ny+dy, nx+dx])
ans = True
for i in range(H):
    for j in range(W):
        if visited[i][j] == False and gridgraph[i][j] == "
            ans = False

if ny == H-1 and nx == W-1 and ans:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
import sys


def go(grid, i, j):
	global H
	global W
	global routes

	if i < H and j < W:
		import copy
		c = copy.deepcopy(grid)

		c[i][j] = '

		if i == H - 1 and j == W - 1:
			routes.append(c)
		else:
			go(c, i + 1, j)
			go(c, i, j + 1)


def merge_grid(grid):
	s = ''

	for line in grid:
		s += ''.join(line)

	return s


H, W = map(int, input().split())
A = []
grid = []

for _ in range(H):
	A.append(input())
	grid.append(['.'] * W)

routes = []
go(grid, 0, 0)

possibles = set()

for route in routes:
	possibles.add(merge_grid(route))

if merge_grid(A) in possibles:
	print('Possible')
else:
	print('Impossible')

Solution (Python):
h,w = map(int,input().split())
c = [0]*(h+2)

r = 0

for i in range(1,h+1):
    c[i] = [0] + list(input()) + [0]
    r += c[i].count("
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

x,y = 1,1

q = 0
ans = 1
while 1:
    if x == h and y == w:
        break
    
    s = 0
    t = 0
    if c[x+1][y] == "
        s = 1
    if c[x][y+1] == "
        t = 1
            
    if s == 1 and t == 1:
        ans = 0
        break
    elif s == 0 and t == 0:
        ans = 0
        break
    elif s == 1:
        x += 1
        q += 1
    else:
        y += 1
        q += 1
if q + 1 != r:
    ans = 0

print(["Impossible","Possible"][ans])

Solution (Python):
H,W = map(int,input().split())
grid = []
X = [['.']*W for _ in range(H)]
for i in range(H):
    grid.append(list(input()))
cur = 0
for i in range(H):
    if grid[i][cur] == '.':
        print('Impossible')
        exit()
    grid[i][cur] = '.'
    if cur != W-1:
        while grid[i][cur+1] == '
            grid[i][cur+1] = '.'
            cur += 1
            if cur == W-1:
                break

if grid != X:
    print('Impossible')
else:
    print('Possible')

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

x = 0
y = 0

while True:
    c = []
    neighbours = 0
    if x != w-1:
        c.append([x+1, y, 1])
    if y != h-1:
        c.append([x, y+1, 3])

    for coords in c:
        if grid[coords[1]][coords[0]] == "
            neighbours += 1
            x2 = coords[0]
            y2 = coords[1]

    if neighbours != 1 and not (x == w-1 and y == h-1):
        print("Impossible")
        break

    c = []
    neighbours = 0
    if x != 0:
        c.append([x-1, y, 0])
    if y != 0:
        c.append([x, y-1, 2])

    for coords in c:
        if grid[coords[1]][coords[0]] == "
            neighbours += 1

    if neighbours > 1:
        print("Impossible")
        break

    if x == w-1 and y == h-1:
        print("Possible")
        break

    x = x2
    y = y2

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

x = 0
y = 0
while True:
    if l[x][y] == "
        l[x][y] = "."
        if y < w-1 and l[x][y+1] == "
            y += 1
        elif x < h-1 and l[x+1][y] == "
            x += 1
        else:
            break
    else:
        break
for i in l:
    if "
        print("Impossible")
        exit()
print("Possible")