Problem:


Score : 200 points

Problem Statement

   #nck {
      width: 30px;
      height: auto;
   }

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



Sample input:
4 5
##...
.##..
..##.
...##


Sample output:
Possible

Submission status: Wrong Answer

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

r = 0
c = 0
while True:
    bl_go_right = (a[r][c+1] == '#') if ((c + 1) < w) else False
    bl_go_down = (a[r+1][c] == '#') if ((r + 1) < h) else False
    #print(r,c,bl_go_right,bl_go_down)
    if (bl_go_right and bl_go_down):
        flg = False
        break
    elif not(bl_go_right or bl_go_down):
        if (r == (h - 1)) and (c == (w - 1)):
            flg = True
            break
        else:
            flg = False
            break
    elif bl_go_right:
        c += 1
    elif bl_go_down:
        r += 1
print('Possible' if flg else 'Impossible')

Submission status: Wrong Answer

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

r = 0
c = 0
while True:
    r_flg = (a[r][c+1] == '#') if ((c + 1) < w) else False
    d_flg = (a[r+1][c] == '#') if ((r + 1) < h) else False
    #print(r,c,r_flg,d_flg)
    if (r_flg and d_flg):
        flg = False
        break
    elif (not r_flg and not d_flg):
        if (r == (h - 1)) and (c == (w - 1)):
            flg = True
            break
        else:
            flg = False
            break
    elif r_flg:
        c += 1
    elif d_flg:
        r += 1
print('Possible' if flg else 'Impossible')

Submission status: Wrong Answer

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

r = 0
c = 0
flg = True
while (c < w) and (r < h):
    r_flg = (a[r][c+1] == '#') if ((c + 1) < w) else False
    d_flg = (a[r+1][c] == '#') if ((r + 1) < h) else False
    #print(r,c,r_flg,d_flg)
    if (r_flg and d_flg):
        flg = False
        break
    elif (not r_flg and not d_flg):
        if (r == (h - 1)) and (c == (w - 1)):
            flg = True
            break
        else:
            flg = False
            break
    elif r_flg:
        c += 1
    elif d_flg:
        r += 1
print('Possible' if flg else 'Impossible')

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a = [list(input()).count('#') for i in range(h)]
print("Possible" if sum(a) == h+w-1 else "Imossible")

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a = [list(input()) for i in range(h)]
def f(i,j):
	global a
	return 1 if 0 <= i and i < h and 0 <= j and j < w and a[i][j] == '#' else 0
print("Impossible" if sum([sum([0 if f(i,j) == 0 or (f(i-1,j)+f(i,j-1) == 1 and f(i,j+1)+f(i+1,j) == 1) else 1 for j in range(w)]) for i in range(h)]) > 2 else "Possible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
array = [y.count("#") for y in input() for x in range(h)]
print("Possible" if sum(array) == h + w - 1 else "Impossible")

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split(' '))
maps = [input() for _ in range(H)]

flag = 1 # default: 1 = Possible, 0 = Impossible

for i in range(H-1):
    for j in range(W-1):
        if maps[i][j] == maps[i+1][j] == maps[i][j+1] == maps[i+1][j+1] == '#':
            flag = 0

for i in range(H-2):
    for j in range(W):
        if maps[i][j] == maps[i+2][j] == '#' and maps[i+1][j] == '.':
            flag = 0

for i in range(H):
    for j in range(W-2):
        if maps[i][j] == maps[i][j+2] == '#' and maps[i][j+1] == '.':
            flag = 0

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
l = []
l.append([l]*(w+2))
for i in range(h):
  temp = list(input())
  l.append([0] + temp + [0])
l.append([l]*(w+2))
x, y = 1, 1
while True:
  if x == w-1 and y == h-1:
    print('Possible') 
    break
  if l[y+1][x] == '#' and l[y][x+1] == '#' or l[y+1][x] == '#' and l[y+1][x-1] == '#':
    print('Impossible')
    break
  elif l[y+1][x] == '#':
    y += 1
  elif l[y][x+1] == '#':
    x += 1
  else:
    break

Submission status: Wrong Answer

Solution code:
def read():
    return [int(x) for x in str.split(raw_input())]

n, m = read()
st = []

for i in range(n):
    st.append(raw_input())

def can_down(st, x, y):
    return x+1 < n and st[x+1][y] == '#'

def can_right(st, x, y):
    return y+1 < m and st[x][y+1] == '#'

def dfs(st, x, y):
    if (x == n-1 and y == m-1):
        return 1
    down, right = can_down(st, x, y), can_right(st, x, y)
    if (down and right):
        return 0
    if ((not down) and (not right)):
        return 0
    if (down):
        return dfs(st, x+1, y)
    return dfs(st, x, y+1)

if (dfs(st, 0, 0)):
    print("Possible")
else:
    print("Impossible");

Submission status: Wrong Answer

Solution code:
def read():
    return [int(x) for x in str.split(raw_input())]

n, m = read()
st = []

for i in range(n):
    st.append(raw_input())

def can_down(st, x, y):
    return x+1 < n and st[x+1][y] == '#'

def can_right(st, x, y):
    return y+1 < m and st[x][y+1] == '#'

def dfs(st, x, y):
    if (x == n-1 and y == m-1):
        return 1
    down, right = can_down(st, x, y), can_right(st, x, y)
    if (down and right):
        return 0
    if ((not down) and (not right)):
        return 0
    if (down):
        return dfs(st, x+1, y)
    return dfs(st, x, y+1)

if (dfs(st, 0, 0)):
    print("Yes")
else:
    print("No");

Submission status: Wrong Answer

Solution code:
import sys
H,W = [int(i) for i in input().split()]
A = [list(input().strip()) for j in range(H)]
print(A)

q = [(0,0)]
while q:
  h,w = q.pop()
  if (h,w) == (H-1,W-1):
    A[h][w] = '.'
    break
  for dh,dw in [(1,0),(0,1)]:
    nh,nw = h+dh,w+dw
    if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '#':
      q.append((nh,nw))
      A[h][w] = '.'
      break
  else:
    print('Impossible')
    sys.exit()
print(A)

for h in range(H):
  for w in range(W):
    if A[h][w] == '#':
      print('Impossible')
      sys.exit()
print('Possible')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

# AtCoder Grand Contest
# Problem A


def depth_first_search(current_x: int, current_y: int) -> str:
    board[current_x][current_y] = '.'
    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]

    for x, y in zip(dx, dy):
        next_x = current_x + x
        next_y = current_y + y

        if (0 <= next_x < h) and (0 <= next_y < w) and board[next_x][next_y] == '#':
            if (x == -1) or (y == -1):
                global count
                count += 1

            depth_first_search(next_x, next_y)


if __name__ == '__main__':
    h, w = list(map(int, input().split()))
    board = [list(map(str, list(input()))) for i in range(h)]
    count = 0

    for x in range(h):
        for y in range(w):
            if board[x][y] == '#':
                depth_first_search(x, y)

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

Submission status: Wrong Answer

Solution code:
h,w=[int(i) for i in input().split()]
s=0
l=0
for i in range(h):
  sf=True
  lf=False
  a=list(input().strip())
  for j in range(w):
    if a[j]=="#" and sf==True:
      s=j
      sf=False
      if s!=l and i!=0:
        print("Impossible")
        exit()
    if a[j]=="#" and lf==True:
      print("Impossible")
      exit()
    if a[j]=="." and sf==False and lf==False:
      l=j-1
      lf=True
else:
  print("Possible")

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
a = ['.'*(W+2)]
for i in range(H):
    a.append('.'+input()+'.')
a.append('.'*(W+2))
x, y = 1, 1
d = [0, 1], [1, 0]

#右と下だけで行けるところまで行く
while True:
    #現在地を探索済みにする
    a[x] = a[x][:y] + '*' + a[x][y+1:]
    
    if [x, y] == [H, W]:
        break
    
    #右か下に進む
    for d_i in d:
        if a[x+d_i[0]][y+d_i[1]]=='#':
            x, y = x+d_i[0], y+d_i[1]
            break
    #行き止まりなら終了
    else:
        break
    
    
#探索結果を確認
end = 0
for r_i in a:
    for j in r_i:
        if j == '#':
            print('Impossible')
            end = 0
            break
    if end == 1:
        break
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
from queue import Queue

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

B = []
for i in range(H):
    B_sub = []
    for j in input():
        if j == "#":B_sub.append(5)
        else: B_sub.append(-1)
    B.append(B_sub)
    
qy,qx = Queue(),Queue()
qy.put(0)
qx.put(0)

isok = True
while(isok):
    if qy.empty() and qx.empty(): isok = False
    else:
        y,x = qy.get(),qx.get()
        if y==0 and x==0:
            if B[y][x]==-1: isok = False
            else: B[y][x] = 0
        elif y==H-1 and x==W-1: break #おめでとう

        if y<H-1 and B[y+1][x]==5:
            B[y+1][x] = 0
            qy.put(y+1)
            qx.put(x)
            if 5 in B[y]: isok = False
        elif x<W-1 and B[y][x+1]==5:
            B[y][x+1] = 0
            qy.put(y)
            qx.put(x+1)
            
if isok:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
from queue import Queue

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

B = []
for i in range(H):
    B_sub = []
    for j in input():
        if j == "#":B_sub.append(5)
        else: B_sub.append(-1)
    B.append(B_sub)
    
qy,qx = Queue(),Queue()
qy.put(0)
qx.put(0)

isok = True
while(True):
    if qy.empty() and qx.empty():
        isok = False
        break
    else:
        y,x = qy.get(),qx.get()
        if y==0 and x==0: B[y][x] = 0
        elif y==H-1 and x==W-1: break

        if y<H-1 and B[y+1][x]==5:
            B[y+1][x] = 0
            qy.put(y+1)
            qx.put(x)
            if 5 in B[y]:
                isok = False
                break
        elif x<W-1 and B[y][x+1]==5:
            B[y][x+1] = 0
            qy.put(y)
            qx.put(x+1)
            
if isok:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
h,m = list(map(int,input().split()))

count = h+m

for i in range(h):
    b =(list(input()))
    count -= b.count('#')
if count == 1:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [input() for _ in range(H)]
now = (0,0)
if A[0][0] != "#":
    print("Impossible")
    exit()
count = 0
while now != (H-1,W-1):
    if len(now) == 0:
        print("Impossible")
        exit()
    now_next = ()
    if now[0] < H-1 and A[now[0]+1][now[1]] == "#":
        now_next = (now[0]+1,now[1])
        count += 1
    if now[1] < W-1 and A[now[0]][now[1]+1] == "#":
        now_next = (now[0],now[1]+1)
        count += 1
    now = now_next
if count == W + H - 2:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
cou = 0
co = 0
for i in range(h):
    lis = str(input())
    lis = lis + "0"
    if cou == w-1:
        w -= 1
        if lis[min(cou,w-1)] == "#":
            w += 1
            for m in range(w):
                if lis[m] == "#":
                    co += 1
            while lis[cou] == "#" and cou < w:
                cou += 1
            if i == h -1 and cou == w and co == h +(w - 1):
                print("Possible")
                exit()
        else:
            print("Impossible")
            exit()
print("Impossible")

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
cou = 0
co = 0
for i in range(h):
    lis = str(input())
    lis = lis + "0"
    if lis[min(cou,w-1)] == "#":
        for m in range(w):
            if lis[m] == "#":
                co += 1
        while lis[cou] == "#" and cou < w:
            cou += 1
        if i == h -1 and cou == w and co == h +(w - 1):
            print("Possible")
            exit()
    else:
        print("Impossible")
        exit()
print("Impossible")

Submission status: Wrong Answer

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

def solve():
    i = j = 0
    while (i,j) != (H-1,W-1):
        if i == H-1:
            j += 1
            if src[i][j] == '.': return False
        elif j == W-1:
            i += 1
            if src[i][j] == '.': return False
        else:
            if src[i+1][j] == src[i][j+1]: return False
            if src[i+1][j] == '#':
                i += 1
            else:
                j += 1
    return True

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

Submission status: Wrong Answer

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

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


def dfs(i, j):
    if i == H - 1 and j == W - 1:
        return not ((i > 1 and A[i - 1][j] == '#') and (j > 1 and A[i][j - 1] == '#'))
    else:
        ret = False
        if i < H - 1 and A[i + 1][j] == '#' and j < W - 1 and A[i][j + 1] == '#':
            return False
        if i < H - 1 and A[i + 1][j] == '#':
            ret |= dfs(i + 1, j)
        if j < W - 1 and A[i][j + 1] == '#':
            ret |= dfs(i, j + 1)
        return ret


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

Submission status: Wrong Answer

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

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


def dfs(i, j):
    if i == H - 1 and j == W - 1:
        return not (i > 1 and A[i - 1][j] == '#' and j > 1 and A[i - 1][j] == '#')
    else:
        ret = False
        if i < H - 1 and A[i + 1][j] == '#' and j < W - 1 and A[i][j + 1] == '#':
            return False
        if i < H - 1 and A[i + 1][j] == '#':
            ret |= dfs(i + 1, j)
        if j < W - 1 and A[i][j + 1] == '#':
            ret |= dfs(i, j + 1)
        return ret


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

Submission status: Wrong Answer

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

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

def dfs(i, j):
    if i == H - 1 and j == W - 1:
        return True
    else:
        ret = False
        if i < H - 1 and A[i + 1][j] == '#' and j < W - 1 and A[i][j + 1] == '#':
            return False
        if i < H - 1 and A[i + 1][j] == '#':
            ret |= dfs(i + 1, j)
        if j < W - 1 and A[i][j + 1] == '#':
            ret |= dfs(i, j + 1)
        return ret


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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool:
    return 0 <= y < H and 0 <= x < W


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

    used = set()
    now = (0, 0)
    used.add(now)
    while True:
        root = []
        for i in range(4):
            ny, nx = now[0] + dy[i], now[1] + dx[i]
            if inside(ny, nx, H, W) and field[ny][nx] == "#" and (ny, nx) not in used:
                root.append(i)

        if len(root) > 1 or 2 in root or 3 in root:
            print("Impossible")
            return

        for i in range(4):
            ny, nx = now[0] + dy[i], now[1] + dx[i]
            if inside(ny, nx, H, W) and field[ny][nx] == "#" and (ny, nx) not in used:
                now = (ny, nx)
                used.add(now)

        if now == (H - 1, W - 1):
            print("Possible")
            return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def solve(h, w, a):
    b = []
    b += [ '.' * (w + 2) ]
    b += [ '.' + row + '.' for row in a ]
    b += [ '.' * (w + 2) ]
    y, x = 1, 1
    while (y, x) != (h, w):
        if b[y - 1][x] == b[y][x - 1] == '#':
            return False
        if b[y + 1][x] == b[y][x + 1] == '#':
            return False
        if b[y + 1][x] == '#':
            y += 1
        elif b[y][x + 1] == '#':
            x += 1
        else:
            return False
    return True
h, w = map(int, input().split())
a = [ input() for _ in range(h) ]
print(['Impossible', 'Possible'][solve(h, w, a)])

Submission status: Wrong Answer

Solution code:
import sys


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

valid = True
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
for y in range(H):
    for x in range(W):
        if m[y][x] != '#':
            continue
        cnt = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and \
               0 <= ny and ny < H and m[ny][nx] == '#':
                cnt += 1
        if cnt >= 3:
            valid = False
            print("Impossible")
            sys.exit()


def rec(x, y):
    if x == W - 1 and y == H - 1:
        return True

    if m[y][x] != '#':
        return False
    dx = [0, 1]
    dy = [1, 0]

    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < W and \
           0 <= ny and ny < H:
            ret = rec(nx, ny)
            if ret:
                return ret
    return False


if rec(0, 0):
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys


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

valid = True
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
for y in range(H):
    for x in range(W):
        if m[y][x] != '#':
            continue
        cnt = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and \
               0 <= ny and ny < H and m[ny][nx] == '#':
                cnt += 1
        if cnt >= 3:
            valid = False
            print("Impossible")
            sys.exit()


def rec(x, y):
    if x == W - 1 and y == H - 1:
        return True

    if m[y][x] != '#':
        return False
    dx = [0, 1]
    dy = [1, 0]

    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < W and \
           0 <= ny and ny < H and m[ny][nx] == '#':
            ret = rec(nx, ny)
            if ret:
                return ret
    return False


if rec(0, 0):
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys


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

valid = True
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
for y in range(H):
    for x in range(W):
        if m[y][x] != '#':
            continue
        cnt = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and \
               0 <= ny and ny < H and m[ny][nx] == '#':
                cnt += 1
        if cnt >= 3:
            valid = False
            print("Impossible")
            sys.exit()
print("Possible")

Submission status: Wrong Answer

Solution code:
h,w = map(int, raw_input().split())
m = [raw_input() for _ in range(h)]
possible = True
for y in range(h):
    for x in range(w):
        if y == h-1 and x == w-1:
            break
        if m[y][x] == '#':
            c = 0
            if y < h-1 and m[y+1][x] == '#':
                c += 1
            if x < w-1 and m[y][x+1] == '#':
                c += 1
            if c != 1:
                possible = False
                break
    if not possible:
        break
if possible:
    print 'Possible'
else:
    print 'Impossible'

Submission status: Wrong Answer

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

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

def check(y, x):
    cnt = 0
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if (ny < 0) or (ny >= h) or (nx < 0) or (nx >= w):
            continue
        if a[ny][nx] == '#':
            cnt+=1
    if cnt >= 3:
        return 1;
    else:
        return 0;

def dfs(y, x):
    if (y >= h) or (x >= w):
        return 0
    if a[y][x] == '.':
        return 0
    if (y == h - 1) and (x == w - 1):
        return 1

    return dfs(y + 1, x) or dfs(y, x + 1)

ans = "Possible"
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            if check(i,j):
                ans = "Impossible"

if not dfs(0, 0):
    ans = "Impossible"

print (ans)

Submission status: Wrong Answer

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

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

def check(y, x):
    for i in range(4):
        cnt = 0
        ny = y + dy[i]
        nx = x + dx[i]
        if (ny < 0) or (ny >= h) or (nx < 0) or (nx >= w):
            continue
        if a[ny][nx] == '#':
            cnt+=1
    if cnt >= 3:
        return 1;
    else:
        return 0;

def dfs(y, x):
    if (y >= h) or (x >= w):
        return 0
    if a[y][x] == '.':
        return 0
    if (y == h - 1) and (x == w - 1):
        return 1

    return dfs(y + 1, x) or dfs(y, x + 1)

ans = "Possible"
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            if check(i,j):
                ans = "Impossible"

if not dfs(0, 0):
    ans = "Impossible"

print (ans)

Submission status: Wrong Answer

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

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

def check(y, x):
    for i in range(4):
        cnt = 0
        ny = y + dy[i]
        nx = x + dx[i]
        if (ny < 0) or (ny >= h) or (nx < 0) or (nx >= w):
            continue
        if a[ny][nx] == '#':
            cnt+=1
    if cnt >= 3:
        return 1;
    else:
        return 0;

def dfs(y, x):
    if a[y][x] == '#':
        return 0
    if (y == h - 1) and (x == w - 1):
        return 1

    dfs(y + 1, x)
    dfs(y, x + 1)
    return 0

ans = "Possible"
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            if check(i,j):
                ans = "Inpossible"

if not dfs(0, 0):
    ans = "Inpossible"

print (ans)

Submission status: Wrong Answer

Solution code:
import copy
h,w=map(int,input().split())

def fun(aa,x,y):
    a=copy.deepcopy(aa)

    if h<=y or w<=x:
        return False

    if y==h-1 and x==w-1:
        count = 0
        for i in a:
            count += i.count('#')
        if count==1:
            return True
        else:
            return False

    if a[y][x]!="#":
        return False

    a[y][x]="."

    if fun(a,x+1,y) or fun(a,x,y+1):
        return True

    return False

a=[["" for i in range(w)] for j in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        a[i][j]=s[j]

Submission status: Wrong Answer

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

def fun(a,x,y):

    if h<=y or w<=x:
        return False

    if y==h-1 and x==w-1:
        count = 0
        for i in a:
            count += i.count('#')
        if count==1:
            return True
        else:
            return False

    if a[y][x]!="#":
        return False

    a[y][x]="."

    if fun(a,x+1,y) or fun(a,x,y+1):
        return True

    return False

a=[["" for i in range(w)] for j in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        a[i][j]=s[j]



print("Possible" if fun(a,0,0) else "Impossible")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def nextcheck(l, i, j, h, w):
    if (i == h)and(j == w):
        print "Possible"
        return ""

    status = [0,0] #[under , right]
    if i < h:
        if l[i+1][j] == "#":
            status[0] += 1
    if j < w:
        if l[i][j+1] == "#":
            status[1] += 1
    if (i != 0) and (j != 0):
        if (l[i-1][j] == "#") and (l[i][j-1] == "#"):
            print "Impossible"

    if (status == [0,0]) or (status == [1,1]):
        print "Impossible"
    elif status == [1,0]:
        nextcheck(l,i+1,j,h,w)
    elif status == [0,1]:
        nextcheck(l,i,j+1,h,w)
    else:
        print "Impossible"


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

for i in range(1,h+1):
    l.append(map(str, raw_input()))
nextcheck(l, 0, 0, h-1, w-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def nextcheck(l, i, j, h, w):
    if (i == h)and(j == w):
        print "Possible"
        return ""

    status = [0,0] #[under , right]
    if i < h:
        if l[i+1][j] == "#":
            status[0] += 1
    if j < w:
        if l[i][j+1] == "#":
            status[1] += 1

    if (status == [0,0]) or (status == [1,1]):
        print "Impossible"
    elif status == [1,0]:
        nextcheck(l,i+1,j,h,w)
    elif status == [0,1]:
        nextcheck(l,i,j+1,h,w)
    else:
        print "Impossible"


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

for i in range(1,h+1):
    l.append(map(str, raw_input()))
nextcheck(l, 0, 0, h-1, w-1)

Submission status: Wrong Answer

Solution code:
H,W = map(int,raw_input().split())
sh = 0
judge = 0
for i in range(H):
    if judge == 1:
        break
    A = list(raw_input())
    if A.count("#") == 0:
        print "Impossible"
        break
    for j in range(W):
        if A[j] == '#':
            if j - sh > 2:
                print "Impossible"
                judge = 1
                break
            else:
                 sh = j
    if i == H-1:
        print "Possible"

Submission status: Wrong Answer

Solution code:
import sys
 
H, W = map(int, input().split())
 
matrix = []
for i in range(H):
	row = sys.stdin.readline()
	matrix.append(row)
	
x=0
y=0
strResult="Possible"
while((x<W) & (y<H-1)):
	if ((x<W-1) & (matrix[y][x+1] == '#')):
		x += 1
	elif ((x>0) & (matrix[y+1][x-1] == '#')):
		strResult = "Impossible"
		break
	elif ((x>0) & (matrix[y][x-1] == '#') & (y>0) & (matrix[y-1][x] == '#')):
		strResult = "Impossible"
		break
	elif matrix[y+1][x] == '.':
		strResult = "Impossible"
		break
	else:
		y += 1
		if y == H-1:
			for x2 in range(x,W):
				if matrix[H-1][x2] == '.':
					strResult = "Impossible"
					break
	
			
print (strResult)

Submission status: Wrong Answer

Solution code:
h,w = (int(i) for i in input().split())
#print("h w:",h,w)
map_data = [list(input()) for j in range(h)]
map_step = [[0 for i in range(w)] for j in range(h)]
def peek_around(map_data,x,y):
#    print("peek_around {},{}".format(x,y))
    count = 0
    result = []
    for i in range(-1,2,1):
        for j in range(-1,2,1):
            if not i*j == 0:
                continue
#            print("  i,j",i,j)
#            print("  x+i,y+j",x+i,y+j)
            if (0 <= x+i and x+i < h)  and (0 <= y+j and y+j < w):
#                print("checking map_data[{}][{}]".format(x+i,y+j))
                if map_data[x+i][y+j] == "#":
                    result.append([x+i,y+j]) 
                    count += 1
    return count, result
                

g_x = h-1
g_y = w-1
for i in range(g_x,-1,-1):
    for j in range(g_y,-1,-1):
#        print("i,j",i,j)
        if map_data[i][j] == "#":
            steps = map_step[i][j]
            count, result = peek_around(map_data,i,j)
            for element in result:
                x = element[0]
                y = element[1]
                if map_step[x][y] == 0 or map_step[x][y] > steps:
                    map_step[x][y] = steps+1
#print("map_data:",map_data)
#print("map_step:",map_step)
if map_step[0][0] == h+w-2:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
h,w=[int(x) for x in input().split()]
a=[]
for i in range(h):
    a.append(list(input()))

s=0
for i in range(h):
    for j in range(s):
        if a[i][j]=="#":
            print("Impossible")
            sys.exit()
    for j in range(s,w):
        s=j
        if a[i][j]==".":
            s=j-1
            break
print("Possible")

Submission status: Wrong Answer

Solution code:
def dfs(l,x,y):
    
    if x+1 is w and y+1 is h:
        return l
    
    #right
    if w > x+1:
        if "#" is l[y][x+1]:

            l2 = list(l)
            l2[y][x+1] = "."

            return dfs(l2,x+1,y)

    #down
    if h > y+1:
        if "#" is l[y+1][x]:
            l3 = list(l)
            l3[y+1][x]= "."
            return  dfs(l3,x,y+1)



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


l = []
for i in range(h):
    l.append(list(raw_input()))

# print l
l[0][0] = "."
l2 = dfs(l,0,0)
# print l2
if l2:
    if "#" in [x for sublist in l2 for x in sublist]:
        print "Impossible"
    else:
        "Possible"
else:
    print "Impossible"

Submission status: Wrong Answer

Solution code:
import sys
 
H, W = map(int, input().split())
 
matrix = []
for i in range(H):
	row = sys.stdin.readline()
	matrix.append(row)
	
x=0
y=0
strResult="Possible"
while((x<W) & (y<H-1)):
	if ((x<W-1) & (matrix[y][x+1] == '#')):
		x += 1
	elif ((x>0) & (matrix[y+1][x-1] == '#')):
		strResult = "Impossible"
		break
	elif matrix[y+1][x] == '.':
		strResult = "Impossible"
		break
	else:
		y += 1
		if y == H-1:
			for x2 in range(x,W):
				if matrix[H-1][x2] == '.':
					strResult = "Impossible"
					break
	
			
print (strResult)

Submission status: Wrong Answer

Solution code:
import sys
 
H, W = map(int, input().split())
 
matrix = []
for i in range(H):
	row = sys.stdin.readline()
	matrix.append(row)
	
x=0
y=0
strResult="Possible"
while((x<W) & (y<H-1)):
	if ((x<W-1) & (matrix[y][x+1] == '#')):
		x += 1
	elif ((x>0) & (matrix[y+1][x-1] == '#')):
		strResult = "Impossible"
		break
	elif matrix[y+1][x] == ',':
		strResult = "Impossible"
		break
	else:
		y += 1
		if y == H-1:
			for x2 in range(x,W):
				if matrix[H-1][x2] == '.':
					strResult = "Impossible"
					break
	
			
print (strResult)

Submission status: Wrong Answer

Solution code:
import sys
h,w=[int(x) for x in input().split()]
a=[]
for i in range(h):
    a.append(list(input()))

s=0
for i in range(h):
    for j in range(s):
        if a[i][j]=="#":
            print("Impossible")
            sys.exit()
    for j in range(s,w):
        s=j-1
        if a[i][j]==".":
            break
print("Possible")

Submission status: Wrong Answer

Solution code:
def dfs(l,x,y):
    l[y][x] = "."
    
    if x+1 is w and y+1 is h:
        return l
    
    #right
    if w > x+1:
         if "#" is l[y][x+1]:
            l2 = list(l)
            return dfs(l2,x+1,y)

    #down
    if h > y+1:
         if "#" is l[y+1][x]:
            l3 = list(l)
            return  dfs(l3,x,y+1)



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


l = []
for i in range(h):
    l.append(list(raw_input()))

# print l

l2 = dfs(l,0,0)
# print l2
if l2:
    if "#" in [x for sublist in l2 for x in sublist]:
        print "Impossible"
    else:
        "Possible"
else:
    print "Impossible"