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
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


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

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

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

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


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

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

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

a = [list(input()) for _ in range(h)]
cnt = 1
for x in range(h):
    for y in range(w):
        if a[x][y] == '
            cnt += 1
            

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

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

ans='Possible'
for i in range(h-1):
    for j in range(w-1):
        if r[i][j]=='
            ans='Impossible'
        elif r[i][j]=='.' and r[i][j+1]=='
            ans='Impossible'
        elif r[i][j]=='
            ans='Impossible'

print(ans)

Solution (Python):



H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (0,1)}
init_q =[]

from collections import deque

def bfs(init):
    next_q = deque([])
    for i in init:
        next_q.append(i)
        Dist[i[0]][i[1]] = 1

    while len(next_q)!=0:
        
        h,w = next_q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='
                next_q.append([hs,ws])
                Dist[hs][ws] = Dist[h][w] + 1
    return Dist

def main():
    
    init_q.append([sth, stw])

    ret = bfs(init_q)
    if ret[glh][glw]>0 and ret[glh][glw]==sum([a.count('
        print('Possible')
    else:
        print('Impossible')

if __name__ == '__main__':
    main()

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())
A = [list(str(input())) for _ in range(H)]
for i in range(H):
  A[i] += '.'
A += [list('.'*(W+1))]
y,x = 0,0
ans = 'Impossible'
while y < H and x < W:
  if A[y+1][x] == '
    break
  elif A[y+1][x] == '
    if '
      break
    y += 1
  elif A[y][x+1] == '
    x += 1
  else:
    break
  if y == H-1 and x == W-1:
    ans = 'Possible'
    break
print(ans)

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

field = [list(input()) for i in range(h)]

cnt = 0

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

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

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

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

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


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


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin

def main():
    from collections import deque
    input = stdin.readline

    h, w = map(int, input().split())
    cm = [["."] * (w + 2) for _ in range(h + 2)]
    que = deque([])
    for i in range(1, h + 1):
        cm[i] = "." + input().rstrip('\n') + "."
    que.append([1, 1])
    while len(que) > 0:
        y, x = que.popleft()
        if (cm[y + 1][x] == "
            print('Impossible')
            exit()
        if cm[y + 1][x] == "
            que.append([y + 1, x])
        if cm[y][x + 1] == "
            que.append([y, x + 1])
    print('Possible')
main()

Solution (Python):
h, w =map(int, input().split())
grid = [None]*h
count = -1
for i in range(h):
  grid[i] = input()
  count += grid[i].count("

x, y = 0, 0

while True:
  if x == h-1 and y == w-1:
    if count == 0:
      print("Possible")
    else:
      print("Impossible")
    break
  elif x == h-1:
    if grid[x][y+1] == ".":
      print("Impossible")
      break
    y += 1
    count -= 1
  elif y == w-1:
    if grid[x+1][y] == ".":
      print("Impossible")
      break
    x += 1
    count -= 1
  else:
    if grid[x+1][y] == grid[x][y+1]:
      print("Impossible")
      break
    if grid[x+1][y] == "
      x += 1
    else:
      y += 1
    count -= 1

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

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
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
from decimal import *

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

cnt_w = sum([X.count("

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
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
from decimal import *

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

cnt_w = sum([X.count("

def DFS(y, x, cnt):
	if 0 <= x+1 <= W-1 and A[y][x+1] == "
			return DFS(y, x+1, cnt+1)
	elif 0 <= y+1 <= H-1 and A[y+1][x] == "
			return DFS(y+1, x, cnt+1)
	else:
		return (y, x, cnt)

if A[0][0] != "
	print("Impossible")
elif (H-1, W-1, cnt_w) == DFS(0, 0, 1):
	print("Possible")
else:
	print("Impossible")

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

H,W = map(int,readline().split())
r = 0
for i in range(H):
  r += readline().rstrip().count("
  
if r != H + W - 1:
  print("Impossible")
else:
  print("Possible")

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

cnt = 0
for _ in  range(H):
    l = input()
    cnt += l.count('

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

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip("\n") for _ in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "
    print("Possible" if count == H + W - 1 else "Impossible")

    return 0

if __name__ == "__main__":
    solve()

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

Solution (Python):
H, W = map(int, input().split())
b = 0
ans = 'Possible'
for i in range(H):
  a = input()
  for j in range(W):
    if a[j] == '
      if j>=b:
        b = j
      else:
        ans = 'Impossible'
print(ans)

Solution (Python):






from collections import defaultdict











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

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
h,w = readInts()
A = [input() for _ in range(h)]
cnt = 0
for y in range(h):
    for x in range(w):
        if A[y][x] == '
            cnt += 1
if h + w - 1 == cnt:
    print('Possible')
else:
    print('Impossible')

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

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

for i in range(H):
    for j in range(W):
        if a[i][j] == "
            x = i-1
            y = j+1

            if 0 <= x < H and 0 <= y < W:
                if a[x][y] == "
                    print("Impossible")
                    exit()
            
            x = i+1
            y = j-1
            if 0 <= x < H and 0 <= y < W:
                if a[x][y] == "
                    print("Impossible")
                    exit()
print("Possible")

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

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

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

Solution (Python):
h, w = map(int, input().split())
cnt = 0
for i in range(h):
    ai = input()
    for j in range(w):
        if ai[j] == '
            cnt += 1

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


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


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


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




H,W = IL()
data = SLs(H)

now = 0
for i in range(H):
  flag = 0
  for j in range(now,W):
    if data[i] == "."*now + "
      now = j
      flag = 1
      break
  if flag == 0:
    print("Impossible")
    exit()
print("Possible")

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

Solution (Python):
h,w=map(int,input().split())
a=[]
c=0
for i in range(h):
  a.append(input())
  c+=a[i].count('
flg=0
if c != h+w-1:
  flg=1
dh=0
dw=0
for i in range(h+w-2):
  if dh==h-1:
    if a[dh][dw+1]=='
      dw+=1
  elif dw==w-1:
    if a[dh+1][dw]=='
      dh+=1
  else:
    if a[dh+1][dw]=='
      dh+=1
    elif a[dh][dw+1]=='
      dw+=1
    else:
      flg=1
if flg==0:
  print('Possible')
else:
  print('Impossible')

Solution (Python):
def main():
    h,w=map(int,input().split())
    a=[]
    for _ in range(h):
        a.append(input())
    now = (0, 0)
    end = (h-1, w-1)
    visited = set([now])
    while True:
        nxt = None
        
        if now[0]+1 < len(a) and a[now[0]+1][now[1]] == "
            nxt = (now[0]+1, now[1])
        if now[1]+1 < len(a[now[0]]) and a[now[0]][now[1]+1] == "
            if nxt is not None:
                print("Impossible")
                return
            nxt = (now[0], now[1]+1)
        
        if now[0]-1 >= 0 and a[now[0]-1][now[1]] == "
            if (now[0]-1,now[1]) not in visited:
                print("Impossible")
                return
        if now[1]-1 >= 0 and a[now[0]][now[1]-1] == "
            if (now[0],now[1]-1) not in visited:
                print("Impossible")
                return
        
        if now == end:
            break
        if nxt is None:
            print("Impossible")
            return
        now = nxt
        visited.add(nxt)
    print("Possible")
    
if __name__ == "__main__":
    main()

Solution (Python):
h,w = map(int,input().split())
a = []
cnt = 0
for _ in range(h):
    a.append(list(input()))
    cnt += a[-1].count("
looked = [[True for _ in range(w)]for i in range(h)]
looked[0][0] = False
x,y = 0,1
now = [0,0]
ans = 1

while(True):
    look = [[min(now[y]+1,h-1),now[x]],[now[y],min(now[x]+1,w-1)]]
    flag = 1
    for i in range(2):
        if looked[look[i][x]][look[i][y]]:
            if a[look[i][x]][look[i][y]] == "
                now = [look[i][y],look[i][x]]
                looked[look[i][x]][look[i][y]] = False
                ans += 1
                flag = 0
                break
    if flag:
        break
if ans == cnt and now == [w-1,h-1]:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction



mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]







h,w=l()
A=[input() for i in range(h)]
ans=0
for i in range(h):
    for j  in  range(w):
        if(A[i][j]=="
            ans+=1



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

Solution (Python):
h,w = map(int,input().split())
left = 0
ok = True
flag = "ok"
for i in range(h):
    dum = input()
    for j in range(0,w):
        if j < left and dum[j] == "
            print("Impossible")
            exit()
        if dum[j] == "
            left_o = j
            flag = "ng"
    left = left_o
    flag = "ok"
print("Possible")

Solution (Python):
H,W = list(map(int,input().split()))
A = [list(input()) for _ in range(H)]
x = 0
y = 0
A[y][x] = 'x'
while True:
    if x < W-1 and A[y][x+1] == '
        x = x+1
        A[y][x] = 'x'
    elif y < H-1 and A[y+1][x] == '
        y = y+1
        A[y][x] = 'x'
    elif y < H-1 and A[y+1][x] == '.':
        print('Impossible')
        exit()
    else:
        break
for a in A:
    if '
        print('Impossible')
        exit()
print('Possible')

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

Flag=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
    Flag=False
    
Flag= Flag and (sum(x.count("
if Flag:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
h,w=map(int,input().split())
list1=[]
ans=0
count1=0
count2=0
count3=0
for i in range(h):
    list1.append(list(input()))
for i in range(h):
    count3+=list1[i].count("
if count3!=h+w-1:
    ans=1
for i in range(h+w-3):
    if count2!=w-1:
        if list1[count1][count2+1]=="
            count2+=1
    if count1!=h-1:
        if list1[count1+1][count2]=="
            count1+=1
    if count2!=w-1:
        if count1!=h-1:
            if list1[count1+1][count2]=="." and list1[count1][count2+1]==".":
                ans=1
                break
        else:
            if list1[count1][count2+1]==".":
                ans=1
                break
    elif count1!=h-1:
        if list1[count1+1][count2]==".":
            ans=1
            break
if count1!=h-1 or count2!=w-1:
    ans=1
if h==2 and w==2:
    if list1[0][0]=="
        ans=0
if ans==1:
    print("Impossible")
else:
    print("Possible")

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

edge = [["." for _ in range(W+2)]]
center = [["."] + list(input()) + ["."] for i in range(H)]
A_array = edge + center + edge

def is_there_OK_move(before_i,before_j,before_move):
    if before_move == "right":
        i = before_i
        j = before_j + 1
    elif before_move == "down":
        i = before_i + 1
        j = before_j

    up = A_array[i-1][j]
    down = A_array[i+1][j]
    right = A_array[i][j+1]
    left = A_array[i][j-1]
    
    if i == H and j == W:
        if up == left == "
            return -1
        else:
            return 1
    elif (down == right == "
        return -1
    else:
        if down == "
            return is_there_OK_move(i,j,"down")
        elif right == "
            return is_there_OK_move(i,j,"right")


ans = is_there_OK_move(0,1,"down")

if ans == 1:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
def main():
    h, w = list(map(int, input().split()))
    A = [['.'] * (w + 2)] + [['.', ] + list(input()) + ['.', ] for _ in range(h)] + [['.'] * (w + 2)]
    i, j = 1, 1
    while True:
        A[i][j] = '.'
        if i == h and j == w:
            break
        if A[i + 1][j] == A[i][j + 1]:
            print('Impossible')
            exit()
        if A[i + 1][j] == '
            i += 1
        else:
            j += 1
    for a in A:
        if any([i == '
            print('Impossible')
            break
    else:
        print('Possible')

if __name__ == '__main__':
    main()

Solution (Python):
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

h,w = iim()
l = []
for _ in range(h):
    l.append(list(input()))

flag = True
for i in range(h):
    for j in range(w):
        if l[i][j] == '
            if i < h-1 and j < w-1:
                if l[i][j+1] == l[i+1][j]:
                    flag = False
            elif i == h-1:
                if l[i][j+1] != '
                    flag = False
            elif j == w-1:
                if l[i+1][j] != '
                    flag = False

for i in range(h):
    for j in range(w):
        if l[i][j] == '
            if i > 0 and j > 0:
                if l[i][j-1] == l[i-1][j]:
                    flag = False
            elif i == 0:
                if l[i][j-1] != '
                    flag = False
            elif j == 0:
                if l[i-1][j] != '
                    flag = False


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

Solution (Python):
h, w = map(int, input().split())
A = []
res_w = []
for i in range(h):
    line = [s for s in input()]
    c = []
    for j in range(len(line)):
        if line[j] == '
            c.append(j)
            if (len(c) > 1) and (c[-2] - c[-1] > 1):
                print('Impossible')
                exit()
            if j not in res_w:
                res_w.append(j)
            else:
                if max(res_w) > j:
                    
                    print('Impossible')
                    exit()
print('Possible')

Solution (Python):
from collections import deque


H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
q = deque([(0, 0, [(0, 0)])])
visited = {(0, 0)}
while q:
    i, j, path = q.popleft()
    if (i, j) == (H - 1, W - 1):
        for pi, pj in path:
            field[pi][pj] = "."
        break
    for di, dj in ((1, 0), (0, 1)):
        ni, nj = i + di, j + dj
        if (
            0 <= ni < H
            and 0 <= nj < W
            and field[ni][nj] == "
            and (ni, nj) not in visited
        ):
            visited.add((ni, nj))
            q.append((ni, nj, path + [(ni, nj)]))

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

Solution (Python):
H, W = map(int, 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())
tizu = [list(input()) for _ in range(h)]
pos = 1
for row in tizu:
    pos -= 1
    for i, index in enumerate(row):
        if i == pos:
            if index == "
                pos += 1
        else:
            if index == "
                print("Impossible")
                exit()
print("Possible")

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

flag = True

prev = 0
for a in A:
    if prev > 0:
        if '
            flag *= False
    prev = max([n for n, v in enumerate(a) if v == '
if flag:
    print('Possible')
else:
    print('Impossible')

Solution (Python):
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    M = [''] * H
    f = False
    for h in range(H):
        M[h] = list(input().strip())
        if '
            f = True
    s = deque([(0, 0)])
    if not f:
        print('Impossible')
        return
    if M[0][0] == '.':
        print('Impossible')
        return
    M[0][0] = '.'
    while s:
        (h, w) = s.popleft()
        if h + 1 < H:
            if M[h+1][w] == '
                M[h+1][w] = '.'
                s.append((h+1, w))
                continue
        if w + 1 < W:
            if M[h][w+1] == '
                M[h][w+1] = '.'
                s.append((h, w+1))

    for h in range(H):
        if '
            print('Impossible')
            return
    else:
        print('Possible')
        return

if __name__ == '__main__':
    main()

Solution (Python):
h,w = map(int,input().split())
a = [list(input()) for nesya in range(h)]
c = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == '
      c += 1

if c == h+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):
h,w=map(int,input().split())
a = [list(input()) for _ in range(h)]
a[0][0] = "."
q=[(0,0)]
dy=[0,1]
dx=[1,0]
while len(q)>0:
    y,x=q.pop(0)
    if y == h-1 and x == w-1:
        break
    for i in range(2):
        if not (0<=dy[i]+y<h and 0<=dx[i]+x<w):
            continue
        if a[dy[i]+y][dx[i]+x] != "
            continue
        else:
            a[dy[i]+y][dx[i]+x] = "."
            q.append((dy[i]+y,dx[i]+x))
            break
f = True
for i in range(h):
    for j in range(w):
        
        if a[i][j] == "
            f = False
if f:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    q = collections.deque()

    q.append((0, 0))
    v = set()
    v.add((0, 0))

    while q:
        c = q.popleft()

        cnt = 0
        for nj, ni in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
            if 0 <= nj + c[0] < H and 0 <= ni + c[1] < W:
                if (nj + c[0], ni + c[1]) in v or A[nj + c[0]][ni + c[1]] == '.':
                    continue
                cnt += 1
                if nj < 0 or ni < 0:
                    print("Impossible")
                    return
                q.append((nj + c[0], ni + c[1]))
                v.add((nj + c[0], ni + c[1]))

        if cnt > 1:
            print("Impossible")
            return

    print("Possible")



if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
a = [input() for _i in range(h)]
p = 0
for i in range(h):
    x = [j for j in range(w) if a[i][j]=="
    for j in range(len(x)-1):
        if x[j]+1==x[j+1]:
            continue
        else:
            import sys
            print("Impossible")
            sys.exit()
    if p==x[0]:
        p = x[-1]
    else:
        import sys
        print("Impossible")
        sys.exit()
print("Possible")