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 itertools import combinations
H,W = map(int,input().split())
grid = [0] * H
for i in range(H):
    grid[i] = list(input())
res = 'Impossible'

move_indexes = [i for i in range(H+W-2)]

for y_move in combinations(move_indexes,H-1):
    now_y, now_x = 0,0
    reached = [[0]*W for _ in range(H)]
    reached[0][0] = 1
    for i in range(H+W-2):
        
        if i in y_move:
            now_y += 1
        else:
            now_x += 1
        reached[now_y][now_x] = 1
    can = True
    for i in range(H):
        for j in range(W):
            if (not reached[i][j] and grid[i][j]=='
                can = False
    if can:
        res = 'Possible'
        break

print(res)

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

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

cnt = 0

for _ in range(h):
    s = input()
    cnt += s.count('

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

Solution (Python):
import collections, sys

h, w = map(int, input().split())
count = 0
a = []
a.append("." * (w + 2))
for i in range(h):
    temp = input()
    a.append("." + temp + ".")
    count += temp.count("
a.append("." * (w + 2))
if count != h + w - 1:
    print("Impossible")
else:
    queue = collections.deque([[1, 1]])
    d = [[1, 0], [0, 1]]
    while queue:
        test = queue.popleft()
        for i in d:
            x = test[0] + i[0]
            y = test[1] + i[1]
            if (x, y) == (w, h):
                print("Possible")
                sys.exit()
            else:
                if a[y][x] == "
                    queue.append([x, y])
    else:
        print("Impossible")

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

A = [list(input()) for i in range(H)]
flag = True
endi = 0
for i in range(H):
    if A[i].index('
        for j in range(W):
            if A[i][j] == '
                endi = j
        continue
    flag = False
    break


if flag:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
H,W=map(int,input().split())
ans='Impossible'
j=0

for i in range(H):
  A=[x for x in input()]
  count=A.count('
  if i==0 and A[0]=='.':
    break
  try:
    if i>0 and '
      break
    else:
      if i==0:
        if count!=A[:count].count('
        	break
      elif count!=A[j:j+count].count('
        break
  except:
    j+=(count-1)
    pass
  j+=(count-1)
else:
  ans='Possible'
print(ans)

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

Solution (Python):
from collections import deque


def main():
    H, W = list(map(int, input().split()))
    A = [list(input()) for _ in range(H)]
    
    
    
    que = deque()
    que.append((0, 0))
    ok = False
    while len(que) > 0:
        h, w = que.pop()
        A[h][w] = '.'
        if (h, w) == (H - 1, W - 1):
            ok = True
            break
        
        next_h, next_w = h, w + 1
        if next_w < W and A[next_h][next_w] == '
            exist_unvisited = False
            for hh in range(next_h, H):
                if A[hh][w] == '
                    exist_unvisited = True
                    break
            if exist_unvisited:
                break
            que.append((next_h, next_w))
            continue
        
        next_h, next_w = h + 1, w
        if next_h < H and A[next_h][next_w] == '
            exist_unvisited = False
            for ww in range(next_w, W):
                if A[h][ww] == '
                    exist_unvisited = True
                    break
            if exist_unvisited:
                break
            que.append((next_h, next_w))
            continue
    if ok:
        print('Possible')
    else:
        print('Impossible')


if __name__ == '__main__':
    main()

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

IsPossible=True
res=[]
for y in range(H):
    left=-1
    right=0
    for x in range(W):
        if A[y][x]=='
            if left<0:
                left=x
                right=x
            else:
                if x-right==1:
                    right=x
                else:
                    IsPossible=False
                    break
    res.append((left,right))

for y in range(1,H):
    if res[y-1][1]!=res[y][0]:
        IsPossible=False

if IsPossible:
    print('Possible')
else:
    print('Impossible')

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

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

Solution (Python):
import sys
def S(): return sys.stdin.readline().rstrip()
def IL(): return map(int,sys.stdin.readline().rstrip().split())

if __name__=='__main__':
    h,w = IL()
    m = [S() for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if i==h-1 or j==w-1:
                continue
            if m[i][j+1]=='
                print('Impossible')
                exit()
    print('Possible')
    exit()

Solution (Python):






dxdy = [[1,0],[0,1]]


def solve(h,w,board):
  sharp_count = sum(x.count("
  def dfs(y,x,gy,gx,cnt=1):
    if y == gy and x == gx:
      return cnt

    if not 0 <= y < h or not 0 <= x < w:
      return 0
    if board[y][x] == ".":
      return 0
    return  dfs(y+1,x,gy,gx,cnt+1) + dfs(y,x+1,gy,gx,cnt+1)
  
  return dfs(0,0,h-1,w-1) == sharp_count



def main():
  H,W = map(int,input().split())
  board = [input() for _ in range(H)]
  print("Possible" if solve(H,W,board) else "Impossible")
  return

if __name__ == '__main__':
  main()

Solution (Python):
H,W=map(int,input().split())
A=[list(input()) for _ in range(H)]
h=0
w=0
ans="Possible"
for i in range(H):
  for j in range(W):
    if A[i][j]=="
      if (i==h and j-w<2) or (i-h<2 and j==w):
        h=i
        w=j
      else:
        ans="Impossible"
print(ans)

Solution (Python):
h, w = map(int, input().split())
a = [input() for _ in range(h)]
now = 0
ng = 0
for i in range(h):
    
    
    extended = 0
    if a[i][now] != "
        ng = 1
        
        break
    for j in range(now, w):
        if not extended:
            if a[i][j] == "
                now = j
            else:
                extended = 1
        else:
            if a[i][j] == "
                
                ng = 1
                break
        if i == h - 1 and j == w - 1 and a[i][j] == ".":
            ng = 1
    if ng:
        break
if ng:
    print("Impossible")
else:
    print("Possible")

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

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


def dfs(maze, visited, sh, sw):
    stack = deque([[sh, sw, 0]])
    visited[sh][sw] = 1
    while stack:
        h, w, t = stack.pop()
        if h == H-1 and w == W-1: 
            return
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): 
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W: 
                continue
            elif maze[new_h][new_w] != "." and \
                visited[new_h][new_w] == 0: 
                visited[new_h][new_w] = 1
                stack.append([new_h, new_w, t+1])
    

visited = [[0]*W for _ in range(H)]
dfs(lst1, visited, 0, 0)

flag = 1
for i in range(H):
    for j in range(W):
        if not ((lst1[i][j] == "." and visited[i][j] == 0) \
        or (lst1[i][j] == "
            flag = 0
            break
res = 0
for i in lst1:
    res += i.count("

if flag and res == H+W-1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
H,W = map(int,input().split())
num = 0
for i in range(H):
    a = input()
    if "
        print("Impossible")
        exit()
    cnt = -1
    for j in range(num, W):
        if a[j] == "
            cnt += 1
        else:break
    num += cnt
    if "
        print("Impossible")
        exit()
print("Possible")

Solution (Python):
from collections import deque
dx=[0,1]
dy=[1,0]
def bfs(x,y):
    que=deque([(x,y)])
    while(que):
        nx,ny=que.popleft()
        seen[nx][ny]=True
        if (nx+1<H-1 and G[nx+1][ny]=='
            return False
        elif nx+1<H and G[nx+1][ny]=='
            que.append((nx+1,ny))
            continue
        elif ny+1<W and G[nx][ny+1]=='
            que.append((nx,ny+1))
            continue
        else:
            if nx==H-1 and ny==W-1:
                return True
            else:
                return False
    return True


memo={}
H,W=map(int,input().split())
G=[list(input()) for i in range(H)]
seen=[[False]*W for i in range(H)]
isok=bfs(0,0)
for i in range(H):
    for j in range(W):
        if G[i][j]=='
            isok=False
print("Possible" if isok else "Impossible")

Solution (Python):
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

h,w = readInts()
a = [list(input()) for i in range(h)]
check = [["."]*w for i in range(h)]
check[0][0]="

now = (0,0)
goal = (h-1,w-1)

while 1:
  if now==goal and check==a:
    print("Possible")
    break
  s = (now[0],now[1]+1)
  t = (now[0]+1,now[1])
  if s[1]<w and a[s[0]][s[1]]=="
    check[s[0]][s[1]]="
    now = s
  elif t[0]<h and a[t[0]][t[1]]=="
    check[t[0]][t[1]]="
    now = t
  else:
    print("Impossible")
    break

Solution (Python):

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

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

ans='Possible'
i=1
while i<H:
    j=1
    while j<W:
        if A[i][j-1]=='
            ans='Impossible'
        j+=1
    i+=1

print(ans)

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

Solution (Python):

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

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

def dfs(h, w):
    global cnt
    cnt += 1
    if h+1 < H and A[h+1][w] == '
        dfs(h+1, w)
    elif w+1 < W and A[h][w+1] == '
        dfs(h, w+1)

cnt = 0

if A[0][0] == '.':
    print('Impossible')
    exit()

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

Solution (Python):
import sys
H, W = list(map(int, input().split()))
A = [input() for _ in range(H)]
for i in range(H - 1):
    for j in range(W - 1):
        if A[i + 1][j] == '
            print('Impossible')
            sys.exit()
print('Possible')

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

if __name__ == '__main__':
    main()

Solution (Python):






H,W = map(int, input().split())
A = []
for _ in range(H):
    A.append(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 = sum(input().count('
print('Possible' if a == h + w - 1 else 'Impossible')

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
a = [sr() for i in range(h)]
c = 0

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

def dfs():
    q = deque([[0,0]])
    dir = [[1,0],[0,1]]
    ret = 1
    while q:
        y,x = q.popleft()
        for dy,dx in dir:
            ny,nx = y+dy, x+dx
            if 0<=ny<h and 0<=nx<w and a[ny][nx] == '
                ret+=1
                if ny==h-1 and nx==w-1:
                    return ret
                q.append([ny,nx])
                break
    return ret

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

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

ans=0
cnt=0
 
for i in range(H-1):
    for j in range(W-1):
        if a[i][j] == '
            cnt+=1
        elif a[i][j] == '
            cnt+=1

            
for i in range(1,H):
    for j in range(1,W):
        if a[i][j] == '
            cnt+=1

        
print('Impossible' if cnt>0 else 'Possible')

Solution (Python):
from collections import deque
h, w = map(int, input().split())
field = []
check = [[False for _ in range(w)] for _ in range(h)]
for i in range(h):
    s = list(input().strip())
    field.append(s)

sx, sy = 0, 0
d = deque()
dirx = [0, 1, 0, -1]
diry = [1, 0, -1, 0]
d.append([sx, sy])

while (d):
    nowx, nowy = d.popleft()
    check[nowx][nowy] = True
    for x, y in zip(dirx, diry):
        nx = nowx + x
        ny = nowy + y
        if nx in range(h) and ny in range(w) and (
                not check[nx][ny]) and field[nx][ny] == '
            d.append([nx, ny])
for i in range(h):
    for j in range(w):
        if not check[i][j] and field[i][j] == '
            print('Impossible')
            exit()


d.append([sx, sy])
check = [[False for _ in range(w)] for _ in range(h)]
while (d):
    nowx, nowy = d.pop()
    check[nowx][nowy] = True

    for x, y in zip(dirx[0:2], diry[0:2]):
        nx = nowx + x
        ny = nowy + y
        if nx in range(h) and ny in range(w) and field[nx][ny] == '
            d.append([nx, ny])
    for x, y in zip(dirx[2:4], diry[2:4]):
        nx = nowx + x
        ny = nowy + y
        if nx in range(h) and ny in range(
                w) and field[nx][ny] == '
            print('Impossible')
            exit()

    if len(d) == 2:
        print('Impossible')
        exit()
    if nowx == h - 1 and nowy == w - 1:
        print('Possible')
        exit()

print('Impossible')

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

flag = True
for i in range(h-1):
    for j in range(w-1):
        if mat[i][j] == '
            if( (mat[i+1][j]=='
                flag = False

for i in range(1,h):
    for j in range(1,w):
        if mat[i][j] == '
            if( (mat[i-1][j]=='.')& (mat[i][j-1]=='.') ):
                flag = False

if flag :
    print('Possible')
else:
    print('Impossible')

Solution (Python):
h ,w = map(int, input().split())
board = [list(input()) for tate in range(h)]
now = 0
flag = False
for i in board:
    direction = i.count("
    if (flag != True):
        now = direction 
        flag = True
    else:
        if(direction == 1):
            continue
        else:
            now  = now + direction - 1

if (now == w):
    print("Possible")
else:
    print("Impossible")

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

count = 0

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

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

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

Solution (Python):
"""
i-1行目の右端のマスとi行目の左端のマスが隣接しており、
それらの行においてはそれ以外のマスは隣接していないこと。

以上を満たした場合に'Possible'を出力すればよさそう。
"""
H, W = map(int, input().split())
table = [input() for _ in range(H)]
pre_row = [i for i, x in enumerate(table[0]) if x == "
for i in range(1, H):
    next_row = [j for j, x in enumerate(table[i]) if x == "
    if len(set(pre_row) & set(next_row)) == 1 and pre_row[-1] == next_row[0]:
        pre_row = next_row
    else:
        print('Impossible')
        exit()
print('Possible')

Solution (Python):
"""
i-1行目の右端のマスとi行目の左端のマスが隣接しており、
それらの行においてはそれ以外のマスは隣接していないこと。

以上を満たした場合に'Possible'を出力すればよさそう。
"""
H, W = map(int, input().split())
table = [input() for _ in range(H)]
for i in range(1, H):
    li_pre = [i for i, x in enumerate(table[i - 1]) if x == "
    li_now = [i for i, x in enumerate(table[i]) if x == "
    if len(set(li_pre) & set(li_now)) == 1 and li_pre[-1] == li_now[0]:
        continue
    else:
        print('Impossible')
        exit()
print('Possible')

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

sharp = A.count("
if sharp == H + W - 1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque
    from itertools import combinations

    h, w = map(int, readline().split())
    a = list()
    cnt = 0
    for i in range(h):
        s = input()
        cnt += s.count("
        a.append(s)

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

    for per in combinations(range(h + w - 2), h - 1):
        cr, cc = 0, 0
        for i in range(h + w - 2):
            if i in per:
                cr += 1
            else:
                cc += 1
            if a[cr][cc] == ".":
                break
            if (cr, cc) == (h - 1, w - 1):
                return print("Possible")
    return print("Impossible")


if __name__ == '__main__':
    main()

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
a = [sr() for i in range(h)]
count = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '
            count+=1
def dfs():
    q = deque([[0,0]])
    ret = 1
    while q:
        x, y= q.popleft()
        for dx,dy in [[1,0], [0,1]]:
            nx = x+dx
            ny = y+dy
            if nx < w and ny < h and a[ny][nx] == '
                q.append([nx,ny])
                ret += 1
                if nx == w-1 and ny == h-1:
                    return ret
                break
    return ret
if dfs()==count:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
H, W = map(int, input().split())
A = []
for i in range(H):
  a = [i for i in str(input())]
  A.append(a)
  
def meiro(A, h, w):
  global H
  global W
  if ('
    return False
  while A[h][w] == '
    w += 1
    if w == W:
      break
  if h==H-1 and w==W:
    return True
  elif h == H-1:
    return False
  elif A[h][w-1:].count('
    return meiro(A, h+1, w-1)
  
if meiro(A, 0, 0):
  print('Possible')
else:
  print('Impossible')

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

Solution (Python):

import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd





def solve():
    n, w = [int(x) for x in input().split()]
    j = 0
    ok = 1
    for i in range(n):
        r = [x for x in input()]
        while r[j] == '
            r[j] = '.'
            j += 1
        if r[j] == '.' or r.count('
            ok = 0


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

    




        
    

    
    

t = 1

for case in range(1,t+1):
    ans = solve()


"""

2 2 2 2 2

"""

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

    cnt = 0
    for a in A:
        cnt += a.count("

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


if __name__ == "__main__":
    main()

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

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

Solution (Python):
import numpy as np
h, w = map(int, input().split())
A = [input() for _ in range(h)]
B = np.empty((h+1, w+1), dtype=str)
for i in range(h):
  for j in range(w):
    B[i, j] = A[i][j]

x = y = 0
B[y, x] = '.'
while x != w-1 or y != h-1:
  if B[y, x+1] == B[y+1, x] == '
    print('Impossible')
    exit()
  elif B[y, x+1] == '
    x += 1
  else:
    y += 1
  B[y, x] = '.'

if np.any(B == '
  print('Impossible')
else:
  print('Possible')

Solution (Python):
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
from decimal import *

import numpy as np

import math

import collections
import itertools
import bisect

def check(maiz):
    for i in range(h):
        for j in range(w):
            count = 0
            if i > 0 and maiz[i-1][j] =="
                count+=1
            if i <h-1 and maiz[i+1][j] =="
                count+=1
            if j > 0 and maiz[i][j-1] =="
                count+=1
            if j <w-1 and maiz[i][j+1] =="
                count+=1
            if count > 2 and  maiz[i][j] == "
                return False
    return True

if __name__ == '__main__':
    h, w = map(int, input().split())
    count =0
    flag =False
    maiz=[]
    for i in range(h):
        s = input()
        count+=s.count("
        maiz.append(list(s))

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

Solution (Python):


import itertools




def main():
    h, w = input_list()
    count = 0
    for _ in range(h):
        s = list(input())
        count += s.count('
    if h+w-1 == count:
        print('Possible')
    else:
        print('Impossible')

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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

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

res = 0

for i in range(H):
    res += input().count('

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

Solution (Python):
def dfs(A, chk):
    if a[A[-1][0]][A[-1][1]] == ".":
        return
    elif A[-1] == [h, w]:
        if len(A) == cnt and chk == 0:
            print("Possible")
        else:
            print("Impossible")
        exit()

    for v in [[1, 0], [0, 1], [0, -1], [-1, 0]]:
        tmp = [A[-1][0] + v[0], A[-1][1] + v[1]]
        if tmp not in A:
            A.append(tmp)
            if v in [[0, -1], [-1, 0]]:
                dfs(A, chk + 1)
            else:
                dfs(A, chk)                
            A.pop()

h, w = map(int, input().split())
a = [["."]*w]
a.extend([list("." + input() + ".") for x in range(h)])
a.append(["."]*w)
cnt = 0
for i in range(1,h+1):
    cnt += a[i].count("
dfs([[1, 1]], 0)

Solution (Python):


import sys
from collections import deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)



def adjacent_2(h, w, H, W):
    ret = []
    for (dh, dw) in [(0, 1), (1, 0)]:
        h_ = h + dh
        w_ = w + dw
        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


def adjacent_2_(h, w, H, W):
    ret = []
    for (dh, dw) in [(0, -1), (-1, 0)]:
        h_ = h + dh
        w_ = w + dw
        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


H, W = map(int, readline().split())
M = [list(readline().decode().rstrip()) for _ in range(H)]

que = deque([(0, 0)])
while len(que) != 0:
    acc = que.popleft()

    ret = adjacent_2(*acc, H, W)
    cnt = adjacent_2_(*acc, H, W)
    ret = [pos for pos in ret if M[pos[0]][pos[1]] == '
    cnt = [pos for pos in cnt if M[pos[0]][pos[1]] == '

    if (len(cnt) > 1):
        print("Impossible")
        sys.exit()
    if acc == (H - 1, W - 1):
        break

    if (len(ret) != 1) or (len(cnt) > 1):
        print("Impossible")
        sys.exit()
    que.append(*ret)

print("Possible")

Solution (Python):
H,W = map(int,input().split())
res = ''
for i in range(H):
    res += input()
if res.count('
    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):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

H,W = I()
boa = []
for i in range(H):
    x = X()
    count += x.count("

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