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 defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    H, W = LI()
    a = SR(H)
    for h in range(H):
        for w in range(W):
            if a[h][w] == "
                t = True
                for mh, mw in [[0, 1], [1, 0]]:
                    mh += h
                    mw += w
                    if 0 <= mh < H and 0 <= mw < W:
                        if a[mh][mw] == "
                            if t:
                                t &= False
                            else:
                                print("Impossible")
                                return
                if t and (h != H - 1 and w != W - 1):
                    print("Impossible")
                    return
                t = True
                for mh, mw in [[0, -1], [-1, 0]]:
                    mh += h
                    mw += w
                    if 0 <= mh < H and 0 <= mw < W:
                        if a[mh][mw] == "
                            if t:
                                t &= False
                            else:
                                print("Impossible")
                                return
                if t and (h != 0 and w != 0):
                    print("Impossible")
                    return
    print("Possible")
    return



if __name__ == '__main__':
    solve()

Solution (Python):
def main():
    H,W = map(int,input().split())
    root = [list(str(input())) for _ in range(H)]
    _long = [[0 for _ in range(W)] for _ in range(H)]
    _long[0][0] = 1
    al = 0
    for i in range(H):
        for j in range(W):
            if root[i][j] == "
                al += 1
    
    if al != H+W-1:
        print("Impossible")
        exit()
    
    print("Possible")
    
if __name__ == "__main__":
    main()

Solution (Python):



h, w = map(int, input().split())
table = []
sharp = 0
for _ in range(h):
    get = input()
    table.append(get)
    sharp += get.count("

flag = False
pos = [0, 0]
path = 0
while True:
    if pos == [h - 1, w - 1]:
        path += 1
        flag = True
        break
    if h <= pos[0] or w <= pos[1]:
        break
    if (
        pos[0] < h - 1
        and pos[1] < w - 1
        and table[pos[0] + 1][pos[1]] == "
        and table[pos[0]][pos[1] + 1] == "
    ):
        break
    if pos[0] < h - 1 and pos[1] < w - 1 and table[pos[0] + 1][pos[1]] == "
        pos[0] += 1
        path += 1
        continue
    elif pos[0] < h - 1 and pos[1] < w - 1 and table[pos[0]][pos[1] + 1] == "
        pos[1] += 1
        path += 1
        continue
    if pos[0] == h - 1 and pos[1] < w - 1 and table[pos[0]][pos[1] + 1] == "
        pos[1] += 1
        path += 1
        continue
    elif pos[0] < h - 1 and pos[1] == w - 1 and table[pos[0] + 1][pos[1]] == "
        pos[0] += 1
        path += 1
        continue
    else:
        break

print("Possible" if flag and path == sharp else "Impossible")

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

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


def dfs(x, y):
    if a[x][y] == '
        a[x][y] = '.'
    if x + 1 < h and a[x + 1][y] == '
        dfs(x + 1, y)
    elif y + 1 < w and a[x][y + 1] == '
        dfs(x, y + 1)


dfs(0, 0)
for i in range(h):
    for j in range(w):
        if a[i][j] == '
            print('Impossible')
            exit()
print('Possible')

Solution (Python):
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
d=[[1,0],[0,1]]
def dfs(x,y):
    a[x][y]="."
    for i in d:
        if 0<=x+i[0]<h and 0<=y+i[1]<w and a[x+i[0]][y+i[1]]=="
            dfs(x+i[0],y+i[1])
            break
dfs(0,0)


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

Solution (Python):
import sys
def routeSearch(x,y):
	a[y][x]='@'
	if(x<w-1 and a[y][x+1]=='
		routeSearch(x+1,y)
	elif(y<h-1 and a[y+1][x]=='
		routeSearch(x,y+1)
h,w=map(int,input().split())

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

routeSearch(0,0)
for i in range(h):
	if('
		print("Impossible")
		sys.exit()

print("Possible")

Solution (Python):

import numpy as np
H, W = map(int, input().split())
board = []
tb = [[False] * W] * H
tb = np.array(tb)
cnt = 0
for i in range(H):
    tmp = list(input())
    for j in range(W):
        if tmp[j] == "
            cnt += 1
            if "s" not in globals():
                s = [i, j]
    board.append(tmp[:])
board = np.array(board)
tb[s[0], s[1]] = True
for i in range(H):
    for j in range(s[1], W):
        if board[i][j] == "
            s[1] = j
            tb[s[0], s[1]] = True
    if s[0] < H - 1:
        s[0] += 1
    if board[s[0], s[1]] == "
        tb[s[0], s[1]] = True
    else:
        break
print("Possible" if cnt == np.sum(tb) else "Impossible")

Solution (Python):
def examA():
    H, W = LI()
    A = [SI() for _ in range(H)]
    cur = 0
    for i in range(H):
        for j in range(W):
            if A[i][j]=="
                cur +=1
    if cur==H+W-1:
        ans = "Possible"
    else:
        ans = "Impossible"
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examA()

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

H, W = map(int, readline().split())
G = sum(sum(1 if s == '
if G == H+W-1:
    print('Possible')
else:
    print('Impossible')

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

Solution (Python):


n,m=map(int,input().split())
s = [list(input()) for i in range(n)]
cnt=0
for i in range(n):
    for j in range(m):
        if s[i][j]=='
            cnt+=1
if cnt>n+m-1:
    print('Impossible')
else:
    print('Possible')

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

A = '.' * (W+2)
for _ in range(H):
    A += '.' + readline().rstrip().decode('utf-8') + '.'
A += '.' * (W+2)

start = 1 * (W+2) + 1
goal = H * (W+2) + W

v = start
fail = False
for _ in range(H+W-2):
    if A[v+1] == '
        v += 1
        continue
    elif A[v+W+2] == '
        v += (W+2)
        continue
    fail = True
    break

cnt = A.count('
bl = (cnt == H + W - 1) and (not fail)
answer = 'Possible' if bl else 'Impossible'
print(answer)

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

Solution (Python):


n,m=map(int,input().split())
s = [list(input()) for i in range(n)]
cnt=0
for i in range(n):
    for j in range(m):
        if s[i][j]=='
            cnt+=1
if cnt>n+m-1:
    print('Impossible')
else:
    print('Possible')

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

Solution (Python):
import copy
from collections import deque
H,W = map(int,input().split())
A = []
for i in range(H):
    A.append(list(input()))
now = [0,0]
goal = [H-1,W-1]
x1 = [0,1]
y1 = [1,0]
alr = copy.deepcopy(A)
alr[0][0] = 1
que = deque()
que.append(now)
while que:
    q = que.popleft()
    for i in range(2):
        if 0 <= q[0]+x1[i] <= H-1 and 0 <= q[1]+y1[i] <= W-1 and alr[q[0]+x1[i]][q[1]+y1[i]] == '
            alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] +1
            que.append([q[0]+x1[i],q[1]+y1[i]])
if alr[-1][-1] != '
    num = alr[-1][-1]
    count = {}
    flag = True
    for i in range(1,num+1):
        count[i] = 0
    for i in range(H):
        for j in range(1,num+1):
            count[j] += alr[i].count(j)
        if '
            flag = False
    
    for i,v in count.items():
        if v != 1:
            flag = False
    if flag:
        print('Possible')
    else:
        print('Impossible')
else:
    print('Impossible')

Solution (Python):
h,w=map(int,input().split())
bd = [list("."+input()+".") for i in range(h)]
bd.insert(0,["."]*(w+2))
bd.append(["."]*(w+2))
stack=[(1,1)]
while(stack):
  i,j=stack.pop()
  if i == h and j == w:
    bd[i][j]="."
    break
  if bd[i+1][j] == bd[i][j+1]:
    print("Impossible")
    exit()
  if bd[i-1][j] == "
    print("Impossible")
    exit()
  if bd[i+1][j] == "
    stack.append((i+1,j))
  if bd[i][j+1] == "
    stack.append((i,j+1))
  bd[i][j] = "."
if bd == [["." for i in range(w+2)] for j in range(h+2)]:
  print("Possible")
else:
  print("Impossible")

Solution (Python):
from sys import exit, stdin
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
S = [list(stdin.readline().rstrip()) for _ in range(H)]
cnt = 0
for l in S:
    cnt += l.count('
if cnt == H + W - 1:
    print('Possible')
else:
    print('Impossible')

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

h,w=map(int,input().split())
l=[]
c=0
for i in range(h):
 t_l=list(input())
 c+=t_l.count('
 l.append(t_l)

sy,sx=0,0
gy,gx=h-1,w-1

dist=[[-1]*w for i in range(h)]
dist[0][0]=0

que=deque()
que.append((sy,sx))

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

 if y==gy and x==gx and dist[gy][gx]==c-1:
  print('Possible')
  exit()

 for dy,dx in [[1,0],[0,1]]:
  ny=y+dy
  nx=x+dx
  if ny<=h-1 and nx<=w-1 and l[ny][nx]=='
   que.append((ny,nx))
   l[ny][nx]=='.'
   dist[ny][nx]=dist[y][x]+1

print('Impossible')

Solution (Python):
import sys
import os
if sys.platform=="darwin":
   base = os.path.dirname(os.path.abspath(__file__))
   name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
   
   sys.stdin = open(name)

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


ans = 0
for i in range(h):
   ans = ans + l[i].count(".")



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

Solution (Python):
h,w=map(int,input().split())
A=[list(input()) for i 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):
def flatten_2d(data):
    for block in data:
        for elem in block:
            yield elem
            
h,w = map(int,input().split())

List=[input() for i in range(h)]



a = list(flatten_2d(List))




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

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

ans = "Possible"
now = 0
for i in range(H):
    nxt = now
    for j in range(W):
        if j < now and A[i][j] == '
            ans = "Impossible"
        elif j == now:
            if A[i][j] == '.':
                ans = "Impossible"
        else:
            if j == nxt+1 and A[i][j] == '
                nxt = j
            elif A[i][j] == '
                ans = "Impossible"
    now = nxt

print(ans)

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



x = 0
y = 0
a[x][y] = '.'

while  x < h and y < w:
    
    if x < h-1:
        if a[x+1][y] == '
            x += 1
            a[x][y] = '.'
            continue
    if y < w-1:
        if a[x][y+1] == '
            y += 1
            a[x][y] = '.'
            continue
    if x == h - 1 and y == w - 1:
        break
    else:
        print('Impossible')
        exit()



for b in a:
    if '
        print('Impossible')
        exit()


print('Possible')

Solution (Python):
H,W = map(int,input().split())
A =[[0]*(W+2)] + [[0] + [0 if s=='.' else 1 for s in input()] + [0]  for _ in range(H)] + [[0]*(W+2)]
pos = [1,1]
A[1][1] = 0
while pos != [W,H]:
  if pos[1]<=H and A[pos[1]+1][pos[0]] == 1:
    A[pos[1]+1][pos[0]] = 0
    pos = [pos[0],pos[1]+1]
  elif pos[0]<=W and A[pos[1]][pos[0]+1] == 1:
    A[pos[1]][pos[0]+1] = 0
    pos = [pos[0]+1,pos[1]]
  else:
    print('Impossible')
    exit()
if sum([sum(row) for row in A]) == 0: print('Possible')
else:print('Impossible')

Solution (Python):
from collections import deque
import numpy as np


def isPossible(grid):
    v = deque([[0, 0]])

    while v:
        x, y = v.popleft()
        grid[x][y] = 0
        if grid[x][y + 1]:
            v.append([x, y + 1])
            continue
        elif grid[x + 1][y]:
            v.append([x + 1, y])
            continue

    if grid.sum() == 0:
        return True
    else:
        return False


if __name__ == "__main__":
    h, w = map(int, input().split())
    grid = [[0 if i == "." else 1 for i in input()+"."] for _ in range(h)]
    grid.append([0]*(w+1))
    grid = np.array(grid)
    if isPossible(grid):
        ans = "Possible"
    else:
        ans = "Impossible"
    print(ans)

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

cnt = 0
for y in range(H) :
  cnt += A[y].count('

y, x = 0, 0
cnt -= 1
while not (y == H - 1 and x == W - 1) :
  if x + 1 < W and A[y][x + 1] == '
    cnt -= 1
    x += 1
    continue
  
  if y + 1 < H and A[y + 1][x] == '
    cnt -= 1
    y += 1
    continue

  break

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

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

Solution (Python):
a,b = map(int,input().split())
cnt = 0
for i in range(a):
    s = input()
    cnt += s.count("

if cnt == a+b-1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
a,b = map(int,input().split())
cnt = 0
for i in range(a):
    s = input()
    cnt += s.count("

if cnt == a+b-1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
from collections import deque

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

def next_point_is_ok1(i,j):
    global a,h
    if i < h-1:
        return a[i+1][j]=="
    else:
        return False

def next_point_is_ok2(i,j):
    global a,w
    if j < w-1:
        return a[i][j+1]=="
    else:
        return False


def next_points():
    global x,a
    
    if x==[h-1,w-1]:
        
        if a == [["." for i in range(w)] for j in range(h)]:
            print("Possible")
        else:
            print("Impossible")
    elif next_point_is_ok1(x[0],x[1]):
        
        x[0]+=1
        a[x[0]][x[1]]="."
        next_points()
    elif next_point_is_ok2(x[0],x[1]):
        
        x[1]+=1
        a[x[0]][x[1]]="."
        next_points()
    else:
        
        print("Impossible")


if a[0][0]==".":
    print("Impossible")
else:
    a[0][0]="."
    next_points()

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

sharp = 0
for line in graph:
    sharp += line.count("
if sharp == H + W - 1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
from sys import stdin

h,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [stdin.readline().rstrip() for _ in range(h)]

now = 0

for i in range(h):
    if "
        print("Impossible")
        exit()
    for j in range(now,w-1):
        if li[i][j] == "
            now = j
        if li[i][w-2] == "
            now = w-1
    if now <= 3:
        if "
            print("Impossible")
            exit()
print("Possible")

Solution (Python):
from sys import stdin

h,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [stdin.readline().rstrip() for _ in range(h)]

now = 0

for i in range(h):
    if "
        print("Impossible")
        exit()
    for j in range(now,w-1):
        if li[i][j] == "
            now = j
        if li[i][w-2] == "
            now = w-1 
    if "
        print("Impossible")
        exit()
print("Possible")

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

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

def dfs(i=0, j=0):
    if not (0 <= i < h and 0 <= j < w):
        return
    elif a[i][j] == ".":
        return
    elif b[i][j]:
        return
    else:
        b[i][j] = 1
        dfs(i+1, j)
        dfs(i, j+1)
        for i in range(h):
            for j in range(w):
                if a[i][j] == "
                    print("Impossible")
                    exit()
        print("Possible")
        exit()

dfs()

Solution (Python):
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:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
from collections import Counter

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

ans = 0
for i in range(H):
    a = input()
    z = Counter(a)
    ans += z["

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

Solution (Python):


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

l=[]
for _ in range(H):
    l.append(list(input()))

def dfs(h,w):
    l[h][w]="!"
    
    
    if h==H-1 and w==W-1:
        for item in l:
            if "
                print("Impossible")
                exit()
        print("Possible")
        exit()
    elif (l[h-1][w]=="
        print("Impossible")
        exit()
    if h<H-1:
        if l[h+1][w]=="
            dfs(h+1,w)
    if w<W-1:
        if l[h][w+1]=="
            dfs(h,w+1)
    l[h][w]="
    
    return "Impossible"

print(dfs(0,0))

Solution (Python):
H,W=map(int,input().split())
gy,gx=H-1,W-1
grid=["" for i in range(H)]
touched=0
for i in range(H):
  grid[i]=input()
  touched+=grid[i].count("

print(("Imp","P")[touched==H+W-1]+"ossible")

Solution (Python):
H,W=map(int,input().split())
gy,gx=H-1,W-1
grid=["" for i in range(H)]
touched=0
for i in range(H):
  grid[i]=input()
  touched+=grid[i].count("

if touched!=(H+W-1):
  print("Impossible")
  exit(0)

stack=[]
stack.append([0,0])
goal=False
while stack:
  v=stack.pop()
  y=v[0]
  x=v[1]
  if y==gy and x==gx:
    goal=True
    break
  if grid[y][x]==".":
    continue
  if y+1<H:
    stack.append([y+1,x])
  if x+1<W:
    stack.append([y,x+1])
    
print(("Impossible","Possible")[goal])

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

visited = [[False for j in range(W)] for i in range(H)]
visited[0][0] = True

x,y = 0,0

while not (x==H-1 and y==W-1):
    if x<H-1 and A[x+1][y]=='
        x += 1
        visited[x][y] = True
    elif y<W-1 and A[x][y+1]=='
        y += 1
        visited[x][y] = True
    else:
        break
ans = True
for i in range(H):
    for j in range(W):
        if A[i][j] == '
            ans = False

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

Solution (Python):
import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  

H, W = rl()
A = [list(rs()) for _ in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '
            A[i][j] = 1
        else:
            A[i][j] = 0
    A[i].append(0)            
A.append([0] * (W + 1))
bool = True

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            if A[i+1][j] + A[i][j+1] != 1:
                bool = False
            continue
        if i == H - 1 and j == W - 1:
            if A[i-1][j] + A[i][j-1] != 1:
                bool = False
            continue
        if A[i][j] == 1:
            if A[i+1][j] + A[i][j+1] != 1:
                bool = False
            if A[i-1][j] + A[i][j-1] != 1:
                bool = False

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

Solution (Python):

import sys
import numpy as np 

def main():
    H, W = map(int, sys.stdin.readline().split())
    visited = np.array([sys.stdin.readline().rstrip() for _ in range(H)], dtype='U')

    if np.char.count(visited, '
        ans = 'Possible'
    else:
        ans = 'Impossible'

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import numpy as np 

def main():
    H, W = map(int, sys.stdin.readline().split())
    visited = np.array([sys.stdin.readline().rstrip() + '.' for _ in range(H)], dtype='U')
    visited = np.append(visited, '.' * (W + 1))

    if np.char.count(visited, '
        print('Impossible')
        sys.exit()
    
    h, w = 0, 0
    for _ in range(H + W - 2):
        if visited[h+1][w] == '
            h += 1
        elif visited[h+1][w] == '.' and visited[h][w+1] == '
            w += 1
        else:
            print('Impossible')

    print('Possible')


if __name__ == '__main__':
    main()

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

x = 0
y = 0
ans = 'Possible'
a[0][0] = '.'
while True:
    if y < W - 1 and a[x][y + 1] == '
        y += 1
        a[x][y] = '.'
        continue
    elif x < H - 1 and a[x + 1][y] == '
        x += 1
        a[x][y] = '.'
        continue
    break

for i in range(H):
    if a[i].count('
        ans = 'Impossible'
        break
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

h,w = inpl()
s = [list(input()) for i in range(h)]
if s[0][0] != '
    print('Impossible')
    quit()
s[0][0] = '.'
for i in itertools.combinations(range(h+w-2),h-1):
    
    cnt = [1] * (h+w-2)
    for l in range(h+w-2):
        if l in i:
            cnt[l] = 0 
    
    t = [['' for k in range(w)] for j in range(h)] 
    for k in range(h):
        for j in range(w):
            tmp = s[k][j]
            t[k][j] = tmp
    nx = ny = 0
    
    
    
    
    
    for j in cnt:
        if j:
            nx += 1
        else:
            ny += 1
        if t[ny][nx] == '
            t[ny][nx] = '.'
    for j in t:
        if '
            break
    else:
        print('Possible')
        
        
        break
else:
    print('Impossible')

Solution (Python):
import sys


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

    hash = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == "
                hash.append((h, w))

    if hash == []:
        print('Impossible')
        sys.exit()

    s = hash[0]

    nd = ((1, 0), (0, 1))

    q = [s]
    cnt = 1
    while q:
        x0, y0 = q[0]
        del q[0]
        for dx, dy in nd:
            x = x0 + dx
            y = y0 + dy
            if x < H and y < W:
                if A[x][y] == "
                    cnt += 1
                    q.append((x, y))
                    break

    if cnt == len(hash):
        print('Possible')
    else:
        print('Impossible')

main()

Solution (Python):

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

the_number_of_stones = 0

for i in range(h):
    the_number_of_stones += a[i].count('

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

Solution (Python):
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
max_x = 0
max_y = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '
            if max_x > j or max_y > i:
                print('Impossible')
                exit()
            else:
                max_x = j
                max_y = i
print('Possible')

Solution (Python):
N, M = input().split()
c=0
for i in range(int(N)):
	a=list(input())
	for j in a:
		if j=="
			c+=1

if c==int(N)+int(M)-1:
	print("Possible")
else:
	print("Impossible")

Solution (Python):
H,W = map(int,input().split())
A = []
c = 0
O = "ossible"
P = "P" + O
I = "Imp" + O

for i in range(H):
    a = input()
    A.append(a)
    c += a.count("

if H+W-1==c:
    print(P)
else:
    print(I)

Solution (Python):
h, w = map(int, input().split())
table = []
for i in range(h):
    table.append(list(input()))
poss = True
for i in range(h-1):
    for j in range(w-1):
        if table[i][j] == "
            if (table[i+1][j]=="
                poss = False
for i in range(1, h):
    if table[i][w-2]=="
        poss = False
for i in range(1, w):
    if table[h-1][i-1]=="
        poss = False

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

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


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

x, y = 0, 0

while y != H - 1 or x != W - 1:
    A[y][x] = '.'
    dy, dx = min(y + 1, H - 1), x
    ry, rx = y, min(x + 1, W - 1)
    if A[dy][dx] == '
        y, x = dy, dx
    elif A[ry][rx] == '
        y, x = ry, rx
    else:
        
        print('Impossible')
        break
else:
    A[H - 1][W - 1] = '.'
    if any('
        print('Impossible')
    else:
        print('Possible')

Solution (Python):
h,w=map(int,input().split())
a=[list(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:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
H,W=H-1,W-1
if not (A[0][0]==A[-1][-1]=="
    print("Impossible")
    exit()

h=0
w=0
while H>h or W>w:
    if H>h and W>w:
        if A[h+1][w]=="
            print("Impossible")
            exit()
        elif A[h+1][w]=="
            h+=1
        elif A[h][w+1]=="
            w+=1
        else:
            print("Impossible")
            exit()
    elif H>h and A[h+1][w]=="
        h+=1
    elif W>w and A[h][w+1]=="
        w+=1
    else:
        print("Impossible")
        exit()

print("Possible")

Solution (Python):
H,W=map(int,input().split())
prev=0
for i in range(H):
  s=input()
  id = s.index("
  if id >= prev:
    flag=False
    prev = W-1 - s[::-1].index("
    for j in range(id,W):
      if flag and s[j]=="
        print("Impossible")
        exit(0)
      if s[j]==".":
        flag=True
  else:
    print("Impossible")
    exit(0)
print("Possible")

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

A = [[0]*(W) for j in range(H+1)]

for i in range (H):
    A[i]=list(input()+".")

i=0
j=0
A[0][0]=0
while(True):
    if((i==(H-1))and(j==(W-1))):
        for k in range(H):
            if("
                print("Impossible")
                exit()
        print("Possible")
        exit()
    if(A[i+1][j]=="
        A[i+1][j]=0
        i+=1
    elif(A[i][j+1]=="
        A[i][j+1]=0
        j+=1
    else:
        print("Impossible")
        exit()

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

Solution (Python):
H,W=map(int,input().split())
C=[input() for i in range(H)]
F=[[0 for i in range(W)] for j in range(H)]
cc=0
for i in range(H):
    cc+=list(C[i]).count('
C[0]='s'+C[0][1:]
C[-1]=C[-1][:-1]+'g'
for i in range(H):
	if('s' in C[i]):
		home_y=i
		home_x=C[i].index('s')
	if('g' in C[i]):
		store_y=i
		store_x=C[i].index('g')

stack=[[home_x,home_y]]

def check(x,y):
	if(x<0 or x>=W or y<0 or y>=H):
		return 0
	if(C[y][x]=='.'):
		return 0
	if(F[y][x]==1):
		return 0
	return 1

while(len(stack)!=0):
    x,y=stack.pop()
    F[y][x]=1
    if(check(x+1,y)):
        stack.append([x+1,y])
    
        
    if(check(x,y+1)):
        stack.append([x,y+1])
    
        
    

if(F[store_y][store_x]==1) and cc==H+W-1:
	print('Possible')
else:
	print('Impossible')

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