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

import numpy as np

input = sys.stdin.readline


def bfs(H, W, maze, dist, sh, sw):
    queue = deque([[sh, sw]])
    dist[sh][sw] = 0
    while queue:
        h, w = queue.popleft()
        for i, j in [(1, 0), (0, 1)]:
            next_h, next_w = h + i, w + j
            if not ((0 <= next_h <= H - 1) and (0 <= next_w <= W - 1)):
                continue
            if maze[next_h][next_w] and (dist[next_h][next_w] == -1):
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append([next_h, next_w])


def main():
    H, W = map(int, input().split())
    A = np.full((H, W), False, dtype=bool)
    for i in range(H):
        A[i] = [True if s == "

    n_path = np.sum(A) - 1
    dist = [[-1] * W for _ in range(H)]
    bfs(H, W, A, dist, 0, 0)

    if dist[H-1][W-1] == n_path:
        print("Possible")
    else:
        print("Impossible")


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    H, W = (int(_) for _ in input().split())
    board = [input() for _ in range(H)]
    num = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == '

    def dfs(x, y, n):
        if x == H-1 and y == W-1: return n == num
        nx = x + 1
        if 0 <= nx < H and board[nx][y] == '
            if dfs(nx, y, n+1):
                return True
        ny = y + 1
        if 0 <= ny < W and board[x][ny] == '
            if dfs(x, ny, n+1):
                return True
        return False

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

if __name__ == '__main__':
    main()

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

x, y = 0, 0
px, py = 0, 0
while not (x == w-1 and y == h-1):
    if not (x == 0 and y == 0):
        if px == x and py == y:
            print('Impossible')
            exit()
    px, py = x, y
    
    if not x+1 > w-1:
        if a[y][x+1] == '
            a[y][x] = '.'
            x += 1
            continue
    
    if not y+1 > h-1:
        if a[y+1][x] == '
            a[y][x] = '.'
            y += 1
            continue

ans = True

for i in range(h):
    for j in range(w):
        if a[i][j] == '
            if i == h-1 and j == w-1:
                pass
            else:
                ans = False

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

Solution (Python):
import sys
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:  
  if start[0]!=H-1 and start[1]!=W-1 and listA[start[0]+1][start[1]]=="
    print("Impossible")
    sys.exit()
  if start[0]!=0 and start[1]!=0 and listA[start[0]-1][start[1]]=="
    print("Impossible")
    sys.exit()
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()  
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="
    start=[start[0]+1,start[1]]
    continue  
  if start[1]!=W-1 and listA[start[0]][start[1]+1]=="
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")

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):
h,w,= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

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

short = h+w-1

if cnt == short:
    print('Possible')
else:
    print('Impossible')

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

Solution (Python):
from statistics import median


from fractions import gcd
from itertools import combinations 
from collections import deque
from collections import defaultdict
import bisect










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

def readInts():
  return list(map(int,input().split()))
def main():
    H,W = readInts()
    FIELD = [input() for _ in range(H)]
    ARRIVED = [[False]*W for _ in range(H)]
    def Move(y,x):
        ARRIVED[y][x] = True
        if y == H-1 and x == W-1:
            if FIELD[y][x-1] == '
                print('Impossible')
                exit()
            else:
                print('Possible')
                exit()
        y_ = True
        x_ = True
        if y+1 < H:
            y_ = True
        else:
            y_ = False
        if x+1 < W:
            x_ = True
        else:
            x_ = False
        xu = True if x - 1 >= 0 else False
        yu = True if y - 1 >= 0 else False
        if y_ and FIELD[y+1][x] == '
            if x_ and FIELD[y][x+1] == '
                print('Impossible')
                exit()
            elif yu and FIELD[y-1][x] == '
                
                print('Impossible')
                exit()
            else:
                Move(y+1,x)
        elif x_ and FIELD[y][x+1] == '
            if y_ and FIELD[y+1][x] == '
                print('Impossible')
                exit()
            elif xu and FIELD[y][x-1] == '
                
                print('Impossible')
                exit()
            else:
                Move(y,x+1)
        else:
            print('Impossible')
            exit()
    
    Move(0,0)
if __name__ == '__main__':
  main()

Solution (Python):
h,w = map(int,input().split())
ma = []
count = 0
for _ in range(h):
    tmp_li = list(input())
    for t in tmp_li:
        if t == '
            count += 1
    ma.append(tmp_li)
if count != w+h-1:
    print('Impossible')
    exit()
if ma[0][0]!= '
    print('Impossible')
    exit()

li = [[0,0]]
def che(lis):
    lll = lis.pop(0)
    x = lll[0]
    y = lll[1]
    tmp = []
    if x+1 < w:
        
        if ma[y][x+1] == '
            tmp.append([x+1,y])
        if x+1 == w -1 and y == h -1:
            print('Possible')
            exit()
    if y+1 < h:
        if ma[y+1][x] == '
            tmp.append([x,y+1])
        if x == w -1 and y+1 == h -1:
            print('Possible')
            exit()
    if len(tmp) == 0:
        print('Impossible')
        exit()
    else:
        lis += tmp
    tmp = []
    
while len(li)>0:
    che(li)

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

cnt = 0
for v in A:
	cnt += v.count('

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

Solution (Python):
from collections import deque


def bfs(start):
    Q = deque()
    Q.append(start)
    dist[start[1]][start[0]] = 0

    while Q:
        x, y = Q.popleft()

        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]

            if not(0 <= nx < W and 0 <= ny < H):
                continue
            if G[ny][nx] == '.':
                continue
            if dist[ny][nx] != -1:
                continue

            Q.append((nx, ny))
            dist[ny][nx] = dist[y][x] + 1


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

n = 0
for i in range(H):
    G[i] = list(input())
    n += G[i].count('

dist = [[-1 for _ in range(W)] for _ in range(H)]
dx = [1, 0]  
dy = [0, 1]

bfs((0, 0))

if dist[H - 1][W - 1] + 1 == n:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
import sys
from itertools import product
import copy

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


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

    grid_init = [["." for _ in range(W)] for _ in range(H)]
    grid_init[0][0] = "
    for pattern in product(["L", "D"], repeat=H + W - 2):
        grid = copy.deepcopy(grid_init)
        if pattern.count("L") == W - 1 or pattern.count("D") == H - 1:
            h, w = 0, 0
            for p in pattern:
                if p == "L":
                    w += 1
                else:
                    h += 1
                grid[h][w] = "

            flg = True
            for h in range(H):
                for w in range(W):
                    if A[h][w] != grid[h][w]:
                        flg = False
                        break

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


if __name__ == '__main__':
    resolve()

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

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

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

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

A = []
B = ["."] * (w + 2)
A.append(B)
temp = 0
for i in range(h):
    T = ['.'] + list(input()) + ['.']
    A.append(T)
    temp += T.count('
A.append(B)

t = 1
x = 1
y = 1
ans = 0
while t:
    if A[x][y] == '
        C = []
        C.append(A[x][y + 1])
        C.append(A[x+1][y])
        if C.count('
            t = 0
        else:
            A[x][y] = '?'
            if A[x][y+1] == '
                y = y + 1
            else:
                x = x + 1
            ans += 1
    else:
        t = 0

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

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

Solution (Python):
h,w = map(int,input().split())
a = [input() for i in range(h)]
ok = True
l = [False]*w
for i in range(h):
    d = False
    for j in range(w):
        if a[i][j]=='
            if i<h-1 and a[i+1][j]=='
                if d:ok=False
                d = True
            else:
                if l[j]: ok=False
                l[j] = True
print('Possible' if ok else 'Impossible')

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

a=[str(input()) for _ in range(h)]
ans=0
for i in range(h):
    ans+=a[i].count("

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

Solution (Python):
H,W = map(int,input().split())
A = [None for _ in range(H)]
for i in range(H):
  A[i] = 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')

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]


def dfs(i, j):
    global flag, grid
    grid[i][j] = '.'
    if i == H and j == W:
        fgrid = flatten_2dim(grid)
        flag = ('
    if grid[i][j+1] == '
        dfs(i, j+1)
    if grid[i+1][j] == '
        dfs(i+1, j)
    grid[i][j] = '


def main():
    global H, W, grid, flag
    H, W = map(int, readline().split())
    grid = []
    grid.append(['.']*(W+2))
    for _ in range(H):
        grid.append(['.'] + list(readline()[:-1]) + ['.'])
    grid.append(['.']*(W+2))
    flag = True
    dfs(1, 1)

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


if __name__ == "__main__":
    main()

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

for hi in range(h-1):
    for wi in range(w-1):
        if al[hi][wi]==al[hi+1][wi]==al[hi][wi+1]=="
            print("Impossible")
            exit()
        if al[hi+1][wi]==al[hi+1][wi+1]==al[hi][wi+1]=="
            print("Impossible")
            exit()
print("Possible")

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

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

Solution (Python):

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

isExact = 'Possible'

i, j = 0, 0

while i < H - 1 or j < W - 1:
    if ((i + 1 < H and A[i + 1][j] != '
            or (i + 1 == H and j + 1 < W and A[i][j + 1] != '
            or (i + 1 < H and j + 1 == W and A[i + 1][j] != '
        isExact = 'Impossible'
        break
    elif j + 1 < W and A[i][j + 1] == '
        A[i] = A[i][:j] + '.' + A[i][j + 1:]
        j += 1
    elif i + 1 < H and A[i + 1][j] == '
        A[i] = A[i][:j] + '.' + A[i][j + 1:]
        i += 1

if isExact == 'Possible':
    A[H - 1] = A[H - 1][:W - 1] + '.'

    for line in A:
        if '
            isExact = 'Impossible'
            break

print(isExact)

Solution (Python):

h,w = map(int,input().split())
g = [input() for _ in range(h)]
num = 0

for i in range(h):
    num += g[i].count("

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

Solution (Python):
import collections
H, W = map(int, input().split())
A = [input() for _ in range(H)]
A = [a+'.' for a in A]
A.append('.'*(W+1))

cnt = -1
for a in A:
    cnt += a.count('

i=j=0
flg=False
while True:
    if (A[i][j+1]=='
        j += 1
        cnt -= 1
    elif (A[i][j+1]=='.' and A[i+1][j]=='
        i += 1
        cnt -= 1
    else:
        break
    
    if i==H-1 and j==W-1 and cnt==0:
        flg=True
        break

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)

import copy

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

B = copy.deepcopy(A)
for h in range(H):
    for w in range(W):
        B[h][w] = A[h][w] == "."

def dfs(h, w, C):
    if h == H or w == W:
        return False
    if A[h][w] == ".":
        return False
    X = copy.deepcopy(C)
    X[h][w] = True
    if [h,w] == [H-1,W-1]:
        tmp = True
        for x in X:
            tmp = tmp and all(x)
        return tmp
    return dfs(h+1, w, X) or dfs(h, w+1, X)

print("Possible" if dfs(0,0,B) else "Impossible")

Solution (Python):
H, W = map(int, input().split())
A = [input() for _ in range(H)]
x = 0
for h in range(H):
    if '
        print('Impossible')
        exit()
    if A[h][x] != '
        print('Impossible')
        exit()
    while x+1 < W and A[h][x+1] == '
        x += 1

    if '
        print('Impossible')
        exit()

print('Possible')

Solution (Python):
h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'.'
    a=list(a)
    for i in a:
        if i == '
            count += 1
    ab.append(a)
ab.append(list('.'*w))

if count != h+w-1:
    print('Impossible')
    exit()
            
step = [[0, 0]]
 
while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print('Possible')
        exit()
    if ab[y+1][x] == '
        step.append([y+1, x])
    elif ab[y][x+1] == '
        step.append([y, x+1])

print('Impossible')

Solution (Python):
H, W = map(int, input().split())
c = [input() for _ in range(H)]
dist = [[-1]*W for _ in range(H)]

now = 0
for h in range(H):
    now = min(now,W-1)
    if c[h][now]!="
        print("Impossible")
        exit()
    for w in range(now,W):
        if c[h][w]==".":
            now-=1
            break
        else:
            dist[h][w]=0
            now+=1

for h in range(H):
    for w in range(W):
        if c[h][w]=="
            print("Impossible")
            exit()

if c[H-1][W-1]=="
    print("Possible")
else:
    print("Impossible")

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

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

if __name__ == '__main__':
    main()

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
h,w = map(int,input().split())
A = [list(input()) for i in range(h)]
que = collections.deque()
que.append((0,0))
while que:
  i,j = que.popleft()
  A[i][j] = "."
  if 0 <= i+1 < h:
    if A[i+1][j] == "
      que.append((i+1,j))
      continue
  if 0 <= j + 1 < w:
    if A[i][j+1] == "
      que.append((i,j+1))

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

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
a = [list(input()) for _ in range(h)]
dx,dy = [1,0],[0,1]
flag = True
for i in range(h):
    for j in range(w):
        if a[i][j] == '
            que = deque()
            que.append((i,j))
            a[i][j] = '.'
            while que:
                y,x = que.popleft()
                for k in range(2):
                    ny, nx = y + dy[k], x + dx[k]
                    if 0 <= ny < h and 0 <= nx < w:
                        if a[ny][nx] == '
                            que.append((ny,nx))
                            a[ny][nx] = '.'
                            break
            flag = False
            break
    if not flag:
        break


for i in range(h):
    for j in range(w):
        if a[i][j] == '
            print('Impossible')
            quit()
print('Possible')

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

A=np.array(A)
ok=True
for h in range(H):
    for w in range(W):
        
        lu=0
        rd=0
        if A[h,w]=="
            if 0<=h-1 and h-1<H:
                if A[h-1,w]=="
                    lu+=1
            if 0<=w-1 and w-1<W:
                if A[h,w-1]=="
                    lu+=1
            if 0<=h+1 and h+1<H:
                if A[h+1,w]=="
                    rd+=1
            if 0<=w+1 and w+1<W:
                if A[h,w+1]=="
                    rd+=1
            if h==0 and w==0:
                lu=1
            if h==H-1 and w==W-1:
                rd=1
            if lu!=1 or rd!=1:
                ok=False
if ok:
    print("Possible")
else:
    print("Impossible")

Solution (Python):



H, W = map(int, input().split())
board = [['']*W for i in range(H)]
for i in range(H):
    s = list(input())
    for j in range(W):
        board[i][j] = s[j]


max_pos = 0
is_ok = True


for i in range(H):
    tmp_min_pos = W
    tmp_max_pos = 0
    for j in range(W):
        if board[i][j]=='
            tmp_min_pos = min(tmp_min_pos, j)
            tmp_max_pos = max(tmp_max_pos, j)
    if not tmp_min_pos==max_pos:
        is_ok = False
    max_pos = tmp_max_pos

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

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

Solution (Python):
h,w = map(int,input().split())
a = [list(input()) for _ in range(h)]
count = 0
for y in range(h):
    for x in range(w):
        if a[y][x]=="
            count += 1
            
visited = [[0]*w for _ in range(h)]
q = [(0,0)]
visited[0][0] = 1
while q:
    cy,cx = q.pop()
    for dy,dx in ((1,0),(0,1)):
        ny,nx = cy+dy,cx+dx
        if (0<=ny<h and 0<=nx<w and a[ny][nx]=="
            visited[ny][nx] = visited[cy][cx]+1
            q.append((ny,nx))
            
if visited[h-1][w-1]==count:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
        H, W = map(int, input().split())
        maze = [input() for _ in range(H)]
        cnt=0
        for i in maze:
            for j in i:
                if j=='
                    cnt+=1
        print('Possible' if cnt==(H-1)+(W-1)+1 else 'Impossible')

resolve()

Solution (Python):
def lake(x,y):
    l[x][y] = "."
    for i in range(2):
        xi = x + dx[i]
        yi = y + dy[i]
        if 0 <= xi < n and 0 <= yi < m and l[xi][yi] == "
            lake(xi,yi)
            break


n,m = map(int, input().split())
l = [list(input()) for _ in range(n)]
l[0][0]=="."
dx = [1,0]
dy = [0,1]
lake(0,0)
for i in range(n):
    for j in range(m):
        if l[i][j] == "
            print("Impossible")
            exit()

print("Possible")

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

i = j = 0

visited = [[None] * W for _ in range(H)]

def dp(i, j):
    global H, W
    visited[i][j] = True
    if i == H - 1 and j == W - 1: return True
    
    if i + 1 >= H:
        d = False
    else:
        d = (A[i + 1][j] == '
    
    if j + 1 >= W:
        r = False
    else:
        r = (A[i][j + 1] == '
    
    if d and not r:
        return dp(i + 1, j)
    elif not d and r:
        return dp(i, j + 1)
    else:
        return False

if dp(0, 0):
    ans = 'Possible'
    for i in range(H):
        for j in range(W):
            if not visited[i][j] and A[i][j] == '
                ans = 'Impossible'
    
    print(ans)
else:
    print('Impossible')

Solution (Python):
from collections import deque


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

q = deque([(0, 0)])
while q:
    i, j = q.pop()
    cnt = 0
    if i == h - 1 and j == w - 1:
        break
    for nxt_i, nxt_j in [(i + 1, j), (i, j + 1)]:
        if not(0 <= nxt_i < h and 0 <= nxt_j < w):
            continue
        if a[nxt_i][nxt_j] == "
            cnt += 1
            q.append((nxt_i, nxt_j))
    if cnt != 1:
        print("Impossible")
        exit()

cnt = 0
for i in range(h):
    cnt += a[i].count("
if cnt != h + w - 1:
    print("Impossible")
else:
    print("Possible")

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

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

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

from collections import deque
dxy = [(0,1),(1,0)]
dist = [[0]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
visited[0][0] = 1
q = deque([(0,0)])
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if visited[ny][nx]: continue
        if A[ny][nx] == '.': continue
        visited[ny][nx] = 1
        dist[ny][nx] = dist[y][x] + 1
        q.append((nx,ny))

cnt = sum(row.count('
print('Possible' if dist[-1][-1]+1 == cnt else 'Impossible')

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

p = -1
q = -1
for i in range(h):
    for j in range(w):
        if A[i][j] == '
            if q > j:
                print('Impossible')
                exit()
            else:
                p = j
    q = p
else:
    print('Possible')

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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 LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

d = [(1,0),(0,1)]
def solve():
    h,w = LI()
    a = [input() for i in range(h)]
    q = deque([(0,0)])
    bfs = [[0]*w for i in range(h)]
    bfs[0][0] = 1
    while q:
        y,x = q.popleft()
        if q:
            print("Impossible")
            return
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if a[ny][nx] != ".":
                    if not bfs[ny][nx]:
                        bfs[ny][nx] = 1
                        q.append((ny,nx))
    for y in range(h):
        for x in range(w):
            if a[y][x] != "." and not bfs[y][x]:
                print("Impossible")
                return
    print("Possible")
    return


if __name__ == "__main__":
    solve()

Solution (Python):
*t,=open(0)
print(["Imp", "P"][int(t[0][0])+int(t[0][2])-1==sum(s.count("

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

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

ans = True
h = 0
w = 0
B = [[1 if a == '
while (ans) and not (h == H - 1 and w == W - 1):
    B[h][w] = 0
    if h == H - 1:
        if A[h][w + 1] == '.':
            ans = False
        else:
            w += 1
    elif w == W - 1:
        if A[h + 1][w] == '.':
            ans = False
        else:
            h += 1
    else:
        sh = A[h + 1][w]
        sw = A[h][w + 1]
        if sh == '
            ans = False
        elif sh == '.' and sw == '.':
            ans = False
        elif sh == '
            h += 1
        else:
            w += 1

s = sum([sum(b_list) for b_list in B])
if ans and s == 1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
import sys
from sys import stdin

h, w = map(int, stdin.readline().rstrip().split())
a = [stdin.readline().rstrip() for i in range(h)]
count = 0
for i in a:
    for j in i:
        if j == '
            count += 1
if h + w - 1 == count:
    print('Possible')
else:
    print('Impossible')

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

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

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

Solution (Python):


int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def solve():
    h, w = MI()
    cnt = 0
    for i in range(h):
        l = list(input())
        for j in range(w):
            if l[j] == '
                cnt = cnt + 1
    if h + w - 1 == cnt:
        print('Possible')
    else:
        print('Impossible')

if __name__ == '__main__':
    solve()

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

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


print ("Impossible") if c > H+W-1 else print ("Possible")

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

cnt = 0
for a in A:
	cnt += a.count("
if cnt == H+W-1:
	print("Possible")
else:
	print("Impossible")

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

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

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

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

cnt = 0
for y in range(H):
    for x in range(W):
        if A[y][x] == '
            cnt += 1

x, y = 0, 0
seen = 0
while 0 <= x < W and 0 <= y < H:
    
    if 0 <= y < H - 1 and A[y + 1][x] == '
        y = y + 1
        seen += 1
    elif 0 <= x < W - 1 and A[y][x + 1] == '
        x = x + 1
        seen += 1
    elif x == W - 1 and y == H - 1:
        
        if seen == cnt - 1:
            print('Possible')
            break
        else:
            print('Impossible')
            break
    else:
        print('Impossible')
        break

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

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

ans = "Possible"
for i in range(h-1):
    for y in range(w-1):
        if a[i][y+1] == a[i+1][y] == "
            ans = "Impossible"
            break
print(ans)