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
sys.setrecursionlimit(10**7)
import math
from collections import defaultdict


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))



H,W = II()
A = [list(map(str, input())) for _ in range(H)]
for i in range(H):
  A[i].append('?')
A.append(['?']*(W+1))

i=0;j=0
A[i][j]='.'
while 1:
  if i==H-1 and j==W-1:
    break
  if A[i+1][j]=='
    A[i+1][j]='.'
    i +=1
    continue
  if A[i][j+1]=='
    A[i][j+1]='.'
    j +=1
    continue
  print('Impossible')
  exit()

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

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

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

def dfs(h,w):
    if(A[h][w]=='.'):
        return False
    else:
        A[h][w]='.'
        x = False
        if(w<W-1):
            x = dfs(h,w+1)
        if(not x and h<H-1):
            dfs(h+1,w)
        return True

dfs(0,0)
for a in A:
    if('
        print('Impossible')
        break
else:
    print('Possible')

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

Solution (Python):
h, w = [ int(v) for v in input().split() ]

v = 0
for i in range(h):
  v += input().count("
  
if v == h + w - 1:
  print("Possible")
else:
  print("Impossible")

Solution (Python):
a, b = map(int, input().split())
c = []
for i in range(a):
    c.append(list(input()))
x = y = 0
while True:
    c[x][y] = "."
    if x == a - 1 and y == b - 1:
        break
    d = False
    if x + 1 < a and not d:
        if c[x+1][y] == "
            d = not d
            x += 1
    if y + 1 < b and not d:
        if c[x][y + 1] == "
            d = not d
            y += 1
    if not d:
        print("Impossible")
        exit()
p = True
for i in range(a):
    if "
        print("Impossible")
        exit()
print("Possible")

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

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    h, w = tuple(map(int, input().rstrip().split()))
    B = tuple(input().rstrip() for _ in range(h))
    cnt = ("".join(B)).count("
    print("Possible" if cnt == h + w - 1 else "Impossible")


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if maze[y+1][x]=="
            return("Impossible")
        for j, k in ([-1, 0], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "
                return("Impossible")
        for j, k in ([1, 0], [0, 1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
        if x==gx and y==gy:
            return("Possible")
h,w=map(int,input().split())
sy,sx=1,1
gy,gx=h,w
maze =["$"*(w+2)]+["$"+input()+"$" for i in range(h)]+["$"*(w+2)]
visited = [[-1]*(w+2) for j in range(h+2)]
print(bfs(maze, visited, sy, sx, gy, gx))

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

t = 0
for i in range(N):
    for j in range(M):
        if a[i][j] == "
            if t <= j:
                t = j
            else:
                print("Impossible")
                exit()
print("Possible")

Solution (Python):
a, b = map(int, input().split())
c = [list(input())for _ in range(a)]
x = y = 0
c[x][y] = "."
while True:
    moved = False
    if x < a-1:
        if c[x+1][y] =="
            c[x+1][y] = "."
            x += 1
            if not moved:
                moved = not moved
    if y < b-1:
        if c[x][y+1] == "
            c[x][y + 1] = "."
            y += 1
            if not moved:
                moved = not moved
    if x == a-1 and y == b-1:
        for i in range(a):
            for j in range(b):
                if c[i][j] == "
                    print("Impossible")
                    exit()
        print("Possible")
        exit()
    if not moved:
        print("Impossible")
        exit()

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

Solution (Python):
import sys
h,w=map(int,input().split())
f=[[] for i in range(h)]
for i in range(h):
  inv=input()
  for j in range(w):
    if inv[j]=="
      f[i].append(j)
c=0
for i in f:
  if c!=i[0]:
    print("Impossible");sys.exit()
  if i[-1]-i[0]>=len(i):print("Impossible");sys.exit()
  c=i[-1]
print("Possible")

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

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

c = 0
for _ in range(H):
    for a in input():
        if a == '
            c += 1

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

Solution (Python):
h,w=map(int,input().split())
a=[list(input()+'.') for _ in range(h)]
d=['.']*(w+1)
a.append(d)
x=1
i=0;j=0
a[0][0]='.'
while i!=h-1 or j!=w-1:
  if a[i+1][j]=='
    if a[i][j+1]=='
      x=0
      break
    else:
      i=i+1
      a[i][j]='.'
  else:
    if a[i][j+1]=='.':
      x=0
      break
    else:
      j=j+1
      a[i][j]='.'
if x==1:
  for k in range(h):
    if '
      x=0
      break
print('Possible' if x==1 else 'Impossible')

Solution (Python):
H, W = map(int,input().split())
pos = 0
for _ in range(H):
    line = input()
    for i, l in enumerate(line):
        if l == "
            if i < pos:
                print("Impossible")
                exit()
            if pos < i:
                pos = i
print("Possible")

Solution (Python):
h, w = map(int, input().split())
a = [input() for i 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())
cnt = 0
for _ in range(H):
    cnt += input().count('

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

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

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

Solution (Python):
h, w = [int(i) for i in input().split()]
cnt = 0
for i in range(h):
    cnt += input().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)]
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):
def solve(h, w, a):
    a = list(map(list, a))
    total = 0
    for r in range(h):
        for c in range(w):
            if a[r][c] == "
                total += 1
    que = [(0,0)]
    a[0][0] = "."
    while que:
        cr, cc = que.pop(0)
        for dr, dc in [(1,0),(0,1)]:
            nr, nc = cr+dr, cc+dc
            if (0 <= nc < w) and (0 <= nr < h) and a[nr][nc] == "
                a[nr][nc] = "."
                que.append((nr, nc))
    return "Possible" if (a[h-1][w-1] == ".") and (total == h+w-1) else "Impossible"

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

Solution (Python):
H, W = map(int, input().split())
table = [input() for _ in range(H)]
path_length = sum([t.count('
if path_length == H + W - 1:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
H, W = map(int, input().split())
c = 0
A = ['.' * (W + 2)]
for _ in range(H):
    a = input()
    c += a.count('
    A.append('.' + a + '.')
A.append('.' * (W + 2))

right = [0, 1]
under = [-1, 0]
goal = [H, W]
now = [1, 1]
ans = 1
while now != goal:
    if A[now[0] + 1][now[1]] == '
        break
    if A[now[0] + 1][now[1]] == '
        ans += 1
        now[0] += 1
    else:
        if A[now[0]][now[1] + 1] == '
            ans += 1
            now[1] += 1
        else:
            break

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

Solution (Python):
h,w=map(int,input().split())
for x in range(h):
    a=input()
    for i in range(w):
        if a[i]=="
            l=i
            break
    for j in range(w):
        if a[w-1-j]=="
            r=w-1-j
            break
    if x>0:
        if br>l:
            print("Impossible")
            exit()
    bl=l
    br=r
print("Possible")

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

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

Solution (Python):

import sys
INF = float("inf")


def yes():
    print("Possible")  


def no():
    print("Impossible")  


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

    
    if H+W-1 != sum([A[i].count("
        no()
        return

    
    yes()

    pass


if __name__ == '__main__':
    main()

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

for way in itertools.combinations([i for i in range(h + w - 2)], h - 1):
    k = 0
    l = 0
    ij_list =[[k, l]]
    
    for i in range(h + w - 1):
        k += (i in way)
        l += (i not in way)
        ij_list.append([k, l])

    for i, j in itertools.product(range(h), range(w)):
            if [i, j] not in ij_list:
                if a[i][j] != ".":
                    break
            else:
                if a[i][j] != "
                    break
    else:
        print("Possible")
        break

else:
    print("Impossible")

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

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

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

bl = True
x,y = 0,0
for _ in range(H+W-2):
  if x+1 < H and A[x+1][y] == '
    x += 1
    continue
  if y+1 < W and A[x][y+1] == '
    y += 1
    continue
  bl = False
  break

bl = bl and (sum(x.count('
answer = 'Possible' if bl else 'Impossible'
print(answer)

Solution (Python):
import itertools
from sys import stdin
H,W = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for _ in range(H):
    data.append(list(input()))

right = 0
down  = 0
for i in data:
    for j in range(0,W-1):
        if i[j] == "
            right += 1

data_t = []
for i in range(W):
    row = []
    for vector in data:
        row.append(vector[i])
    data_t.append(row)

for i in data_t:
    for j in range(0,H-1):
        if i[j] == "
            down += 1

if down == H-1 and right == W-1:
    print("Possible")
else:
    print("Impossible")

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

f = 1
k = 0
p = 0
for _ in range(h):
  s = input()
  k += s.count("
  if s[p] == ".":
    f = 0
    break
  else:
    for i in range(p,w):
      if s[i] == ".":
        break
      else:
        p = i

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

Solution (Python):
h,w = map(int,input().split())
a=[]
for _ in range(h):
    a.append(input())
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 = [int(item) for item in input().split()]
field = [input().rstrip() for _ in range(h)]
path = 0
for line in field:
    path += line.count("
if path != h + w - 1:
    print("Impossible")
else:
    print("Possible")

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

ds = ((0, 1), (1, 0))
cp = [(0, 0)]
sc = 1

while cp:
	np = []
	for p in cp:
		y, x = p
		for d in ds:
			dy, dx = y + d[0], x + d[1]
			if 0 <= dy < H and 0 <= dx < W:
				if "
					sc += 1
					if not (dy, dx) in np:
						np += [(dy, dx)]
						break
			else:
				continue
	
	cp = np

c = 0
for line in STAGE:
	c += line.count("

print(["Possible", "Impossible"][not(sc == c)])

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

A_lst = []
for i in range(H):
    tmp = list(input())
    A_lst.append(tmp)



def judge(A_lst): 
    for i in range(1, H):
        for j in range(1, W):
            if A_lst[i][j-1] == "
                return False
    return True

if judge(A_lst):
    print("Possible")

else:
    print("Impossible")

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

Solution (Python):
h,w=map(int,input().split())
a=[[i for i in input()] for i in range(h)]
i=0
j=0
a[0][0]="."
while not(i==h-1 and j==w-1):
    if(i==h-1):
        if(a[i][j+1]=="
            a[i][j+1]="."
            j+=1
        else:
            print("Impossible")
            break
    elif(j==w-1):
        if(a[i+1][j]=="
            a[i+1][j]="."
            i+=1
        else:
            print("Impossible")
            break
    else:
        if(a[i][j+1]=="
            a[i][j+1]="."
            j+=1
        elif(not a[i][j+1]=="
            a[i+1][j]="."
            i+=1
        else:
            print("Impossible")
            break
else:
    if any("
        print("Impossible")
    else:
        print("Possible")

Solution (Python):

"""
A - Shik and Stone
https://atcoder.jp/contests/agc007/tasks/agc007_a

"""
import sys


def solve(H, W, grid):
    x, y = 0, 0
    while True:
        grid[y][x] = '@'
        if x+1 < W and grid[y][x+1] == '
            x += 1
        elif y+1 < H and grid[y+1][x] == '
            y += 1
        else:
            break
    for row in grid:
        if '
            return 'Impossible'
    return 'Possible'


def main(args):
    H, W = map(int, input().split())
    grid = [list(input()) for _ in range(H)]
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
h,w=map(int,input().split())
a=""
for i in range(h):a+=input()
print(["Imp","P",][a.count("

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

A[-1] = ['.'] * (W+1)

x = 0
y = 0
p = 1

while x < W and y < H:
    right = A[y][x+1] == '
    down = A[y+1][x] == '
    if right:
        x += 1
        p += 1
    elif down:
        y += 1
        p += 1
    else:
        break

print(['Impossible','Possible'][o == p])

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

Solution (Python):
H,W=map(int,input().split())
G=[input()+"." for _ in range(H)]+["."*(W+1)]
G_cnt=sum([g.count("
p=[0,0]
i=1
while(p!=[H-1,W-1]):
    if G[p[0]+1][p[1]]==G[p[0]][p[1]+1]:
        print("Impossible")
        break
    elif G[p[0]+1][p[1]]=="
        p=[p[0]+1,p[1]]
        i+=1
    else:
        p=[p[0],p[1]+1]
        i+=1
else:
    if i==G_cnt:
        print("Possible")
    else:
        print("Impossible")

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

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

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

def dfs(h, w, count):
    if (h, w) == (H - 1, W - 1):
        return count

    ans = 0
    for nh, nw in [(h + 1, w), (h, w + 1)]:
        if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == "
            ans += dfs(nh, nw, count + 1)
    return ans

if dfs(0, 0, 1) == sum(a.count("
    print("Possible")
else:
    print("Impossible")

Solution (Python):
H,W=map(int,input().split())
L=[]
for i in range(H):
    a=[]
    b=list(input())
    for j in range(W):
        if b[j]=="
            a.append(j)
    if a==[]:
        print("Impossible")
        exit()
    L.append([min(a),max(a)])

for i in range(1,H):
    if L[i][0]==L[i-1][1]:
        pass
    else:
        print("Impossible")
        exit()
print("Possible")

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

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

x = ms = 0
for i in range(H):
    for j in range(x,W):
        if A[i][j] == '.':
            if i==H-1:
                print('Impossible')
            else:
                break
        else:
            x = j
            ms += 1

cs = sum(row.count('

print('Possible' if cs==ms else 'Impossible')

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

numright = 0
numdown = 0
for i in range(H):
    now = A[i][0]
    for j in range(1,W):
        if now == "
            numright += 1
        now = A[i][j]

for i in range(W):
    now = A[0][i]
    for j in range(1,H):
        if now == "
            numdown += 1 
        now = A[j][i]


if numdown == H - 1 and numright == W - 1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
from queue import Queue
h, w = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(input()))
x = [0, 1]
y = [1, 0]
a[0][0] = 0
q = Queue()
q.put([0, 0])
while (q.qsize() > 0):
    start_y, start_x = q.get()
    for i in range(2):
        xx = start_x + x[i]
        yy = start_y + y[i]
        if (xx >= 0) & (xx < w) & (yy >= 0) & (yy < h):
            if a[yy][xx] == "
                a[yy][xx] = a[start_y][start_x] + 1
                q.put([yy, xx])
ans_list = []
for i in range(h):
    ans_list.extend(a[i])
dot_num = ans_list.count(".")
last_num = ans_list[-1]
if last_num != "
    if h*w == dot_num + last_num+1:
        ans = "Possible"
    else:
        ans = "Impossible"
else:
    ans = "Impossible"
print(ans)

Solution (Python):
h,w=map(int,input().split())
A=[input() for i in range(h)]
LR=[]
for i in range(h):
  l=A[i].find("
  r=A[i].rfind("
  LR.append([l,r])
ans=0
for i in range(1,h):
  if LR[i-1][1]==LR[i][0]:
    ans+=1
print("Possible" if ans==h-1 else "Impossible")

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

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

Solution (Python):
h,w = map(int,input().split())
r = 0
for i in range(h):
    s = input()
    a = 0
    for j in range(w):
        if s[j] == "
            if j < r:
                print("Impossible")
                exit()
            else:
                a = j
        else:
            continue
    r = a

print("Possible")

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

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

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

Solution (Python):
n,m=map(int,input().split())
arr=[input() for _ in range(n)]
for i in range(n-1):
  if (m-1)-arr[i][::-1].index('
    print('Impossible')
    break
else:
  print('Possible')

Solution (Python):


import sys
input = sys.stdin.readline

def io_generator():
	return input()



def ll2l(a_list):
	ret=[]
	for i, v in enumerate(a_list):
		if i == 0 or ret[-1][0] != v:
			ret.append([v,1])
		else: 
			ret[-1][1] += 1
	return ret
		

def main(io):
	a, b = map(int, io().split())
	end_pos=0
	ok='Possible'
	ng='Impossible'
	for i in range(a):
		l = list(io())[:b]
		rr=ll2l(l)
		
		if len(rr) == 0:
			return ng
		elif len(rr) >= 4:
			return ng
		elif len(rr)==1 and rr[0][0] == '.':
			return ng
		elif len(rr)==1:
			st=0
			end = rr[0][1]-1
		elif len(rr) == 2 and rr[0][0]=='.':
			st = rr[0][1]
			end = st + rr[1][1]-1
		elif len(rr) == 2 and rr[0][0]=='
			st = 0
			end = rr[0][1] - 1
		elif len(rr) == 3 and rr[0][0]=='
			return ng
		else:
			st=rr[0][1]
			end=st + rr[1][1]-1
		
		if end_pos != st:
			return ng
		end_pos = end
		
	if end_pos==b-1:
		return ok
	return ng
	


if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

Solution (Python):
import re

pattern = re.compile('^(?:\.*)(

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

c = 0
for row in board:
    result = pattern.match(row)
    if result == None or result.start(1) != c:
        print("Impossible")
        exit()
    else:
        c = result.end(1) - 1

print("Possible")

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

currentNode = [0, 0]
visited = [["." for w in range(W)] for h in range(H)]
search = [(0, 1), (1, 0)]

while currentNode != [H-1, W-1]:
    visited[currentNode[0]][currentNode[1]] = "
    tovisit = []
    for s in search:
        nexth, nextw = currentNode[0] + s[0], currentNode[1] + s[1]
        if 0 <= nexth <= H-1 and 0 <= nextw <= W-1:
            if A[nexth][nextw] == "
                tovisit.append([nexth, nextw])
    if len(tovisit) == 1:
        currentNode = tovisit[0]
    else:
        print("Impossible")
        break
else:
    visited[currentNode[0]][currentNode[1]] = "
    flag = True
    for h in range(H):
        for w in range(W):
            if A[h][w] != visited[h][w]:
                flag = False
                break
        if not flag:
            print("Impossible")
            break
    else: print("Possible")

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

flag = 0
for i in range(H):
    tmp = []
    for j,k in enumerate(li[i]):
        if k == '
            tmp.append(j)
    if i != 0 and p != tmp[0]:
        flag = 1
        break
    p = tmp[-1]

print(['Possible', 'Impossible'][flag])

Solution (Python):
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
a = 0
for h in range(H):
    for w in range(W):
        if A[h][w] == '
            a += 1
h = 0
w = 0
d = 0
fh = False
fw = False
while True:
    if h == H-1 and w == W-1:
        break
    
    if h == H-1:
        fh = True
    if w == W-1:
        fw = True
        
    if h < H-1:
        if A[h+1][w] == '
            h += 1
            d += 1
        elif fw:
            break
    if w < W-1:
        if A[h][w+1] == '
            w += 1
            d += 1
        elif fh:
            break
    
if a == d+1:
    print('Possible')
else:
    print('Impossible')

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

pos = [0, 0]
num = 1
while True:
    if pos == [H - 1, W - 1]:
        total = sum(map(lambda A: A.count("
        ans = total == num
        break
    h, w = pos
    if h != H - 1 and A_s[h + 1][w] == "
        pos = [h + 1, w]
        num += 1
        continue
    if w != W - 1 and A_s[h][w + 1] == "
        pos = [h, w + 1]
        num += 1
        continue
    ans = False
    break

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

Solution (Python):
h,w=map(int,input().split())
a,b=0,0
ans="Possible"
for y in range(h):
  m=input()
  a=m.find("
  if a<b:
    ans="Impossible"
    break
  b=m.rfind("
print(ans)

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

Solution (Python):
h, w = map(int, input().split())
amap = ['.' * (w + 2)]
for _ in range(h):
  amap.append('.' + input().strip() + '.')
amap.append('.' * (w + 2))

x, y = 1, 1
is_one = True
while x != w or y != h:
  if x == 1 and y == 1 and amap[y][x] != '
    break
  c = 0
  if amap[y][x+1] == '
    c += 1
  if amap[y][x-1] == '
    c += 1
  if amap[y+1][x] == '
    c += 1
  if amap[y-1][x] == '
    c += 1

  if c != 1:
    break
  else:
    amap[y] = amap[y][:x] + '.' + amap[y][x+1:]
    if amap[y][x+1] == '
      x += 1
    elif amap[y+1][x] == '
      y += 1
    elif amap[y][x-1] == '
      break
    elif amap[y-1][x] == '
      break

if x == w or y == h:
  c = 0
  for a in amap:
    c += a.count('
  if c == 1:
    print('Possible')
  else:
    print('Impossible')
else:
  print('Impossible')

Solution (Python):
from itertools import product

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
tmpH = -1
tmpW = -1
flag = True

for i, j in product(range(H), range(W)):
    if A[i][j] == "
        if i < tmpH or j < tmpW:
            flag = False
            break
        else:
            tmpH = i
            tmpW = j

print("Possible" if flag else "Impossible")

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

Solution (Python):
a,b,*c=open(0).read().split()
if int(a)+int(b)-1==sum(i.count("
    print("Possible")
else:
    print("Impossible")

Solution (Python):

'''
問題
縦H行で横W列の盤面がある
コマははじめ左上隅のマスに置かれており，右下隅に移動した
駒は1マスずつ上下左右に動ける
駒が通ったことのあるマスが提示されるので，駒が常に右または下にしか動いていなかったどうか判定せよ
ただし通ったことのあるマスは'

考察
各行0,1,...,i,...,H-1に対して'
このとき各0,1,...,j,...,H-2について b_j == a_(j+1) であればよい
'''

import re

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

ans = ''
answers = ('Possible','Impossible')

r = re.compile(r'\.*

for i in range(H):
	s = input()
	if len(r.findall(s)) == 1:
		A.append(s)
	else:
		
		ans = answers[1]
		break

if ans == '':
	for i in range(H-1):
		if A[i].rfind('
			continue
		else:
			ans = answers[1]
			break

if ans == '':
	ans = answers[0]

print(ans)

Solution (Python):
h,w = map(int,input().split())
num = []
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] =='
            num.append(j+1)
            
for i in range(len(num)-1):
    if num[i] == num[i+1] or num[i]+1 == num[i+1]:
        continue
    else:
        print('Impossible')
        exit()
print('Possible')

Solution (Python):
from collections import deque
h,w=[int(i) for i in input().split()]
a=[[i for i in input()] for _ in range(h)]
right_count=sum([sum([1 for j in range(w) if a[i][j]=="
pattern=[(1,0),(0,1)]
queue=deque([(0,0)])
def bfs():
    cnt=1
    while queue:
        (x,y)=queue.popleft()
        if (x,y)==(w-1,h-1):
            return cnt
        around=False
        for i,j in pattern:
            if y+i<h and x+j<w:
                if a[y+i][x+j]=="
                    queue.append((x+j,y+i))
                    around=True
                    cnt+=1
        if around==False:
            return False
print("Possible" if bfs()==right_count else "Impossible")

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

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

Solution (Python):
def chk(r, c):
    cnt_in, cnt_out = 0, 0
    if (r, c) == (0, 0): cnt_in += 1
    if (r, c) == (H - 1, W - 1): cnt_out += 1
    if r - 1 >= 0:
        if a[r - 1][c] == '
    if r + 1 < H:
        if a[r + 1][c] == '
    if c - 1 >= 0:
        if a[r][c - 1] == '
    if c + 1 < W:
        if a[r][c + 1] == '
    return cnt_in == 1 and cnt_out == 1


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

bl = True
for r in range(H):
    for c in range(W):
        if a[r][c] == '
            if not chk(r, c):
                bl = False
                break
    else:
        continue
    break

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

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

count = 0

for a in A:
    count += a.count('

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

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

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

Solution (Python):
t=open(0).read();print('I mPp'[t.count('

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

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

flag = 0
for a in A:
    X = a.split('.')
    cnt = 0
    for x in X:
        if '
            cnt += 1
    if cnt > 1:
        flag = 1
        
if flag:
    ans = 'Impossible'
else:
    ans = 'Possible'
    posi = 0
    for i in range(h):
        B = []
        for j in range(w):
            if A[i][j] == '
                B.append(j)
        if B[0] > posi or B[0] < posi:
            ans = 'Impossible'
            break
        else:
            posi = B[-1]

print(ans)

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

Solution (Python):
from itertools import chain
h, w = map(int, input().split())
As = list(chain.from_iterable([list(input()) for i in range(h)]))
print("Possible" if As.count("