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 deque
h, w =  map(int, input().split())
a = [list(input()) for i in range(h)]
mv = [[1, 0], [0, 1]]

sx, sy = 0, 0
gx, gy = h - 1, w - 1
nxt = deque()
nxt.appendleft([sx, sy])

for i in range(h - 1):
    count = 0
    check = 0
    count2 = 0
    for j in range(w):
        if a[i][j] == "
            if a[i][j] == a[i + 1][j]:
                count += 1
                if check == 0:
                    check = 1
                    if count2 > 0:
                        count = 2
                        break
        else:
            if a[i + 1][j] == "
              count2 += 1  

    if count > 1:
        nxt.clear()
        break

flag = 0
while len(nxt) > 0:
    tmp = nxt.pop()
    nwx, nwy = tmp[0], tmp[1]
    if nwx == gx and nwy == gy:
        flag = 1
        break
    count = 0
    for i in range(2):
        tmpx = mv[i][0] + nwx
        tmpy = mv[i][1] + nwy
        if tmpy < w and tmpx < h:
            if a[tmpx][tmpy] == '
                nxt.appendleft([tmpx, tmpy])
                count += 1
    if count > 1:
        break

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

Solution (Python):




h, w = map(int, input().split())

table = []
for _ in range(h):
    a = input()
    temp = []
    for c in a:
        temp.append(c == '
    table.append(temp)

def check():
    for s in table:
        if True in s:
            return False
    return True
    
def solve(y, x):
    if table[y][x] == False:
        return False
    table[y][x] = False
    ret = False
    if y == h - 1 and x == w - 1:
        ret = check()
    else:
        if y < h - 1:
            ret = ret or solve(y + 1, x)
        if x < w - 1:
            ret = ret or solve(y, x + 1)
    table[y][x] = True
    return ret

ans = 'Possible' if solve(0, 0) else 'Impossible'

print(ans)

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

B = list()
for h in range(H):
    B.append(list())
    for w in range(W):
        B[h].append('.')

i = 0
j = 0
ret = "Impossible"
while True:
    B[i][j] = '
    
    if i+1 < H and j+1 < W:
        if A[i][j+1] == "
            
            j += 1
        elif A[i][j+1] == "." and A[i+1][j] == "
            
            i += 1
        else:
            break
    
    elif i+1 == H and j+1 < W:
        if A[i][j+1] == "
            
            j += 1
        else:
            break
    
    elif i+1 < H and j+1 == W:
        if A[i+1][j] == "
            
            i += 1
        else:
            break
    elif i+1 == H and j+1 == W:
        if A == B:
            ret = "Possible"
        break
print ret

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

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

prevend=0
for i in range(H):
    for j in range(W):
        if A[i][j] == '
            print ("Impossible")
            exit()
        elif j>0 and A[i][j-1] == '
            prevend = j-1
            break
        elif j==W-1:
            prevend =W-1

prevend = 0
for j in range(W):
    for i in range(H):
        if A[i][j] == '
            print ("Impossible")
            exit()
        elif i>0 and A[i-1][j] == '
            prevend = i-1
            break
        elif i==H-1:
            prevend =H-1


print("Possible")

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

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

possible = True
prev_min_hash = W

for h in range(H-1, -1, -1):
    max_hash = 0
    for w in range(W):
        if array[h][w] == "
            max_hash = w

    if max_hash > prev_min_hash:
        possible = False
        break

    for w in range(W-1, -1, -1):
        if array[h][w] == "
            prev_min_hash = w

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

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

m = []
m.append('.'*(W+2))
for i in range(H):
    m.append('.'+input()+'.')

m.append('.'*(W+2))

x, y = 1, 1

while not(x==W and y==H):
    if(m[y][x+1]==m[y+1][x] or m[y][x-1]==m[y-1][x]=='
        print('Impossible')
        exit()
    if(m[y][x+1]=='
        x+=1
    elif(m[y+1][x]=='
        y+=1


print('Impossible' if m[y-1][x]==m[y][x-1]=='

Solution (Python):
import sys

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

board = [[-1 for i in range(w)] for j in range(h)]
board[0][0] = 0

movecol = [1, 0]
moverow = [0, 1]
count = 0


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

def dfs(x, y, n):
    
    if(x >= w or y >= h or a[y][x] == "."):
        flag = -1
        return
    
    if(x == w-1 and y == h-1):
        if(n == count):
            print("Possible")
            sys.exit()
        else:
            flag = -1

    for i in range(2):
        nextx = x + movecol[i]
        nexty = y + moverow[i]
        dfs(nextx, nexty, n+1)

dfs(0, 0, 1)
print("Impossible")

Solution (Python):


H, W = map(int, input().split())
F = [list(input()) for x in range(H)]
ans = True
px = py = 0
while py < H-1 or px < W-1:
    if py<H-1 and F[py+1][px]=='
        if (px<W-1 and F[py][px+1]=='
            ans = False
            break
        py += 1
    elif px<W-1 and F[py][px+1]=='
        if py>0 and F[py-1][px+1]=='
            ans = False
            break
        px += 1
    else:
        ans = False
        break
print('Possible' if ans else 'Impossible')

Solution (Python):
import sys

IMPOSSIBLE = 'Impossible'
POSSIBLE = 'Possible'

def solve():
    H, W = map(int, sys.stdin.readline().split())
    lines = list(map(lambda s: s.rstrip(), sys.stdin.readlines()))
    maxs = []
    mins = []
    for line in lines:
        m = -1
        for i, w in enumerate(line):
            if w == '
                m = i
        maxs.append(m)
        m = len(line)
        for i, w in reversed(list(enumerate(line))):
            if w == '
                m = i
        mins.append(m)

    for i, (min, max) in enumerate(zip(mins, maxs)):
        if '.' in lines[i][min:max+1]:
            return IMPOSSIBLE

    for min, max in zip(mins[1:], maxs):
        if min != max:
            return IMPOSSIBLE

    return POSSIBLE

print(solve())

Solution (Python):
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

(H, W) = reads()
A = []

for _ in range(H):
  A.append(input()+".")
A.append("." * (W+1))

walk = [(0, 0)]

for i in range(H + W - 2):
  (y, x) = walk[-1]
  if A[y][x+1] == "
      walk.append((y, x+1))
  elif A[y+1][x] == "
      walk.append((y+1, x))
  else:
    print("Impossible"); exit()

if all(A[y][x] == "." for y in range(H) for x in range(W) if not (y, x) in walk):
  print("Possible")
else:
  print("Impossible")

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        if g[y][x]=="
            return True
    return False

def dfs(y,x):
    dx=(0,1)
    dy=(1,0)
    if y==h-1 and x==w-1:
        return True
    for i in xrange(2):
        nxy=y+dy[i]
        nxx=x+dx[i]
        if check(nxy,nxx) and not visited[nxy][nxx]:
            visited[nxy][nxx]=True
            if dfs(nxy,nxx):
                return True
            visited[nxy][nxx]=False
    return False

h,w=map(int,raw_input().split())
g=[raw_input() for _ in xrange(h)]
visited=[[False]*w for _ in xrange(h)]
visited[0][0]=True
if not dfs(0,0):
    print("Impossible")
    exit()
for i in xrange(h):
    for j in xrange(w):
        if g[i][j]=="
            print("Impossible")
            exit()
print("Possible")

Solution (Python):



import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        h, w = map(int, input().split())
        a = []
        for i in range(h):
            a.append(list(input()))
        
        
        

        hash = []
        for i in range(h):
            for j in range(w):
                if a[i][j] == '
                    hash.append((i, j))
        
                
        queue = [(0, 0, [(0, 0)])]
        flag = False
        while queue:
            
            i, j, hist = queue.pop(0)
            if (i, j) == (h - 1, w - 1) and a[i][j] == '
                flag = True
                break
            else:
                if i + 1 < h and a[i+1][j] == '
                    queue.append((i + 1, j, hist + [(i + 1, j)]))
                if j + 1 < w and a[i][j+1] == '
                    queue.append((i, j + 1, hist + [(i, j + 1)]))
        if flag:
            print('Possible')
        else:
            print('Impossible')
        
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Solution (Python):
import sys

if __name__ == '__main__':
    H, W = (int(i) for i in input().split())
    arr = input()
    index = arr.rfind("
    for i in range(H-1):
        arr = input()
        if arr.find("
            print("Impossible")
            sys.exit()

        if arr.rfind("
            print("Impossible")
            sys.exit()

        index = arr.rfind("

    print("Possible")

Solution (Python):



def rl(s): return xrange(len(s))

INF = 2147483647


import sys
stdin = sys.stdin

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

lines = [stdin.readline() + '.' for _ in range(H)] + ['.' * W]

fail = False
for y, line in enumerate(lines):
    for x, ch in enumerate(line):
        if ch != '
        if x == W-1 and y == H-1: continue

        right = (line[x+1] == '
        down = (lines[y+1][x] == '
        if not (right ^ down):
            fail = True

        if not (x == 0 and y == 0):
            if x == 0:
                if lines[y-1][x] != '
            elif y == 0:
                if line[x-1] != '
            else:
                if not ( (lines[y-1][x] == '
                    fail = True

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

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

A = [list(map(lambda x: x=="




try:
    for i in range(H):
        for j in range(W):
            if A[i][j]:
                start=i,j
                raise
except:
    pass


def a(i,j):
    if i<H and j<W:
        return A[i][j]
    return False

tmp =start
used = [start]
while True:
    
    i,j =tmp
    if a(i+1,j):
        tmp = i+1,j
        used.append(tmp)
        continue
    if a(i,j+1):
        tmp = i ,j+1
        used.append(tmp)
    else:
        break

for i in range(H):
    for j in range(W):
        if A[i][j]:
            if (i,j) in used:
                continue
            else:
                
                print("Impossible")
                exit()
print("Possible")

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

def solve():
    x, y = 0, 0
    while x != w - 1 or y != h - 1:
        m[y][x] = '.'

        if y < h - 1 and m[y + 1][x] == '
            if x < w - 1 and m[y][x + 1] == '
                return False
            else:
                if '
                    return False
                y += 1
        elif x < w - 1 and m[y][x + 1] == '
            for i in range(h):
                if '
                    return False
            x += 1
        else:
            return False

    return True

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

Solution (Python):
h, w = map(int, raw_input().split())
s = [list(raw_input().strip()) for _ in xrange(h)]
def dfs(x, y):
    if x == w - 1 and y == h - 1:
        s[y][x] = '.'
        return 1
    if x < w - 1 and s[y][x+1] == '
        s[y][x] = '.'
        return 1
    if y < h - 1 and s[y+1][x] == '
        s[y][x] = '.'
        return 1
    return 0
if dfs(0, 0) and sum(''.join(r).count('
    print "Possible"
else:
    print "Impossible"

Solution (Python):
h,w=map(int,raw_input().split())
l=[]

for i in range(h):
    l.append(list(raw_input()))
l[0][0]='.'
x=y=0
while 1:
    if x+1<w and l[y][x+1]=='
        x+=1
        l[y][x]='.'
    elif y+1<h and l[y+1][x]=='
        y+=1
        l[y][x]='.'
    else:
        break
for i in l:
    if '
        print 'Impossible'
        exit()
print 'Possible'

Solution (Python):
h, w = map(int, raw_input().split())
A = [list(raw_input()) for i in xrange(h)]

x = y = 0
A[0][0] = '.'
while 1:
    if y+1 < h and A[y+1][x] == '
        A[y+1][x] = '.'
        y += 1
    elif x+1 < w and A[y][x+1] == '
        A[y][x+1] = '.'
        x += 1
    else: break
if y == h-1 and x == w-1 and all(all(f is '.' for f in e) for e in A):
    print "Possible"
else:
    print "Impossible"

Solution (Python):
H, W= map(int, raw_input().split())
array = []
for i in range(H):
    array.append(list(raw_input()))


left = 0
possible = True
for i in range(H):
    for j in range(W):
        if array[i][j] == "
            if j < left:
                possible = False
                break
            if j > left:
                left = j

if possible:
    print "Possible"
else:
    print "Impossible"

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

current = (0,0)
good = True
for y in range(H):
    for x in range(W):
        if grid[y][x] == "
            count = 0
            aboveCount = 0
            if W-1>x and grid[y][x+1] == "
                count+=1
            if H-1>y and grid[y+1][x] == "
                count+=1
            if x>0 and grid[y][x-1] == "
                aboveCount+=1
            if 0<y and grid[y-1][x] == "
                aboveCount+=1
            if (aboveCount==0 and y+x!=0) or (count!=1 and y+x!=H+W-2):
                good = False
                break
if good:
    print("Possible")
else:
    print("Impossible")

Solution (Python):
import sys
h,w=map(int,raw_input().split())
a=[list(raw_input()) for _ in range(h)]
b=[['.']*w for _ in range(h)]
i=j=0
flag=True
while flag:
    b[i][j]='
    if (i,j)==(h-1,w-1):break
    flag=False
    if i+1<h:
        if a[i+1][j]=='
    if not flag and j+1<w:
        if a[i][j+1]=='
if a==b:print 'Possible'
else:print 'Impossible'

Solution (Python):
import re

def main():
    H, W = map(int, raw_input().split())
    prev_end = 0
    HASH_RE = re.compile(r"
    for i in range(H):
        A = raw_input()
        if HASH_RE.search(A, endpos=prev_end-1) is not None:
            print "Impossible"
            return 0

        m = HASH_RE.search(A, pos=prev_end-1)
        if m is None:
            print "Impossible"
            return 0

        if HASH_RE.search(A, pos=m.end()):
            print "Impossible"
            return 0

        prev_end = m.end()

    print "Possible"

if __name__ == "__main__":
    main()

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

used[0][0] = True
q = [(0, 0)]

while len(q) > 0:
    y, x = q[0]
    q = q[1:]
    if x+1 < W and board[y][x+1]=='
        used[y][x+1] = True;
        q.append((y, x+1))
    elif y+1 < H and board[y+1][x]=='
        used[y+1][x] = True;
        q.append((y+1, x))

ans = True
for i in range(H):
    for j in range(W):
        if board[i][j] == '
            ans = ans and used[i][j]

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

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

x,y = 0,0
while (x!=W-1 or y!=H-1):
    A[y][x] = "."
    r = x<W-1 and A[y][x+1]=="
    d = y<H-1 and A[y+1][x]=="

    if int(r)+int(d)!=1:
        print "Impossible"
        exit(0)
    if r:
        x += 1
    if d:
        y += 1

if sum(a.count("
    print "Impossible"
    exit(0)
print "Possible"

Solution (Python):
H, W = map(int, raw_input().split())
B = [raw_input() for _ in xrange(H)]
r, c = 0, 0
s = set()

while r != H-1 or c != W-1:
    s.add((r, c))
    if r < H-1 and c < W-1:
        if B[r+1][c] == '
            print 'Impossible'
            exit()
        elif B[r+1][c] == '.' and B[r][c+1] == '.':
            print 'Impossible'
            exit()
        elif B[r+1][c] == '
            r += 1
            continue
        else:
            c += 1
            continue
    elif r == H-1:
        if B[r][c+1] == '.':
            print 'Impossible'
            exit()
        else:
            c += 1
            continue
    else:
        if B[r+1][c] == '.':
            print 'Impossible'
            exit()
        else:
            r += 1
            continue

s.add((H-1, W-1))

t = set()
for i in xrange(H):
    for j in xrange(W):
        if B[i][j] == '
            t.add((i, j))

if s == t:
    print 'Possible'
else:
    print 'Impossible'

Solution (Python):
line=input().split()
h=int(line[0])
w=int(line[1])
m = []
m.append("."*(w+2))
for i in range (h):
    m.append("." + input() + ".")
m.append("."*(w+2))
works=True
for i in range (1,h+1):
    for j in range (1,w+1):
        if m[i][j]=="
            if m[i+1][j]=="
                works=False
            if m[i-1][j]=="
                works=False
if works:
    print ("Possible")
else:
    print("Impossible")

Solution (Python):

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

H, W = ln()

panel = [['.'] + list(s()) + ['.'] for h in xrange(H)]

cur = 1

for i in xrange(H):
    for j in xrange(cur, W + 1):
        if panel[i][j] == '
            panel[i][j] = '.'
            cur = j
        else:
            break

success = True
for i in xrange(H):
    for j in xrange(1, W + 1):
        if panel[i][j] == '
            success = False
            break
    if not success:
        break

if success:
    print 'Possible'
else:
    print 'Impossible'

Solution (Python):



import sys

def rl(proc=None):
    if proc is not None:
        return proc(sys.stdin.readline())
    else:
        return sys.stdin.readline().rstrip()

def srl(proc=None):
    if proc is not None:
        return map(proc, rl().split())
    else:
        return rl().split()

def go(a, x, y):
    if a[x][y] != '
        return []
    r = [(x, y)]
    while True:
        for tx, ty in ((x+1, y), (x, y+1)):
            if 0 <= tx < len(a) and 0 <= ty < len(a[0]) and a[tx][ty] == '
                x = tx
                y = ty
                break
        else:
            break
        r.append((x,y))
    return r


def main():
    R, C = srl(int)
    a = []
    for _ in xrange(R):
        a.append(rl())
    b = go(a, 0, 0)
    if not b or b[-1] != (R-1, C-1):
        print "Impossible"
        return
    s = sum(x.count('
    print "Impossible" if s != len(b) else "Possible"

if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
a1 = []
s = input()
for j in range(w):
    if s[j] == "
        a1.append(j)
a =[]
for i in range(h - 1):
    s = input()
    for j in range(w):
        if s[j] == "
            a.append(j)
    if a[0] < a1[len(a1) - 1]:
        print("Impossible")
        raise SystemExit
    a1 = [i for i in a]
    a = []
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):



def main():
    h, w = (int(x) for x in input().split())
    passed = sum(input().count("
    if passed == h + w - 1:
        print("Possible")
    else:
        print("Impossible")


if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
ans = 0
for i 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())
cnt = 0
for _ in range(h):
    cnt += input().count('
print('Possible' if cnt == h + w - 1 else 'Impossible')

Solution (Python):



H,W=map(int,raw_input().split())
c=0
for _ in xrange(H):
    s=raw_input()
    for i in xrange(W):
        if s[i]=="
if H+W-1==c: print "Possible"
else: print "Impossible"