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:
import sys
h, w = map(int, input().split())
a = [input() for _ in range(h)]
flag = True
for i in range(h):
    for j in range(w):
        if not flag:
            print('Impossible')
            sys.exit()
        if a[i][j] == '#':
            if i == 0:
                if j == 0:
                    if (a[0][1] == '#' and a[1][0] == '#'):
                        flag = False
                if 1 <= j and j <= w-2:
                    if (a[0][j+1] == '#' and a[1][j] == '#') or (a[0][j+1] == '.' and a[1][j] == '.'):
                        flag = False
                if j == w-1:
                    if a[i+1][j] != '#':
                        flag = False
            if i == h-1:
                if j == 0:
                    if a[i][j+1] != '#':
                        flag = False
                if (1 <= j and j <= w-2):
                    if a[i][j+1] != '#':
                        flag = False
            if (1 <= i and i <= h-2):
                if j == 0:
                    if (a[i][j+1] == '#' and a[i+1][j] == '#'):
                        flag = False
                if j == w-1:
                    if a[i+1][j] != '#':
                        flag = False
                if (1 <= j and j <= w-2):
                    if (a[i][j+1] == '#' and a[i+1][j] == '#'):
                        flag = False

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

Submission status: Wrong Answer

Solution code:
# A - Shik and Stone
import sys
sys.setrecursionlimit(1000000)
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
def dfs1(y,x,cy,cx):
    if (y<0 or y>=h or x<0 or x>=w or a[y][x]=='.'):return
    if cy>y or cx>x:
        if visited1[y][x]:
            return
        else:
            ng_flg[0]=False

    visited1[y][x] = True
    cy=y
    cx=x
    dfs1(y+1,x,cy,cx)
    dfs1(y-1,x,cy,cx)
    dfs1(y,x+1,cy,cx)
    dfs1(y,x-1,cy,cx)

h,w=nm()
a=[input() for i in range(h)]
visited1 = [[False]*w for i in range(h)]
ng_flg=[True]
dfs1(0,0,0,0)

if visited1[h-1][w-1] and ng_flg[0]:
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
# AGC007a
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    h, w = map(int, input().split())

    grid = [input()[:-1] for _ in range(h)]

    def dfs(i, j):
        cou = 0
        if i == h-1 and j == w-1 or i == h-2 and j == w-1 or i == h-1 and j == w-2:
            print('Possible')
            exit(0)
        if i < h-1 and grid[i+1][j] == '#':
            cou += 1
        if j < w-1 and grid[i][j+1] == '#':
            cou += 1
        if cou != 1:
            print('Impossible')
            exit(0)
        if i < h-1 and grid[i+1][j] == '#':
            dfs(i+1, j)
        if j < w-1 and grid[i][j+1] == '#':
            dfs(i, j+1)

    dfs(0, 0)
    print('Impossible')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# AGC007a
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    h, w = map(int, input().split())

    grid = [input()[:-1] for _ in range(h)]

    def dfs(i, j):
        cou = 0
        if i == h-1 and j == w-1:
            print('Possible')
            exit(0)
        if i < h-1 and grid[i+1][j] == '#':
            cou += 1
        if j < w-1 and grid[i][j+1] == '#':
            cou += 1
        if cou != 1:
            print('Impossible')
            exit(0)
        if i < h-1 and grid[i+1][j] == '#':
            dfs(i+1, j)
        if j < w-1 and grid[i][j+1] == '#':
            dfs(i, j+1)

    dfs(0, 0)
    print('Impossible')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)
H, W = map(int, input().split())
A = [input() for _ in range(H)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def dfs(x, y, cx, cy):
    if x==W-1 and y==H-1:
        return True
    cnt = 0
    Nx = 0
    Ny = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if cx==nx and cy == ny:
            continue
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if A[ny][nx] == '#':
            Nx = nx
            Ny = ny
            cnt+=1
    if not cnt == 1:
        return False
    if (Nx == x+1 and Ny == y) or (Nx == x and Ny == y+1):
        return dfs(Nx, Ny, x, y)
    else:
        return False


if __name__ == '__main__':
    if dfs(0, 0, -1, -1):
        print('Possible')
    else:
        print('Impossible')

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [input() for _ in range(H)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def dfs(x, y, cx, cy):
    if x==W-1 and y==H-1:
        return True
    cnt = 0
    Nx = 0
    Ny = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if cx==nx and cy == ny:
            continue
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if A[ny][nx] == '#':
            Nx = nx
            Ny = ny
            cnt+=1
    if not cnt == 1:
        return False
    if (Nx == x+1 and Ny == y) or (Nx == x and Ny == y+1):
        return dfs(Nx, Ny, x, y)
    else:
        return False


if __name__ == '__main__':
    if dfs(0, 0, -1, -1):
        print('Possible')
    else:
        print('Impossible')

Submission status: Wrong Answer

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

q = [[0,0]]

while q != []:
	ans = 0
	cx,cy = q.pop()
	A[cx][cy] = "."

	if [cx,cy] == [H-1,W-1]:
		ans = 1
		for i in range(H):
			for j in range(W):
				if A[i][j] == "#":
					ans = 0
		break

	nps = [[cx+1,cy],[cx,cy+1]]
	for nx,ny in nps:
		if 0 <= nx < H and 0 <= ny < W:
			if A[nx][ny] == "#":
				q.append([nx,ny])

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

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
X = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]

Q = [0]
D = [[0] * W for _ in range(H)]
D[0][0] = 1
c = 1
while Q:
    x = Q.pop()
    i, j = x//W, x%W
    for di, dj in ((1, 0), (0, 1)):
        ni, nj = i+di, j+dj
        if ni < H and nj < W and X[ni][nj]:
            if D[ni][nj] == 0:
                D[ni][nj] = 1
                Q.append(ni*W + nj)
                c += 1
if D[-1][-1] and c == H + W - 1:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import queue

def main():
    H,W = map(int,input().split())
    root = [list(str(input())) for _ in range(H)]
    _long = [[0 for _ in range(W)] for _ in range(H)]
    _long[0][0] = 1
    al = 0
    for i in range(H):
        for j in range(W):
            if root[i][j] == "#":
                al += 1
    
    if al != H+W-1:
        print("IMPOSSIBLE")
        exit()
    
    print("POSSIBLE")
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n,m=map(int,input().split())
s = [list(input()) for i in range(n)]
ans=[]
print('Possible')
"""
def dfs(x,y):
    for i in range(2):
        for j in range(2):
            if i==0 and j==0:
                continue
            else:
                nx=i+x
                ny=j+y
                if 0<=nx<n and 0<=ny<m and s[nx][ny]=='#':
                    if [nx,ny] not in ans:
                        ans.append([nx,ny])
                    dfs(nx,ny)
dfs(0,0)
cnt=0
for i in range(n):
    for j in range(m):
        if s[i][j]=='#':
            cnt+=1
if ans[len(ans)-1]==[n-1,m-1] and len(ans)==cnt-1:
    print('Possible')
else:
    print('Impossible')
#print(ans)"""

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n,m=map(int,input().split())
s = [list(input()) for i in range(n)]
ans=[]
def dfs(x,y):
    for i in range(2):
        for j in range(2):
            if i==0 and j==0:
                continue
            else:
                nx=i+x
                ny=j+y
                if 0<=nx<n and 0<=ny<m and s[nx][ny]=='#':
                    if [nx,ny] not in ans:
                        ans.append([nx,ny])
                    dfs(nx,ny)
dfs(0,0)
cnt=0
for i in range(n):
    for j in range(m):
        if s[i][j]=='#':
            cnt+=1
if ans[len(ans)-1]==[n-1,m-1] and len(ans)==cnt-1:
    print('Possible')
else:
    print('Impossible')
#print(ans)

Submission status: Wrong Answer

Solution code:
import copy
from collections import deque
H,W = map(int,input().split())
A = []
for i in range(H):
    A.append(list(input()))
now = [0,0]
goal = [H-1,W-1]
x1 = [0,0,1,-1]
y1 = [1,-1,0,0]
alr = copy.deepcopy(A)
alr[0][0] = 1
que = deque()
que.append(now)
while que:
    q = que.popleft()
    for i in range(4):
        if 0 <= q[0]+x1[i] <= H-1 and 0 <= q[1]+y1[i] <= W-1 and alr[q[0]+x1[i]][q[1]+y1[i]] == '#':
            alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] +1
            que.append([q[0]+x1[i],q[1]+y1[i]])
if alr[-1][-1] != '#':
    num = alr[-1][-1]
    count = {}
    for i in range(1,num+1):
        count[i] = 0
    for i in range(H):
        for j in range(1,num+1):
            count[j] += alr[i].count(j)
    flag = True
    for i,v in count.items():
        if v != 1:
            flag = False
    if flag:
        print('Possible')
    else:
        print('Impossible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
import copy
from collections import deque
H,W = map(int,input().split())
A = []
for i in range(H):
    A.append(list(input()))
now = [0,0]
goal = [H-1,W-1]
x1 = [0,1]
y1 = [1,0]
alr = copy.deepcopy(A)
alr[0][0] = 1
que = deque()
que.append(now)
while que:
    q = que.popleft()
    for i in range(2):
        if 0 <= q[0]+x1[i] <= H-1 and 0 <= q[1]+y1[i] <= W-1 and alr[q[0]+x1[i]][q[1]+y1[i]] == '#':
            alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] +1
            que.append([q[0]+x1[i],q[1]+y1[i]])
if alr[-1][-1] != '#':
    num = alr[-1][-1]
    count = {}
    for i in range(1,num+1):
        count[i] = 0
    for i in range(H):
        for j in range(1,num+1):
            count[j] += alr[i].count(j)
    flag = True
    for i,v in count.items():
        if v != 1:
            flag = False
    if flag:
        print('Possible')
    else:
        print('Impossible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
bd = [list("."+input()+".") for i in range(h)]
bd.insert(0,["."]*(w+2))
bd.append(["."]*(w+2))
for i in range(h+1):
  for j in range(w+1):
    if bd[i][j] == "#":
      if i == h and j == w:
        print("Possible")
        break
      if bd[i+1][j] == bd[i][j+1]:
        print("Impossible")
        break
      if bd[i-1][j] == "#" or bd[i][j-1] == "#":
        print("Impossible")
        break
      bd[i][j]="."
  else:
    continue
  break

Submission status: Wrong Answer

Solution code:
from collections import deque

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

c=l.count('#')

sy,sx=0,0
gy,gx=h-1,w-1

stack=deque()
stack.append((sy,sx))

cnt=1
while stack:
 y,x=stack.pop()

 if y==gy and x==gx and cnt==c:
  print('Possible')
  exit()

 for dy,dx in [[1,0],[0,1]]:
  ny=y+dy
  nx=x+dx
  if ny<=h-1 and nx<=w-1 and l[ny][nx]=='#':
   stack.append((ny,nx))
   l[ny][nx]=='.'
   cnt+=1

print('Impossible')

Submission status: Wrong Answer

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

h,w = 0,0

while True: #h<=H-1 and w <=W-1:
    if (li[h+1][w] == "#" or li[h][w+1] == "#") and (li[h+1][w+1] == "#"):
        flag = True
    elif (li[h+1][w] == "#" or li[h][w+1] == "#") and (li[h+1][w+1] == "#") == False:
        print("Impossible")
        exit()

    h += 1
    w += 1
    if h == H-1 or w == W-1:
        break
if flag == True: # and li[H][W] == li[h-2][w-2]:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
li = [input() for i in range(H)]
print(li)
h,w = 0,0

while True: #h<=H-1 and w <=W-1:
    if (li[h+1][w] == "#" or li[h][w+1] == "#") and (li[h+1][w+1] == "#"):
        flag = True
    elif (li[h+1][w] == "#" or li[h][w+1] == "#") and (li[h+1][w+1] == "#") == False:
        print("Impossible")
        exit()
    print(li[h][w],h,w)
    h += 1
    w += 1
    if h == H-1 or w == W-1:
        break
if flag == True: # and li[H][W] == li[h-2][w-2]:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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


def dfs(graph: list, start: tuple, goal: tuple) -> int:
    one_steps = ((1, 0), (0, 1))
    seen = {start}
    todo = [start]
    dump = set()
    while todo:
        x, y = todo.pop(-1)
        dump.add((x, y))
        for dx, dy in one_steps:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H) or not (0 <= ny < W):
                continue
            if (nx, ny) in seen:
                continue
            if graph[nx][ny] == "#":
                todo.append((nx, ny))
                seen.add((nx, ny))
            if (nx, ny) == goal:
                return len(dump)
    return len(dump)


step = dfs(graph, (0, 0), (H - 1, W - 1))
sharp = 0
for line in graph:
    sharp += line.count("#")
if step + 1 == sharp:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
A = [ input() for _ in range(h) ]
nh, nw = 0, 0
if A[0][0] != "#":
  print("Impossible")
  exit()
while True:
  if nh == h-1 and nw == w-1:
    print("Possible")
    break
  if nh == h-1:
    if A[nh][nw+1] == "#":
      nw += 1
    else:
      print("Impossible")
      break
  elif nw == w-1:
    if A[nh+1][nw] == "#":
      nh += 1
    else:
      print("Impossible")
      break
  else:
    s, t = A[nh][nw+1] == "#", A[nh+1][nw] == "#"
    if s ^ t:
      nh += int(t)
      nw += int(s)
    else:
      print("Impossible")
      break

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
A = [ input() for _ in range(h) ]
nh, nw = 0, 0
while True:
  if nh == h-1 and nw == w-1:
    if A[h-1][w-1] == "#":
      print("Possible")
    else:
      print("Impossible")
    break
  if nh == h-1:
    if A[nh][nw+1] == "#":
      nw += 1
    else:
      print("Impossible")
      break
  elif nw == w-1:
    if A[nh+1][nw] == "#":
      nh += 1
    else:
      print("Impossible")
      break
  else:
    s, t = A[nh][nw+1] == "#", A[nh+1][nw] == "#"
    if s ^ t:
      nh += int(t)
      nw += int(s)
    else:
      print("Impossible")
      break

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
A = [ input() for _ in range(h) ]
nh, nw = 0, 0
while True:
  if nh == h-1 and nw == w-1:
    print("Possible")
    break
  if nh == h-1:
    if A[nh][nw+1] == "#":
      nw += 1
    else:
      print("Impossible")
      break
  elif nw == w-1:
    if A[nh+1][nw] == "#":
      nh += 1
    else:
      print("Impossible")
      break
  else:
    s, t = A[nh][nw+1] == "#", A[nh+1][nw] == "#"
    if s ^ t:
      nh += int(t)
      nw += int(s)
    else:
      print("Impossible")
      break

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())

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

def dfs(h,w):
    l[h][w]="!"
    #print(l)
    #print(h,w,l[h][w])
    if h==H-1 and w==W-1:
        print("Possible")
        exit()
    elif l[h-1][w]=="#" or l[h][w-1]=="#":
        print("Impossible")
        exit()
    
    if h<H-1:
        if l[h+1][w]=="#":
            dfs(h+1,w)
    if w<W-1:
        if l[h][w+1]=="#":
            dfs(h,w+1)
    l[h][w]="#"
    return "Impossible"

print(dfs(0,0))

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
gy,gx=H-1,W-1
grid=["" for i in range(H)]
touched=0
for i in range(H):
  grid[i]=input()
  touched+=grid[i].count("#")
  
stack=[]
stack.append([0,0])
goal=False
while stack:
  v=stack.pop()
  y=v[0]
  x=v[1]
  if grid[y][x]=="#":
    touched-=1
  if y==gy and x==gx:
    goal=True
    break
  if grid[y][x]==".":
    continue
  if y+1<H:
    stack.append([y+1,x])
  if x+1<W:
    stack.append([y,x+1])
    
print(("Impossible","Possible")[goal and touched==0])

Submission status: Wrong Answer

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

i,j = 0,0
while i<H-1 or j<W-1:
    if ((i>0 and A[i-1][j]=='#') and (j>0 and A[i][j-1]=='#')) or ((i<H-1 and A[i+1][j]=='#') and (j<W-1 and A[i][j+1]=='#')):
        print('Impossible')
        break
    else:
        if i<H-1 and A[i+1][j]=='#':
            i += 1
        elif j<W-1 and A[i][j+1]=='#':
            j += 1
        else:
            print('Impossible')
            break
if i==H-1 and j==W-1:
    print('Possible')

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = rl()
A = [list(rs()) for _ in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            A[i][j] = 1
        else:
            A[i][j] = 0
    A[i].append(0)            
A.append([0] * (W + 1))
bool = True

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            if A[i+1][j] + A[i][j+1] != 1:
                bool = False
        if i == H - 1 and j == W - 1:
            if A[i-1][j] + A[i][j-1] != 1:
                bool = False
        if A[i][j] == 1:
            if A[i+1][j] + A[i][j+1] != 1:
                bool = False
            if A[i-1][j] + A[i][j-1] != 1:
                bool = False

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

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = rl()
A = [list(rs()) for _ in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            A[i][j] = 1
        else:
            A[i][j] = 0
    A[i].append(0)            
A.append([0] * (W + 1))
bool = True

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        if i == H - 1 and j == W - 1:
            continue
        if A[i][j] == 1:
            if A[i+1][j] + A[i][j+1] != 1:
                bool = False
            if A[i-1][j] + A[i][j-1] != 1:
                bool = False
if A[0][0] == 0 or A[H-1][W-1] == 0:
    bool = False

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

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = rl()
A = [list(rs()) for _ in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            A[i][j] = 1
        else:
            A[i][j] = 0
    A[i].append(0)            
A.append([0] * (W + 1))
bool = True

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue
        if i == H - 1 and j == W - 1:
            continue
        if A[i][j] == 1:
            if A[i+1][j] + A[i][j+1] != 1:
                bool = False
            if A[i-1][j] + A[i][j-1] != 1:
                bool = False

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

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = rl()
A = [list(rs()) for _ in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            A[i][j] = 1
        else:
            A[i][j] = 0
    A[i].append(0)            
A.append([0] * (W + 1))
bool = True

for i in range(H):
    for j in range(W):
        if i == H - 1 and j == W - 1:
            continue
        if A[i][j] == 1:
            if A[i+1][j] + A[i][j+1] != 1:
                bool = False

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

A = np.zeros([W, H])

for i in range(H):
    A[:, i] = np.array(
            list(map(
                lambda x: 1 if x == "#" else 0, list(input())
                ))
            )

r = np.zeros([H, 2])

Submission status: Wrong Answer

Solution code:
h,w = map(int, input().split())
board = []
for i in range(h):
  board.append(list(input()))
line = 0
column = 0
for i in range(len(board)):
  board[i].append("")
for i in range((h-1) + (w-1)):
  if board[line][column+1] == "#":
    board[line][column] = "."
    column += 1
  elif board[line+1][column] == "#" :
    board[line][column] = "."
    line += 1
  else:
    print("Impossible")
    break
  if board[line-1][column] == "#" or board[line][column-1] == "#":
    print("Impossible")
    break
  if i+1 == (h-1) + (w-1):
    print("Possible")

Submission status: Wrong Answer

Solution code:
h,w = map(int, input().split())
board = []
for i in range(h):
  board.append(list(input()))
line = 0
column = 0
for i in range(len(board)):
  board[i].append("")
for i in range((h-1) + (w-1)):
  if board[line][column+1] == "#":
    board[line][column] = "."
    column += 1
  elif board[line+1][column] == "#" :
    board[line][column] = "."
    line += 1
  else:
    print("Impossible")
    break
  if i+1 == (h-1) + (w-1):
    print("Possible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
table = []
for i in range(h):
    table.append(list(input()))
poss = True
for i in range(h-1):
    for j in range(w-1):
        if table[i][j] == "#":
            if (table[i+1][j]=="#" and table[i][j+1]=="#") or (table[i+1][j]=="." and table[i][j+1]=="."):
                poss = False
if poss:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
table = []
for i in range(h):
    table.append(list(input()))
poss = True
for i in range(h-1):
    for j in range(w-1):
        if table[i][j] == "#":
            if table[i+1][j]=="#" and table[i][j+1]=="#":
                poss = False
if poss:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
def inpl():
    return list(map(int, input().split()))


H, W = inpl()
A = [list(input()) for i in range(H)]

x, y = 0, 0

while True:
    A[y][x] = '.'
    dy, dx = min(y + 1, H - 1), x
    ry, rx = y, min(x + 1, W - 1)
    if A[dy][dx] == '#':
        y, x = dy, dx
    elif A[ry][rx] == '#':
        y, x = ry, rx
    else:
        print('Impossible')
        break
else:
    if any('#' in a for a in A) is True:
        print('Impossible')
    else:
        print('Possible')

Submission status: Wrong Answer

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

h=0
w=0
while H>h or W>w:
    if H>h and W>w:
        if A[h+1][w]=="#" and  A[h][w+1]=="#":
            print("Impossible")
            exit()
        elif A[h+1][w]=="#":
            h+=1
        elif A[h][w+1]=="#":
            w+=1
        else:
            print("Impossible")
            exit()
    elif H>h and A[h+1][w]=="#":
        h+=1
    elif W>w and A[h][w+1]=="#":
        w+=1
    else:
        print("Impossible")
        exit()

print("Possible")

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
prev=0
for i in range(H):
  s=input()
  id = s.index("#")
  if id >= prev:
    flag=False
    prev = id
    for j in range(prev,W):
      if flag and s[j]=="#":
        print("Impossible")
        exit(0)
      if s[j]==".":
        flag=True
  else:
    print("Impossible")
    exit(0)
print("Possible")

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
prev=0
for i in range(H):
  s=input()
  id = s.index("#")
  if id >= prev:
    flag=False
    prev = id
    for j in range(prev,W):
      if flag and s[j]=="#":
        print("Impossible")
        exit(0)
      if s[j]==".":
        flag=True
print("Possible")

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
prev=0
for i in range(H):
  s=input()
  id = s.index("#")
  if id >= prev:
    for j in range(id,W):
      if s[j]!="#":
        print("Impossible")
        exit(0)
print("Possible")

Submission status: Wrong Answer

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

A = [[0]*(W) for j in range(H+1)]

for i in range (H):
    A[i]=list(input()+".")

i=0
j=0
A[0][0]=0
while(True):
    if((i==(H-1))and(j==(W-1))):
        if("#" in A):
            print("Impossible")
            exit()
        print("Possible")
        exit()
    if(A[i+1][j]=="#"):
        A[i+1][j]=0
        i+=1
    elif(A[i][j+1]=="#"):
        A[i][j+1]=0
        j+=1
    else:
        print("Impossible")
        exit()

Submission status: Wrong Answer

Solution code:
# -*-coding: utf-8 -*-
def check(A, h, w):
    cnt = 0
    if A[h-1][w] == "#":
        cnt += 1
    if A[h][w-1] == "#":
        cnt += 1
    if A[h][w+1] == "#":
        cnt += 1
    if A[h+1][w] == "#":
        cnt += 1
    return cnt

def main():
    H, W = map(int, input().split())
    A = ["." * (W+2)]
    for i in range(H):
        A.append("." + input() + ".")
    A.append("." * (W + 2))
    #print(A)
    ans = "Possible"
    for w in range(1, W+1):
        for h in range(1, H+1):
            if A[h][w] == "#":
                if w == h == 1:
                    pass
                elif h == H and w == W:
                    pass
                elif check(A, h, w) == 2:
                    if A[h-1][w] == A[h+1][w] == "#" and A[h][w-1] == A[h][w+1] == ".":     # 直線(縦)
                        pass
                    elif A[h-1][w] == A[h+1][w] == "." and A[h][w-1] == A[h][w+1] == "#":   # 直線(横)
                        pass
                    elif A[h-1][w] == A[h][w+1] == "#" and A[h+1][w] == A[h][w-1] == ".":   # L字
                        pass
                    elif A[h+1][w] == A[h][w-1] == "#" and A[h-1][w] == A[h][w+1] == ".":   # L時
                        pass
                    else:
                        ans = "Impossible"
                else:
                    ans = "Impossible"
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*-coding: utf-8 -*-
import math
def main():
    H, W = map(int, input().split())
    A = ["." * (W+2)]
    for i in range(H):
        A.append("." + input() + ".")
    A.append("." * (W + 2))
    #print(A)
    ans = "Possible"
    for w in range(1, W+1):
        for h in range(1, H+1):
            if A[h][w] == "#":
                if w == h == 1:
                    pass
                elif h == H and w == W:
                    pass
                else:
                    if A[h-1][w] == A[h+1][w] == "#" and A[h][w-1] == A[h][w+1] == ".":     # 直線(縦)
                        pass
                    elif A[h-1][w] == A[h+1][w] == "." and A[h][w-1] == A[h][w+1] == "#":   # 直線(横)
                        pass
                    elif A[h-1][w] == A[h][w+1] == "#" and A[h+1][w] == A[h][w-1] == ".":   # L字
                        pass
                    elif A[h+1][w] == A[h][w-1] == "#" and A[h-1][w] == A[h][w+1] == ".":   # L時
                        pass
                    else:
                        ans = "Impossible"
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def check(A, h, w):
    cnt = 0
    if A[h-1][w] == "#":
        cnt += 1
    if A[h][w-1] == "#":
        cnt += 1
    if A[h][w+1] == "#":
        cnt += 1
    if A[h+1][w] == "#":
        cnt += 1
    return cnt

H, W = map(int, input().split())
A = ["." * (W+2)]
for i in range(H):
    A.append("." + input() + ".")
A.append("." * (W + 2))
#print(A)
ans = "Possible"
for w in range(1, W+1):
    for h in range(1, H+1):
        if A[h][w] == "#":
            if h == 1 and w == 1:
                pass
            elif h == H and w == W:
                pass
            else:
                cnt = check(A, h, w)
                if cnt != 2:
                    ans = "Impossible"
                else:
                    if A[h-1][w] == "#" and A[h][w-1] == "#":
                        ans = "Impossible"
                    if A[h-1][w] == "#" and A[h][w-1] == "#":
                        ans = "Impossible"
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = ["." * (W+1)]
for i in range(H):
    A.append("." + input())
ans = "Possible"
for w in range(1, W+1):
    for h in range(1, H+1):
        if A[h][w] == "#":
            if h == 1 and w == 1:
                pass
            elif A[h][w-1] == "#" and A[h-1][w] == ".":
                pass
            elif A[h][w-1] == "." and A[h-1][w] == "#":
                pass
            else:
                ans = "Impossible"
                break
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = []
A.append("."*(W+1))
A = ["."+input() for _ in range(H)]
ans = "Possible"
for w in range(1, W):
    for h in range(1, H):
        if A[h][w] == "#":
            if h == 1 and w == 1:
                pass
            elif A[h][w-1] == "#" and A[h-1][w] == ".":
                pass
            elif A[h][w-1] == "." and A[h-1][w] == "#":
                pass
            else:
                ans = "Impossible"
                break
print(ans)