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) ]

(x, y) = (0, 0)
while y < H-1 and x < W-1:
    A[y][x] = '.'
    if (y>0 and A[y-1][x]=='#') or (x>0 and A[y][x-1]=='#'):
        print('Impossible')
        exit()

    if A[y+1][x] == '#':
        if A[y][x+1] == '#':
            print('Impossible')
            exit()
        else:
            y = y+1
    else:
        if A[y+1][x] == '#':
            print('Impossible')
            exit()
        else:
            x = x+1

print('Possible')

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split());print("P"*(open(0).read().count("#")==h+w-1)or"Imp"+"ossible")

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split());print("Imp"*(open(0).read().count("#")==h+w-1)or"P"+"ossible")

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split());print("IPmopsossisbilbel e"[open(0).read().count("#")==h+w-1::2])

Submission status: Wrong Answer

Solution code:
# 最短ルートでいける、左上開始、右上終了ゆえに#の数数えればいけるぞ
H, W = map(int, input().split(" "))
A = [input() for _ in range(H)]

print(["Imbossible", "Possible"]["".join(A).count("#")==H+W-1])

Submission status: Wrong Answer

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

all_ads = [(0, 1), (1, 0), (0, -1), (-1, 0)]
can_moves = [(0, 1), (1, 0)]

def dfs(this_pos):
    this_x, this_y = this_pos

    routes = set()
    for ad_x, ad_y in all_ads:
        x, y = pos = this_x+ad_x, this_y+ad_y
        if not(0<=x<W and 0<=y<H):
            continue
        if A[y][x] == ".":
            continue
        routes.add(pos)
    # print(routes)
    if len(routes) >= 2:
        return False
    
    for ad_x, ad_y in can_moves:
        x, y = pos = this_x+ad_x, this_y+ad_y
        if pos not in routes:
            continue
        A[y][x] = "."
        res = dfs(pos)
        if res == False:
            return False
    
    return True
        
A[0][0] = "."

if dfs((0, 0)) and A[-1][-1] == ".":
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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

ads = {(0, 1), (1, 0), (0, -1), (-1, 0)}
can_moves = {(0, 1), (1, 0)}


def dfs(this_pos):
    this_x, this_y = this_pos

    routes = set()
    for ad in ads:
        ad_x, ad_y = ad
        x, y = pos = this_x+ad_x, this_y+ad_y
        if not (0 <= x < W and 0<= y < H):
            continue
        if A[y][x] == ".":
            continue
        routes.add((pos, ad))
    # print(routes, A)

    if len(routes) >= 2:
        return False
    for route in [route for route, ad in routes if ad in can_moves]:
        x, y = route
        A[y][x] = "."
        if dfs(route) == False:
            return False

    return True

A[0][0] = "."

res = dfs((0, 0))

if res and A[-1][-1] == ".":
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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

ads = [(0, 1), (1, 0), (0, -1), (-1, 0)]
can_moves = {(0, 1), (1, 0)}

def dfs(this_pos):
    this_x, this_y = this_pos

    count = 0
    for ad in ads:
        ad_x, ad_y = ad
        x, y = pos = this_x+ad_x, this_y+ad_y
        if not (0 <= x < W and 0<= y < H):
            continue
        if A[y][x] == ".":
            continue
        A[y][x] = "."
        dfs(pos)
        count += 1
        if count >= 2:
            print("Impossible")
            exit()

dfs((0, 0))

if A[-1][-1] == ".":
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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

ads = [(0, 1), (1, 0), (0, -1), (-1, 0)]
can_moves = {(0, 1), (1, 0)}

def dfs(this_pos):
    this_x, this_y = this_pos
    A[this_y][this_x] = "."

    routes = []
    for ad_x, ad_y in ads:
        x, y = pos = this_x+ad_x, this_y+ad_y
        if not (0 <= x < W and 0 <= y < H):
            continue
        if A[y][x] == ".":
            continue
        routes.append((pos, (ad_x, ad_y)))
    # print(routes)
    if len(routes) > 1:
        print("Impossible")
        exit()
    for route, _ in filter((lambda x: x[1] in can_moves), routes):
        dfs(route)

dfs((0, 0))

# print("A")

if A[-1][-1] == ".":
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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

ads = [(0, 1), (1, 0)]

def dfs(this_pos):
    this_x, this_y = this_pos
    A[this_y][this_x] = "."

    routes = []
    for ad_x, ad_y in ads:
        x, y = pos = this_x+ad_x, this_y+ad_y
        if not (0 <= x < W and 0 <= y < H):
            continue
        if A[y][x] == ".":
            continue
        routes.append(pos)
    if len(routes) == 2:
        print("Impossible")
        exit()
    for route in routes:
        dfs(route)

dfs((0, 0))

if A[-1][-1] == ".":
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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

ads = [(0, 1), (1, 0)]

def dfs(this_pos):
    this_x, this_y = this_pos
    A[this_y][this_x] = "."

    for ad_x, ad_y in ads:
        x, y = pos = this_x+ad_x, this_y+ad_y
        if not (0 <= x < W and 0 <= y < H):
            continue
        if A[y][x] == ".":
            continue
        dfs(pos)

dfs((0, 0))

if A[-1][-1] == ".":
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
h,w = (int(i) for i in input().split())
a = []
for i in range(h):
  a.append(input())
queue = [(0,0)]
check = []
if a[0][0] == '.':
 print('Impossible')
 exit()
while queue != []:
 i,j = queue[0]
 queue.pop(0)
 if not (i,j) in check:
  if i+1 < h:
   if a[i+1][j] =='#':
    queue.append((i+1,j))
  if j+1 < w: 
   if a[i][j+1] =='#':
    queue.append((i,j+1))
  check.append((i,j))
  if i+1 < h and j+1 < w: 
    if a[i+1][j] =='#' and  a[i][j+1] =='#':
      break
  if queue != []:
   if queue[0] == (h-1,w-1) and a[h-1][w-1] == '#':
    print('Possible')
    exit()
print('Impossible')

Submission status: Wrong Answer

Solution code:
h,w = (int(i) for i in input().split())
a = []
for i in range(h):
  a.append(input())
queue = [(0,0)]
check = []
while queue != []:
 i,j = queue[0]
 queue.pop(0)
 if not (i,j) in check:
  if i+1 < h:
   if a[i+1][j] =='#':
    queue.append((i+1,j))
  if j+1 < w: 
   if a[i][j+1] =='#':
    queue.append((i,j+1))
  check.append((i,j))
  if i+1 < h and j+1 < w: 
    if a[i+1][j] =='#' and  a[i][j+1] =='#':
      break
  if queue != []:
   if queue[0] == (h-1,w-1) and a[h-1][w-1] == '#':
    print('Possible')
    exit()
print('Impossible')

Submission status: Wrong Answer

Solution code:

from collections import deque
H, W = map(int, input().split())
sy,sx = 1,1
gy,gx = H,W
sy-=1
sx-=1
gy-=1
gx-=1
con = [[1,0],[0,1],[-1,0],[0,-1]]
m=[]
d = [[0]*W for _ in range(H)]
for i in range(H):
    a= input()
    m.append(a)
q = deque()
q.append((sy,sx))
d[sy][sx] = 1
s = 0
while len(q)>0:
    y,x = q.popleft()
    if y == gy and x == gx:
        break
    for dx,dy in con:
        if  y+dy>=0 and x+dx >= 0 and y+dy < H and x+dx < W:
            if d[y+dy][x+dx] == 0 and m[y+dy][x+dx] =="#":
                q.append((y+dy,x+dx))
                d[y+dy][x+dx]+=d[y][x]+1
                if dx==-1 or dy == -1:
                    s = 1


if H+W < d[gy][gx] or s == 1:
    print("Impossible")
else:print("Possible")

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sy,sx = 1,1
gy,gx = H,W
sy-=1
sx-=1
gy-=1
gx-=1
con = [[1,0],[0,1],[-1,0],[0,-1]]
m=[]
d = [[0]*W for _ in range(H)]
for i in range(H):
    a= input()
    m.append(a)
q = deque()
q.append((sy,sx))
s = 0
while len(q)>0:
    y,x = q.popleft()
    if y == gy and x == gx:
        break
    for dx,dy in con:
        if  y+dy>=0 and x+dx >= 0 and y+dy < H and x+dx < W:
            if d[y+dy][x+dx] == 0 and m[y+dy][x+dx] =="#":
                q.append((y+dy,x+dx))
                d[y+dy][x+dx]+=d[y][x]+1
                if dx==-1 or dy == -1:
                    s = 1


if H+W < d[gy][gx] or s == 1:
    print("Impossible")
else:print("Possible")

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
sy,sx = 1,1
gy,gx = H,W
sy-=1
sx-=1
gy-=1
gx-=1
con = [[1,0],[0,1],[-1,0],[0,-1]]
m=[]
d = [[0]*W for _ in range(H)]
for i in range(H):
    a= input()
    m.append(a)
q = deque()
q.append((sy,sx))
while len(q)>0:
    y,x = q.popleft()
    if y == gy and x == gx:
        break
    for dx,dy in con:
        if  y+dy>=0 and x+dx >= 0 and y+dy < H and x+dx < W:
            if d[y+dy][x+dx] == 0 and m[y+dy][x+dx] =="#":
                q.append((y+dy,x+dx))
                d[y+dy][x+dx]+=d[y][x]+1


if H+W < d[gy][gx]:
    print("Impossible")
else:print("Possible")

Submission status: Wrong Answer

Solution code:
def dask(x,y):
  if(a[x][y]=="."):
    return [0,0,False]
  if(a[x+1][y]=="#"):
    for i in range(w):
      if(i>y and a[x][i]=="#"):
        return [0,0,False]
    return [x+1,y,True]
  if(a[x][y+1]=="#"):
    for i in range(h):
      if(i>y and a[i][y]=="#"):
        return [0,0,False]
    return [x,y+1,True]
  return [0,0,False]
h,w=map(int,input().split())
a=[input()+"." for _ in[0]*h]+["."*(w+1)]
x=0
y=0
fl=True
while(fl and (x<h-1 or y<w-1)):
  x,y,fl=dask(x,y)
print("Possible" if fl else "Impossible")

Submission status: Wrong Answer

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

A = []

for i in range(H):
    tmp = input()
    A.append(tmp)
    
f = 1
now_H = 0
now_W = 0

while f==1:
    if A[now_H][now_W]=='.':
        f=-1
    elif now_H==H-1 and now_W==W-1:
        f = 2
    else:
        k = 0
        if now_H<H-1 and A[now_H+1][now_W]=='#':
            k = k + 1
            next_H = now_H+1
            next_W = now_W          
        if now_W<W-1 and A[now_H][now_W+1]=='#':
            k = k + 1
            next_H = now_H
            next_W = now_W+1
        if k==0 or k==2:
            f = -1
        else:
            now_H = next_H
            now_W = next_W
    
if f<0:
    print('Impossible')
else:
    print('Possible')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

y = 0
x = 0

goal_y = H - 1
goal_x = W - 1

counts = 0
for input in inputs:
    counts += input.count('#')

if counts != (H + W - 1):
    print('Impossible')
else:
    for i in range(H + W - 2):
        try:
            if inputs[y][x + 1] == '#':
                x = x + 1
            elif inputs[y + 1][x] == '#':
                y = y + 1
        except:
            pass
    print('Possible' if y == goal_y and x == goal_x else 'Impossible')

Submission status: Wrong Answer

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

x = 0
for y in range(H):
    if src[y][x] != '#':
        print('Impossible')
        exit()
    while x+1 < W and src[y][x+1] == '#':
        if y+1 < H and src[y+1][x] == '#':
            print('Impossible')
            exit()
        x += 1

print('Possible' if x == W-1 else 'Impossible')

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
field = [["."] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    a = list(input())
    for j in range(1,W+1):
        if a[j-1] == "#":
            field[i][j] = "#"
p_i,p_j = 1,1
while True:
    top = field[p_i - 1][p_j]
    right = field[p_i][p_j + 1]
    bottom = field[p_i + 1][p_j]
    left = field[p_i][p_j - 1]
    if (top,right,bottom,left) == (".","#",".","."):
        p_j += 1
    elif (top,right,bottom,left) == (".",".","#","."):
        p_i += 1
    else:
        ans = "Impossible"
        break
    if (p_i,p_j) == (H,W):
        ans = "Possible"
        break
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
field = [["."] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    a = list(input())
    for j in range(1,W+1):
        if a[j-1] == "#":
            field[i][j] = "#"
p_i,p_j = 1,1
while True:
    right = field[p_i][p_j + 1]
    bottom = field[p_i + 1][p_j]
    if right == "#" and bottom == ".":
        p_j += 1
    elif bottom == "#" and right == ".":
        p_i += 1
    else:
        ans = "Impossible"
        break
    if (p_i,p_j) == (H,W):
        ans = "Possible"
        break
print(ans)

Submission status: Wrong Answer

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

def solve():
    x, y = (1, 1)
    while (x, y) != (H, W):
        isOK_X = Ass[x + 1][y] == '#'
        isOK_Y = Ass[x][y + 1] == '#'
        if isOK_X == isOK_Y:
            print('Impossible')
            return
        if isOK_X:
            x += 1
        else:
            y += 1
    print('Possible')

solve()

Submission status: Wrong Answer

Solution code:
H, W, *A = open(0).read().split()
if A.count('#') == int(H) * int(W) - 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

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


def parse(x, y):
    A[x][y] = '.'
    cand_OK = []
    cand_NG = []
    if x < H - 1:
        cand_OK += [[x + 1, y]]
    if y < W - 1:
        cand_OK += [[x, y + 1]]
    if x > 0:
        cand_NG += [[x - 1, 1]]
    if y > 0:
        cand_NG += [[x, y - 1]]
    if x == H - 1 and y == W - 1:
        return True
    if any([A[i][j] == '#' for i, j in cand_NG]):
        return False
    if sum([A[i][j] == '#' for i, j in cand_OK]) == 2:
        return False
    if sum([A[i][j] == '.' for i, j in cand_OK]) == 2:
        return False
    for i, j in cand_OK:
        if A[i][j] == '#':
            return parse(i, j)


if parse(0, 0):
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

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


def parse(x, y):
    flag = False

    def parse_in(x, y):
        A[x][y] = '.'
        if x == H - 1 and y == W - 1:
            nonlocal flag
            flag = True
        if x + 1 < H and A[x + 1][y] == '#':
            parse_in(x + 1, y)
        if y + 1 < W and A[x][y + 1] == '#':
            parse_in(x, y + 1)

    parse_in(x, y)
    return flag


if parse(0, 0):
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

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

x = 0
y = 0

c = 0
a[0][0] = '.'
while x != w-1 or y != h-1:
    r = 0
    if x <= w-2:
        if a[y][x+1] == '#':
            r = 1
            a[y][x+1] = '.'
    if y <= h-2:
        if a[y+1][x] == '#':
            r += 2
            a[y+1][x] = '.'
    if x >= 1:
        if a[y][x-1] == '#':
            r = 0
    if y >= 1:
        if a[y-1][x] == '#':
            r = 0
    if r == 2:
        y += 1
    if r == 1:
        x += 1
    if x == w-1 and y == h-1:
        c = 1
    
    if r == 0 or r == 3:
        c = -1
        x = w-1
        y = h-1

    

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

Submission status: Wrong Answer

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

x = 0
y = 0

c = 0

while x != w-1 or y != h-1:
    r = 0
    if x <= w-2:
        if a[y][x+1] == '#':
            r = 1
    if y <= h-2:
        if a[y+1][x] == '#':
            r += 2
    if r == 2:
        y += 1
    if r == 1:
        x += 1
    if x == w-1 and y == h-1:
        c = 1
    
    if r == 0 or r == 3:
        c = -1
        x = w-1
        y = h-1

    

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

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
c = 0
for i in range(h):
    c += list(input()).count('#')
if c == h+w-1:
    print('Possible')
else:
    print('Imipossible')

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
h = 0
w = 0
flag = 0
ans = 0

L = []
for i in range(H) :
    L.append(input())

while flag == 0 :
    if h == (H-1) and w == (W-1) :
        ans = 1
        flag = 1
    else :
        if w == (W-1) :
            if L[h+1][w] == "#" :
                h += 1
            else :
                flag = 1
        elif h == (H-1) :
            if L[h][w+1] == "#" :
                w += 1
            else :
                flag = 1
        else :
            if L[h+1][w] == "#" and L[h][w+1] == "#" :
                flag = 1
            else :
                if L[h+1][w] == "#" :
                    h += 1
                elif L[h][w+1] == "#" :
                    w += 1
                else :
                    flag = 1
                
if ans == 1 :
    print("Possible")
else :
    print("Impossible")

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
h = 0
w = 0
flag = 0
ans = 0

L = []
for i in range(H) :
    L.append(input())

while flag == 0 :
    if h == (H-1) and w == (W-1) :
        ans = 1
        flag = 1
    else :
        if w == (W-1) :
            if L[h+1][w] == "#" :
                h += 1
            else :
                flag = 1
        elif h == (H-1) :
            if L[h][w+1] == "#" :
                w += 1
            else :
                flag = 1
        else :
            if L[h+1][w] == "#" and L[h][w+1] == "#" :
                flag = 1
            else :
                if L[h+1][w] == "#" :
                    h += 1
                elif L[h][w+1] == "#" :
                    w += 1
                else :
                    flag = 1
                
if ans == 1 :
    print("Possible")
else :
    print("Impposible")

Submission status: Wrong Answer

Solution code:
height, width = map(int, input().split())

arr = []

for i in range(height):
    s = input()
    a = []
    for j in range(width):
        if s[j] == '#':
            a.append(1)
        else:
            a.append(0)
    arr.append(a)
    
h = 0
w = 0
f = 1

if arr[0][0] == 0:
    h = height-1
    w = width-1
    f = 0

while h < height-1 or w < width-1:
    if h == height-1:
        if arr[h][w+1] == 0:
            f = 0
            break
        else:
            arr[h][w+1] = 0
            w += 1
    elif w == width-1:
        if arr[h+1][w] == 0:
            f = 0
            break
        else:
            arr[h+1][w] = 0
            h += 1
    else:
        if arr[h][w+1] == 0:
            if arr[h+1][w] == 0:
                f = 0
                break
            else:
                arr[h+1][w] = 0
                h += 1
        else:
            if arr[h+1][w] == 1:
                f = 0
                break
            else:
                arr[h][w+1] = 0
                w += 1


if f == 0:
    print('Impossible')
else:
    extra = 0
    for i in range(h):
        for j in range(w):
            extra += arr[i][j]
    if extra > 1:
        print('Impossible')
    else:
        print('Possible')

Submission status: Wrong Answer

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

result = []

for i in range(H):
    a = input()
    result.append(a)

possibility = True

for i in range(H):
   for j in range(W):
        if j != W-1 and i != H-1:
            if result[i][j] == "#" and result[i+1][j] == result[i][j] and result[i][j+1] == result[i][j]:
                possibility = False
if possibility:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
A = [input() for i in range(H)]
for i in range(1,H):
    for j in range(1,W):
        if A[i][j]=='#' and A[i-1][j]=='#' and A[i][j-1]=='#':
            print("Impossible")
            exit()

print("Possible")

Submission status: Wrong Answer

Solution code:
H, W = list(map(int, input().split()))
A = []

for i in range(H):
	A.append(list(input()))

judge = "Possible"
x = 0
y = 0
for i in range(H + W - 2):
	if x == W - 1:
		if A[y + 1][x] == "#":
			y += 1
		else:
			judge = "Impossible"
			break
	elif y == H - 1:
		if A[y][x + 1] == "#":
			x += 1
		else:
			judge = "Impossible"
			break

	else:
		if A[y + 1][x] == "#":
			if A[y][x + 1] == "#":
				judge = "Impossible"
				break
			else:
				y += 1
		else:
			if A[y][x + 1] == "#":
				x += 1
			else:
				judge = "Impossible"
				break

print(judge)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = []
for i in range(H):
  A.append(list(input()+ "."))

A.append(["."] * (W+1))
#print(A)

i, j = 0,0
while i <= H-1 and j <= W-1:
  if i == H-1 and j == W-1:
    break
  if A[i][j+1] == A[i+1][j]: # #/.
    print("Impossible")
    exit(0)
  elif A[i][j+1] == "#":
    j += 1
    continue
  elif A[i+1][j] == "#":
    i += 1
    continue
  else:
    exit(1)
  
print("Possible")

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
@lru_cache(maxsize=None)
def search(i,j):
  global s,h,w
  if i==h-1and j==w-1:return 1
  r=0
  if i<h-1and s[i+1][j]=='#':r|=search(i+1,j)
  elif j<w-1and s[i][j+1]=='#':r|=search(i,j+1)
  if i>0and s[i-1][j]=='#':r=0
  if j>0and s[i][j-1]=='#':r=0
  return r
h,w=map(int,input().split())
s=[input()for _ in[0]*h]
print(('P'*search(0,0)or'Imp')+'ossible')

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
@lru_cache(maxsize=None)
def search(i,j):
  global s,h,w
  if i==h-1and j==w-1:return 1
  r=0
  if i<h-1and s[i+1][j]=='#':r|=search(i+1,j)
  if j<w-1and s[i][j+1]=='#':r|=search(i,j+1)
  return r
h,w=map(int,input().split())
s=[input()for _ in[0]*h]
for i in range(h-1):
  for j in range(w-1):
    if (s[i][j:j+2]=='##')&(s[i+1][j:j+2]=='##'):
      print('Impossible')
      exit()
print(('P'*search(0,0)or'Imp')+'ossible')

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
@lru_cache(maxsize=None)
def search(i,j):
  global s,h,w
  if i==h-1and j==w-1:return 1
  r=0
  if i<h-1and s[i+1][j]=='#':r|=search(i+1,j)
  if j<w-1and s[i][j+1]=='#':r|=search(i,j+1)
  return r
h,w=map(int,input().split())
s=[input()for _ in[0]*h]
print(('P'*search(0,0)or'Imp')+'ossible')

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
@lru_cache(maxsize=None)
def search(i,j):
  global s,h,w
  if i==h-1and j==w-1:return 1
  r=0
  if i<h-2and s[i+1][j]=='#':r|=search(i+1,j)
  if j<w-2and s[i][j+1]=='#':r|=search(i,j+1)
  return r
h,w=map(int,input().split())
s=[input()for _ in[0]*h]
print('Im'*search(0,0)+'possible')

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
a = [list(input()) for i in range(H)]
j = 0
for i in range(H-1):
    if a[i+1][j] =="#" and a[i][j+1:].count("#")==0:
        pass
    elif a[i][j] =="#" and a[i][j+1] =="#" and a[i][j+2:].count("#")==0:
        j+=1
    else:
        print('Impossible')
        exit()
print("Possible")

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
a = [list(input()) for i in range(H)]
j = 0
for i in range(H-1):
    if a[i+1][j] =="#" and a[i].count("#")==1:
        pass
    elif a[i][j] =="#" and a[i][j+1] =="#" and a[i].count("#")==2:
        j+=1
    else:
        print('Impossible')
        exit()
print("Possible")

Submission status: Wrong Answer

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

def dfs(x, y):
    if x == w - 1 and y == h - 1:
        return True
    if 0 <= x < w and 0 <= y < h:
        if A[y][x] == '#':
            return dfs(x + 1, y) | dfs(x, y + 1)
    return False

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

Submission status: Wrong Answer

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

x,y = 0,0
while not (x==h-1 and y==w-1):
    s = a[x+1][y]=='#'
    t = a[x][y+1]=='#'
    if s+t!=1:
        print('Impossible')
        exit()
    elif s==1:
        x += 1
    elif t==1:
        y += 1
    else:
        print('Impossible')
        exit()

print('Possible')

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a = [input() for _ in range(h)]
x,y = 0,0
while x<h-1 or y<w-1:
    if x+1==h:
        if a[x][y+1]=='#':
            y += 1
        else:
            print('Impossible')
            exit()
    elif y+1==w:
        if a[x+1][y]=='#':
            x += 1
        else:
            print('Impossible')
            exit()
    else:
        s = a[x+1][y]=='#'
        t = a[x][y+1]=='#'
        if s+t!=1:
            print('Impossible')
            exit()
        else:
            if s==1:
                x += 1
            else:
                y += 1

print('Possible')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W = inpl()
MAP = [['.']*(W+2)]
for i in range(H):
	MAP.append(['.'] + list(input()) + ['.'])
MAP.append(['.']*(W+2))

x = y = 1
while x < W or y < H:
	ri = MAP[y][x+1]
	do = MAP[y+1][x]
	le = MAP[y][x-1]
	up = MAP[y-1][x]
	if ri == do or [ri,do,le,up].count('#')>2:
		print('Impossible')
		sys.exit()
	else:
		if ri == '#':
			x += 1
		else:
			y += 1

print('Possible')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W = inpl()
MAP = [['.']*(W+2)]
for i in range(H):
	MAP.append(['.'] + list(input()) + ['.'])
MAP.append(['.']*(W+2))

x = y = 1
if MAP[y][x] == '.' or MAP[H][W] == '.':
	print('Impossible')
	sys.exit()

while x < W or y < H:
	ri = MAP[y][x+1]
	do =  MAP[y+1][x]
	if ri == do:
		print('Impossible')
		sys.exit()
	else:
		if ri == '#':
			x += 1
		else:
			y += 1

print('Possible')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W = inpl()
MAP = [['.']*(W+2)]
for i in range(H):
	MAP.append(['.'] + list(input()) + ['.'])
MAP.append(['.']*(W+2))

x = y = 1
while x < W or y < H:
	ri = MAP[y][x+1]
	do =  MAP[y+1][x]
	if ri == do:
		print('Impossible')
		sys.exit()
	else:
		if ri == '#':
			x += 1
		else:
			y += 1

print('Possible')

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = []
for _ in range(h):
    a.append(input())
    
sharpnum = 0
for ai in a:
    sharpnum += ai.count("#")
     
if h != w:                   
    if sharpnum == max((2*w - 2), (2*h - 2)):
        print("Possible")
    else:
        print("Impossible")
        
else:
    if sharpnum == 2*h - 1:
        print("Possible")
    else:
        print("Impossible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = []
for _ in range(h):
    a.append(input())
    
sharpnum = 0
for ai in a:
    sharpnum += ai.count("#")
                         
if sharpnum == (2*w - 2):
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
H, W = [int(x) for x in input().split()]
A = [input() for i in range(0, H)]
i, j = 0, 0
H, W = H-1, W-1
moveX=[1,0,-1,0]
moveY=[0,1,0,-1]
while True:
    count=0
    for k in range(0,4):
        ii=i+moveX[k]
        jj=j+moveY[k]
        if 0<=ii and ii<=H and 0<=jj and jj<=W:
            if A[ii][jj]=='#':
                count+=1
    if count > 2:
        print("Impossible")
        break
    if i < H and A[i+1][j] == '#':
        i = i+1
        continue
    if j < W and A[i][j+1] == '#':
        j = j+1
        continue
    if i == H and j == W:
        print("Possible")
        break
    else:
        print("Impossible")
        break

Submission status: Wrong Answer

Solution code:
H, W = [int(x) for x in input().split()]
A = [input() for i in range(0, H)]
i, j = 0, 0
H, W = H-1, W-1
while True:
    if i < H and j < W:
        if A[i+1][j] == '#' and A[i][j+1] == '#':
            print("Impossible")
            break
    if i < H and A[i+1][j] == '#':
        i = i+1
        continue
    if j < W and A[i][j+1] == '#':
        j = j+1
        continue
    if i == H and j == W:
        print("Possible")
        break
    else:
        print("Impossible")
        break

Submission status: Wrong Answer

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

def solve(H, W, A):
    x, y = 0, 0
    while 1:
        if y == H - 1 and x == W - 1:
            return True
        if A[y][x] != "#":
            return False
        r = (x + 1) < W and A[y][x + 1] == "#"
        d = (y + 1) < H and A[y + 1][x] == "#"
        if r and d:
            return False
        if not r and not d:
            return False
        if r:
            x += 1
        if d:
            y += 1

result = solve(H, W, A)


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