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=0
y=0
flag=1
while True:
    if (x==W-1)and(y==H-1):
        try:
            if A[H-2][x]==A[y][W-2]:
                flag=0
        except:
            flag=1
        break
    elif (x==0)and(y==0):
        if (A[y+1][x]=="#")and(A[y][x+1]=="."):
            y=y+1
        elif (A[y][x+1] == "#") and (A[y+1][x] == "."):
            x=x+1
        else:
            flag=0
            break
    elif x==0:
        if (y!=H-1):
            if (A[y+1][x]=="#")and(A[y][x+1]=="."):
                y=y+1
            elif (A[y][x+1] == "#") and (A[y+1][x] == "."):
                x=x+1
            else:
                flag=0
                break
        else:
            if (A[y][x+1]=="#"):
                x=x+1
            else:
                flag=0
                break
    elif y==0:
        if (x!=W-1):
            if (A[y+1][x]=="#")and(A[y][x+1]=="."):
                y=y+1
            elif (A[y][x+1] == "#") and (A[y+1][x] == "."):
                x=x+1
            else:
                flag=0
                break
        else:
            if (A[y+1][x]=="#"):
                y=y+1
            else:
                flag=0
                break
    elif x==W-1:  #横端についた
        if (A[y+1][x]=="#")and(A[y+1][x-1]=="."):
            y=y+1
        else:
            flag=0
            break
    elif y==H-1:
        if (A[y][x+1] == "#")and(A[y-1][x+1]=="."):
            x=x+1
        else:
            flag=0
            break
    else:
        if (A[y+1][x]=="#")and(A[y][x+1]==".")and(A[y-1][x]==".")and(A[y][x-1]=="#"):
            y=y+1
        elif (A[y][x+1] == "#") and (A[y+1][x] == ".")and (A[y-1][x] == "#")and (A[y][x-1] == "."):
            x=x+1
        else:
            flag=0
            break
    #print(x,y)
if flag==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)]
x=0
y=0
flag=1
while True:
    if (x==W-1)and(y==H-1):
        try:
            if A[H-2][x]==A[y][W-2]:
                flag=0
        except:
            flag=1
        break
    elif (x==0)and(y==0):
        if (A[y+1][x]=="#")and(A[y][x+1]=="."):
            y=y+1
        elif (A[y][x+1] == "#") and (A[y+1][x] == "."):
            x=x+1
        else:
            flag=0
            break
    elif x==0:
        if (y!=H-1):
            if (A[y+1][x]=="#")and(A[y][x+1]=="."):
                y=y+1
            elif (A[y][x+1] == "#") and (A[y+1][x] == "."):
                x=x+1
            else:
                flag=0
                break
        else:
            if (A[y][x+1]=="#"):
                x=x+1
            else:
                flag=0
                break
    elif y==0:
        if (x!=W-1):
            if (A[y+1][x]=="#")and(A[y][x+1]=="."):
                y=y+1
            elif (A[y][x+1] == "#") and (A[y+1][x] == "."):
                x=x+1
            else:
                flag=0
                break
        else:
            if (A[y+1][x]=="#"):
                y=y+1
            else:
                flag=0
                break
    elif x==W-1:  #横端についた
        if (A[y+1][x]=="#")and(A[y+1][x-1]=="."):
            y=y+1
        else:
            flag=0
            break
    elif y==H-1:
        if (A[y][x+1] == "#")and(A[y-1][x+1]=="."):
            x=x+1
        else:
            flag=0
            break
    else:
        if (A[y+1][x]=="#")and(A[y][x+1]==".")and(A[y-1][x]==".")and(A[y][x-1]=="."):
            y=y+1
        elif (A[y][x+1] == "#") and (A[y+1][x] == ".")and (A[y-1][x] == ".")and (A[y][x-1] == "."):
            x=x+1
        else:
            flag=0
            break
    #print(x,y)
if flag==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)]
x=0
y=0
flag=1
while True:
    if (x==W-1)and(y==H-1):
        try:
            if A[H-2][x]==A[y][W-2]:
                flag=0
        except:
            flag=1
        break
    if x==W-1:  #横端についた
        if (A[y+1][x]=="#")and(A[y+1][x-1]=="."):
            y=y+1
        else:
            flag=0
            break
    elif y==H-1:
        if (A[y][x+1] == "#")and(A[y-1][x+1]=="."):
            x=x+1
        else:
            flag=0
            break
    else:
        if (A[y+1][x]=="#")and(A[y][x+1]=="."):
            y=y+1
        elif (A[y][x+1] == "#") and (A[y+1][x] == "."):
            x=x+1
        else:
            flag=0
            break
    #print(x,y)
if flag==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)]
x=0
y=0
flag=1
while True:
    if (x==W-1)and(y==H-1):
        try:
            if A[max(H-2)][x]=="#":
                flag=0
        except:
            flag=1
        break
    if x==W-1:  #横端についた
        if (A[y+1][x]=="#")and(A[y+1][x-1]=="."):
            y=y+1
        else:
            flag=0
            break
    elif y==H-1:
        if (A[y][x+1] == "#")and(A[y-1][x+1]=="."):
            x=x+1
        else:
            flag=0
            break
    else:
        if (A[y+1][x]=="#")and(A[y][x+1]=="."):
            y=y+1
        elif (A[y][x+1] == "#") and (A[y+1][x] == "."):
            x=x+1
        else:
            flag=0
            break
    #print(x,y)
if flag==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)]
x=0
y=0
flag=1
while True:
    if (x==W-1)and(y==H-1):
        try:
            if A[max(H-2)][x]=="#":
                flag=0
        except:
            flag=1
        break
    if x==W-1:  #横端についた
        if (A[y+1][x]=="#"):
            y=y+1
        else:
            flag=0
            break
    elif y==H-1:
        if (A[y][x+1] == "#"):
            x=x+1
        else:
            flag=0
            break
    else:
        if (A[y+1][x]=="#")and(A[y][x+1]=="."):
            y=y+1
        elif (A[y][x+1] == "#") and (A[y+1][x] == "."):
            x=x+1
        else:
            flag=0
            break
    #print(x,y)
if flag==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)]
x=0
y=0
flag=1
while True:
    if (x==W-1)and(y==H-1):
        if A[max(0,H-2)][x]=="#":
            flag=0
        break
    if x==W-1:
        if (A[y+1][x]=="#"):
            y=y+1
        else:
            flag=0
            break
    elif y==H-1:
        if (A[y][x+1] == "#"):
            x=x+1
        else:
            flag=0
            break
    else:
        if (A[y+1][x]=="#")and(A[y][x+1]=="."):
            y=y+1
        elif (A[y][x+1] == "#") and (A[y+1][x] == "."):
            x=x+1
        else:
            flag=0
            break
    #print(x,y)
if flag==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)]
x=0
y=0
flag=1
while not((x==W-1)and(y==H-1)):
    if x==W-1:
        if (A[y+1][x]=="#"):
            y=y+1
        else:
            flag=0
            break
    elif y==H-1:
        if (A[y][x+1] == "#"):
            x=x+1
        else:
            flag=0
            break
    else:
        if (A[y+1][x]=="#")and(A[y][x+1]=="."):
            y=y+1
        elif (A[y][x+1] == "#") and (A[y+1][x] == "."):
            x=x+1
        else:
            flag=0
            break
    #print(x,y)
if flag==1:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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

A = []

for _ in range(H):
    A.append(list(input()))
    
a = []
for B in A:
    for i, C in enumerate(B):
        if C == '#':
            a.append(i)
            break
b = False
for i in range(i - 1):
    if a[i] <= a[i+1]:
        b = True
        break
if b:
    print('Impossible')
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w = na()
b = 0
for i in range(h):
    a = list(ns())
    b += a.count('#')

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

Submission status: Wrong Answer

Solution code:
# Problem A - Shik and Stone

# input
H, W = map(int, input().split())
board = [['.']*W for i in range(H)]
v_board = [[True]*W for i in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        board[i][j] = s[j]

# initialization
is_ok = True

# search
class DfsSearch:
    def __init__(self):
        self.is_ok = True

    def get_is_ok(self):
        return self.is_ok

    def dfs(self, pos):
        x = pos[0]
        y = pos[1]
        v_board[x][y] = False
        # left
        if y-1>=0 and board[x][y-1]=='#' and v_board[x][y-1]:
            self.is_ok = False
            self.dfs([x, y-1])

        # up
        if x-1>=0 and board[x-1][y]=='#' and v_board[x-1][y]:
            self.is_ok = False
            self.dfs([x-1, y])

        # right
        if y+1<W and board[x][y+1]=='#' and v_board[x][y+1]:
            self.dfs([x, y+1])

        # down
        if x+1<H and board[x+1][y]=='#' and v_board[x+1][y]:
            self.dfs([x+1, y])

        v_board[x][y] = True

# output
dfs = DfsSearch()
dfs.dfs([0, 0])
if dfs.get_is_ok():
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w = na()
b = [0,0]
for i in range(h):
    a = list(ns())
    c = [-1,w-1]
    for j in range(w):
        if c[0] == -1 and a[j] == '#':
            c[0] = j
        if c[0] != -1 and a[j] == '.':
            c[1] = j-1
    if b[1] != c[0]:
        print('Impossible')
        exit()
    b = c

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w = na()
b = [0,0]
for i in range(h):
    a = list(ns())
    c = [-1,w-1]
    for j in range(w):
        if c[0] == -1 and a[j] == '#':
            c[0] = j
        if c[0] != w-1 and a[j] == '.':
            c[1] = j-1
    if b[1] != c[0]:
        print('Impossible')
        exit()
    b = c

Submission status: Wrong Answer

Solution code:
from collections import deque
dx = (1, 0, -1, 0)
dy = (0, 1, 0, -1)

H, W = [int(i) for i in input().split()]
A = [[0 if v=="#" else -1 for v in list(input())] for _ in range(H)]

que = deque()
que.append((0, 0))

logx = []
logy = []
while que:
    ny, nx = que.popleft()
    A[ny][nx] = 1
    logy.append(ny)
    logx.append(nx)
    # print("visited: A[{}][{}]".format(ny, nx), end=" ")
    # print(que)
    if que:
        print(que)
        print("Impossible")
        quit()
    for y, x in zip(dy, dx):
        my, mx = ny+y, nx+x
        if 0 <= my < H and 0 <= mx < W and A[my][mx] == 0:
            que.append((my, mx))

for i in range(len(logx)-1):
    if logx[i]>logx[i+1]:
        print("Impossible")
        quit()
    if logy[i]>logy[i+1]:
        print("Impossible")
        quit()

print("Possible")

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w = na()
a = []
for i in range(h):
    a.append(list(ns()))

def f(x,y):
    if x == w-1 and y == h-1:
        print('Possible')
        exit()
    if y < h-1 and a[y+1][x] == '#':
        f(x,y+1)
    if x < w-1 and a[y][x+1] == '#':
        f(x+1,y)

f(0,0)
print('Impossible')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

def pad(mxy, wall="#"):
	w = len(mxy[0])
	gp = wall*(w+2)
	re = [gp,]
	re_app = re.append
	for vx in mxy:
		re_app(wall+vx+wall)
	re_app(gp)
	return re

def main():
	H,W = linput()
	mM = [input() for _ in [0,]*H]
	mM = pad(mM,".")
	mV = [[0,]*(W+2) for _ in [0,]*(H+2)]
	
	vD = [(0,1),(1,0)]
	
	res = False
	cnt = 0
	
	vQ = []
	vQ_app, vQ_pop = vQ.append, vQ.pop
	if mM[1][1]=="#":
		vQ_app((1,1))
	while vQ:
		x,y = vQ_pop()
		#print(x,y)
		if (x,y)==(W,H):
			res = True; mV[H][W] = 1; break
		
		mV[y][x] = 1
		
		for dx,dy in vD:
			nx,ny = x+dx, y+dy
			if mM[ny][nx]=="#" and \
			not mV[ny][nx]:
				vQ_app((nx,ny))
		
		cnt += 1
		#print(res,cnt,X,Y,H)
		if cnt>999999: break
	
	if res:
		for vm,vv in zip(mM,mV):
			if not all(v for m,v in 
			  zip(vm,vv) if m=="#"):
				res = False; break
	
	print(("Impossible","Possible")[res])
	#print(res)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
h, w = [int(i) for i in input().split()]
lists = []
for _ in range(h):
    l = input().split()[0]
    l = [c for c in l]
    lists.append(l)

x = 0
y = 0
while not (x==w-1 and y==h-1):
    #print(x,y)
    lists[y][x]='.'
    if 0<x and lists[y][x-1]=='#':
        print("Impossible")
        break
    if 0<y and lists[y-1][x]=='#':
        print("Impossible")
        break
    if x<w-1 and lists[y][x+1]=='#' and y<h-1 and lists[y+1][x]=='#' :
        print("Impossible")
        break
    if x<w-1 and lists[y][x+1]=='#':
        x += 1
    else:
    #elif y<h-1 and lists[y+1][x]=='#' :
        y += 1
else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
h, w = [int(i) for i in input().split()]
lists = []
for _ in range(h):
    l = input().split()[0]
    l = [c for c in l]
    lists.append(l)

x = 0
y = 0
while not (x==w-1 and y==h-1):
    #print(x,y)
    lists[y][x]='.'
    if 0<x and lists[y][x-1]=='#':
        print("Impossible")
        break
    if 0<y and lists[y-1][x]=='#':
        print("Impossible")
        break
    if x<w-1 and lists[y][x+1]=='#' and y<h-1 and lists[y+1][x]=='#' :
        print("Impossible")
        break
    if x<w-1 and lists[y][x+1]=='#':
        x += 1
    elif y<h-1 and lists[y+1][x]=='#' :
        y += 1
else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
h, w = [int(i) for i in input().split()]
lists = []
for _ in range(h):
    l = input().split()[0]
    l = [c for c in l]
    lists.append(l)

x = 0
y = 0
while not (x==w-1 and y==h-1):
    print(x,y)
    lists[y][x]='.'
    if 0<x and lists[y][x-1]=='#':
        print("Impossible")
        break
    if 0<y and lists[y-1][x]=='#':
        print("Impossible")
        break
    if x<w-1 and lists[y][x+1]=='#' and y<h-1 and lists[y+1][x]=='#' :
        print("Impossible")
        break
    if x<w-1 and lists[y][x+1]=='#':
        x += 1
    elif y<h-1 and lists[y+1][x]=='#' :
        y += 1
else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
h, w = [int(i) for i in input().split()]
lists = []
for _ in range(h):
    l = input().split()[0]
    l = [c for c in l]
    lists.append(l)

x = 0
y = 0
while not (x==w-1 and y==h-1):
    #print(x,y)
    lists[y][x]='.'
    if 0<x and lists[y][x-1]=='#':
        print("Impossible")
        break
    if 0<y and lists[y-1][x]=='#':
        print("Impossible")
        break
    if x<w-1 and lists[y][x+1]=='#' and y<h-1 and lists[y+1][x]=='#' :
        print("Impossible")
        break
    if x<w-1 and lists[y][x+1]=='#':
        x += 1
    if y<h-1 and lists[y+1][x]=='#' :
        y += 1
else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
h, w = [int(i) for i in input().split()]
lists = []
for _ in range(h):
    l = input().split()[0]
    lists.append(l)

x = 0
y = 0
while(x==w-1 and y==h-1):
    lists[y][x]='.'
    if 0<x and lists[y][x-1]=='#':
        print("Impossible")
        break
    if 0<y and lists[y-1][x]=='#':
        print("Impossible")
        break
    if x<w-1 and lists[y][x+1]=='#' and y<h-1 and lists[y+1][x]=='#' :
        print("Impossible")
        break
    if x<w-1 and lists[y][x+1]=='#':
        x += 1
    if y<h-1 and lists[y+1][x]=='#' :
        y += 1
else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
pos = [0, 0]
S = [input() for i in range(H)]
p = 1
while pos != [H-1, W-1]:
  cnt = 0
  x, y = pos[0], pos[1]
  if x < H-1:
    if S[x+1][y] == '#':
      cnt += 1
      pos = [x+1, y]
  if y < W-1:
    if S[x][y+1] == '#':
      cnt += 1
      pos = [x, y+1]
  if cnt != 1:
    p = 0
    break
if p == 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)]
a.append(["."] * (w + 1))

i = 0
j = 0

bl = False
while True:
    if a[i+1][j] == "#":
        a[i][j] = "."
        i += 1
    elif a[i][j+1] == "#":
        a[i][j] = "."
        j += 1
    else:
        break

    if i == h - 1 and j == w - 1:
        bl = True

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

Submission status: Wrong Answer

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

i = 0
j = 0

bl = False
while True:
    if i == h - 1 and j == w - 1:
        bl = True

    if a[i+1][j] == "#":
        a[i][j] = "."
        i += 1
    elif a[i][j+1] == "#":
        a[i][j] = "."
        j += 1
    else:
        break

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

Submission status: Wrong Answer

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

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

# for i in range(H):
#     print(A[i])

di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

ans = True
for i in range(H):
    for j in range(W):
        if (i == 0 and j == 0) or (i == H-1 and j == W-1):
            continue
        if A[i][j] == '#':
            ul = 0  # 上 or 左
            rd = 0  # 右 or 下
            for k in range(4):
                ni = i + di[k]
                nj = j + dj[k]
                if 0 <= ni < H and 0 <= nj < W:
                    if A[ni][nj] == '#':
                        if k == 0 or k == 1:
                            ul += 1
                        else:
                            rd += 1
            # print(i, j, ':', ul, rd)
            if not (ul == 1 and rd == 1):
                ans = False

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

Submission status: Wrong Answer

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

ans = "Impossible"

cnt = 0
for a in A:
    cnt += A.count("#")

if cnt == H + W - 1:
    ans = "Possible"

print(ans)

Submission status: Wrong Answer

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

ans = "Impossible"


def f(y, x):
    if y == H-1 and x == W-1:
        global ans
        ans = "Possible"
        return
    elif not (0 <= y < H and 0 <= x < W):
        return
    elif A[y][x] == ".":
        return
    
    f(y+1, x)
    f(y, x+1)


f(0, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
#n = int(input())
#n,k = map(int,input().split())
#x = list(map(int,input().split()))


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

h = 0
w = 0
A[0][0]="."

while not(h==H-1 and w==W-1):
    # print(h,w)
    if h<H-1 and w<W-1 and A[h+1][w]=="#" and A[h][w+1]=="#":
        print("Impossible")
        break

    elif h<H-1 and A[h+1][w]=="#":
        h += 1
        A[h][w] = "."

    elif w<W-1 and A[h][w+1]=="#":
        w += 1
        A[h][w] = "."
    else:
        print("Impossible")
        break

else:
    flg = 0
    for h in range(H):
        for w in range(W):
            if A[h][w]=="#":
                print("Impossible")
                flg = 1
                break
    else:
        if flg:
            print("Impossible")
        else:    
            print("Possible")

Submission status: Wrong Answer

Solution code:
print("Impossible")

Submission status: Wrong Answer

Solution code:
#n = int(input())
#n,k = map(int,input().split())
#x = list(map(int,input().split()))


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

h = 0
w = 0
A[0][0]="."

while not(h==H-1 and w==W-1):
    # print(h,w)
    if h<H-1 and w<W-1 and A[h+1][w]=="#" and A[h][w+1]=="#":
        print("Impossible")
        break

    elif h<H-1 and A[h+1][w]=="#":
        h += 1
        A[h][w] = "."

    elif w<W-1 and A[h][w+1]=="#":
        w += 1
        A[h][w] = "."
    else:
        print("Impossible")
        break

else:
    flg = 0
    for h in range(H):
        if flg:
            break
        for w in range(W):
            if A[h][w]=="#":
                print("Impossible")
                flg = 1
                break
    else:
        print("Possible")

Submission status: Wrong Answer

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

h = 0
w = 0

while not(h==H-1 and w==W-1):
    # print(h,w)
    if h<H-1 and w<W-1 and A[h+1][w]=="#" and A[h][w+1]=="#":
        print("Impossible")
        break

    elif h<H-1 and A[h+1][w]=="#":
        h += 1

    elif w<W-1 and A[h][w+1]=="#":
        w += 1
    else:
        print("Impossible")
        break

else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

h,w = inpl()
s = [input() for i in range(h)]
cnt = 0
for i in s:
    cnt += s.count('#')
if cnt != h+w:
    print('Impossible')
    quit()
for fl in itertools.combinations(range(h+w-2),h-1):
    nx = 0; ny = 0
    for i in range(h+w-2):
        if i in fl:
            ny += 1
        else:
            nx += 1
        if s[ny][nx] == '#':
            continue
        break
    else:
        print('Possible')
        break
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    h, w = map(int, input().split())
    a = list()
    for i in range(h):
        a.append(input() + '.')
    a.append('.' * (w+1))

    pos = [0, 0]
    while True:
        if pos == [h-1, w-1]:
            print('Possible')
            exit()
        tmp = a[pos[0]+1][pos[1]] + a[pos[0]][pos[1]+1] + \
            a[pos[0]-1][pos[1]] + a[pos[0]][pos[1]-1]
        count = tmp.count('#')
        if count > 2:
            print('Impossible')
            exit()
        if a[pos[0]+1][pos[1]] == '#':
            pos[0] += 1
            continue
        if a[pos[0]][pos[1]+1] == '#':
            pos[1] += 1
            continue
        print('Impossible')
        exit()

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    h, w = map(int, input().split())
    a = list()
    for i in range(h):
        a.append(input() + '.')
    a.append('.' * (w+1))

    pos = [0, 0]
    while True:
        if pos == [h-1, w-1]:
            print('Possible')
            exit()
        if a[pos[0]+1][pos[1]] == '#' and a[pos[0]][pos[1]+1] == '#':
            print('Impossible')
            exit()
        if a[pos[0]+1][pos[1]] == '#':
            pos[0] += 1
            continue
        if a[pos[0]][pos[1]+1] == '#':
            pos[1] += 1
            continue
        print('Impossible')
        exit()

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    h, w = map(int, input().split())
    a = list()
    for i in range(h):
        a.append(input())

    pos = [0, 0]
    while True:
        if pos == [h-1, w-1]:
            print('Possible')
            exit()
        if pos[0] == h-1 or pos[1] == w-1:
            print('Impossible')
            exit()
        if a[pos[0]+1][pos[1]] == '#' and a[pos[0]][pos[1]+1] == '#':
            print('Impossible')
            exit()
        if a[pos[0]+1][pos[1]] == '#':
            pos[0] += 1
        if a[pos[0]][pos[1]+1] == '#':
            pos[1] += 1

Submission status: Wrong Answer

Solution code:
from sys import stdin,setrecursionlimit
from itertools import groupby
from collections import deque
setrecursionlimit(10**7)
h,w = map(int,stdin.readline().rstrip().split())
inf = 10**10
li = [["" for i in range(w)]for j in range(h)]
point = h+w-1
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque()
lin = [[inf for i in range(w)]for j in range(h)]
lin[0][0] = 0
que.append([0,0])
while que:
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "." :
            continue
        elif lin[nx][ny] == inf:
            que.append([nx,ny])
            lin[nx][ny] = lin[x][y]+1
kotae = lin[h-1][w-1]
if kotae+1 == point:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
from sys import stdin,setrecursionlimit
from itertools import groupby
from collections import deque
setrecursionlimit(10**7)
h,w = map(int,stdin.readline().rstrip().split())
inf = 10**10
li = [["" for i in range(w)]for j in range(h)]
point = h+w-1
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
que = deque()
lin = [[inf for i in range(w)]for j in range(h)]
lin[0][0] = 0#ここをスタートの座標に変えること
que.append([0,0])#ここもスタートの座標に変えること
while que:
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        elif li[nx][ny] == "." :
            continue
        elif lin[nx][ny] == inf:
            que.append([nx,ny])
            lin[nx][ny] = lin[x][y]+1
kotae = lin[h-1][w-1]
if kotae+1 == point:
    print("Possible")
else:
    print("Impossibe")

Submission status: Wrong Answer

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

ok = True
N = 0
for i in range(H):
  if ok == False: break
  n = 0
  for j in range(W):
    if j == N:
      if A[i][j] != "#" or A[i][j - 1] == "#" or A[i][j+1] != "#":
        ok = False
        break
    if A[i][j] == "#":
      n = j
  N = n
print("Possible" if ok else "Impossible")

Submission status: Wrong Answer

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

ok = True
N = 0
for i in range(H):
  if ok == False: break
  n = 0
  for j in range(W):
    if j == N:
      if A[i][j] != "#" or A[i][j - 1] == "#":
        ok = False
        break
    if A[i][j] == "#":
      n = j
  N = n
print("Possible" if ok else "Impossible")

Submission status: Wrong Answer

Solution code:
from sys import stdin,setrecursionlimit
from itertools import groupby
setrecursionlimit(10**7)
h,w = map(int,stdin.readline().rstrip().split())
li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]
now = 0
last = 0
for i in range(h):
    flag = True
    for j in range(w):
        lin = []
        for key, value in groupby(li[i]):
            lin.append(key)
        if lin.count("#") >= 2:
            print("Impossible")
            exit()
        if li[i][j] == "#" and flag:
            now = j
            flag = False
        if i >= 1 and now != last:
            print("Impossible")
            exit()
        if (flag == False and li[i][j] == "."):
            last = j-1
            break
        if  (not flag and j == w-1):
            last = j
            break
if last == w-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
from sys import stdin,setrecursionlimit
from itertools import groupby
setrecursionlimit(10**7)
h,w = map(int,stdin.readline().rstrip().split())
li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]
now = 0
last = 0
for i in range(h):
    flag = True
    for j in range(w):
        lin = []
        for key, value in groupby(li[i]):
            lin.append(key)
        if lin.count("#") >= 2:
            print("Impossible")
            exit()
        if li[i][j] == "#" and flag:
            now = j
            flag = False
        if (flag == False and li[i][j] == "."):
            last = j-1
            break
        if  (not flag and j == w-1):
            last = j
            break
if last == w-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
B = ["."+input()+"." for k in range(H)]
B = ["."*(W+2)] + B + ["."*(W+2)]
x, y = 1,1
while True:
    if x == W and y == H:
        print("Possible")
        exit(0)
    elif B[y][x+1] == "#" and B[y+1][x] == ".":
        x += 1
    elif B[y+1][x] == "#" and B[y][x+1] == ".":
        y += 1
    else:
        print("Impossible")
        exit(0)