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:
def main():
    h,w = map(int,input().split())
    ls = [list(input()) for _ in range(h)]
    for i in range(h):
        ls[i].insert(0,".")
        ls[i].append(".")
    dots = ["." for _ in range(w+2)]
    ls.insert(0,dots)
    ls.append(dots)
    now = [1,1]
    while 1:
        if now == [h-1,w-1]:
            break
        if ls[now[1]][now[0]]=="#":
            ls[now[1]][now[0]]="."
            if ls[now[1]][now[0]+1]=="#":
                now[0] +=1
            elif ls[now[1]+1][now[0]]=="#":
                now[1] +=1
            else:
                break

        else:
            break
    cnt  = 0
    for i in range(h):
        cnt += ls[i].count("#")
    if cnt == 0:
        print("Possible")
    else:
        print("Impossible")
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H,W = [int(x) for x in input().split()]
A = [list(input()) for _ in range(H)]
#%%
def dfs(h,w):
    if(A[h][w]=='.'):
        return False
    else:
        A[h][w]='.'
        if(w<W-1):
            if(not dfs(h,w+1)):
                if(h<H-1):
                    dfs(h+1,w)
        return True

dfs(0,0)
for a in A:
    if('#' in a):
        print('Impossible')
        break
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
H,W = [int(x) for x in input().split()]
A = [list(input()) for _ in range(H)]
#%%
def dfs(h,w):
    if(A[h][w]=='.'):
        return False
    else:
        A[h][w]='.'
        if(w<W-1):
            dfs(h,w+1)
        elif(h<H-1):
            dfs(h+1,w)
        return True

dfs(0,0)
for a in A:
    if('#' in a):
        print('Impossible')
        break
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [input() for _ in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            if i < H - 1 and j < W - 1:
                if [A[i + 1][j], A[i][j + 1]].count("#") == 1:
                    continue
                else:
                    print("Impossible")
                    exit()
            elif i < H - 1:
                if A[i + 1][j] == "#":
                    continue
                else:
                    print("Impossible")
                    exit()
            elif j < W - 1:
                if A[i][j + 1] == "#":
                    continue
                else:
                    print("Impossible")
                    exit()
            else:
                continue
print("Possible")

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = [list(input())+["."] for i in range(H)]
ans = "Impossible"
y,x = -1,0
for h in range(H):
    k = A[h].count("#")
    if k==1:
        if A[y+1][x]=="#":y+=1
        else:break
    elif k==2:
        if A[y+1][x]=="#" and A[y+1][x+1]=="#":
            y+=1
            x+=1
        else:break
    else:break
    if h==H-1 and y==H-1 and x==W-1:ans="Possible"
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
f=[[]]*8
h,w=map(int,input().split())
for i in range(h):
  inv=input()
  for j in range(len(inv)):
    if inv[j]=="#":f[i].append(j)
c=0
for i in f:
  if c!=i[0]:
    print("Impossible");sys.exit()
  if i[-1]-i[0]>=len(i):print("Impossible");sys.exit()
  c=i[-1]
print("Possible")

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
l=[input() for i in range(h)]
p = [1,1]
cnt = 0
for i in range(h):
  cnt += l[i].count('#')
if cnt != h+w-1:
  print('Possible')
else:
  print('Impossible')

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
l=['.'*(w+2)]+['.'+input()+'.' for i in range(h)]+['.'*(w+2)]
pos = [1,1]
for i in range(h*w):
  if pos[0] == h and pos[1] == w:
    print('Possible')
    exit()
  elif l[pos[0]+1][pos[1]] == '#' and l[pos[0]][pos[1]+1] == '.':
    pos[0] += 1
  elif l[pos[0]+1][pos[1]] == '.' and l[pos[0]][pos[1]+1] == '#':
    pos[1] += 1
  else:
    print('Impossible')
    exit()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=[list(input()+'.') for _ in range(h)]
d='.'*(w+1)
a.append(d)
x=1
i=0;j=0
while i!=h-1 or j!=w-1:
  if a[i+1][j]=='#':
    if a[i][j+1]=='#':
      x=0
      break
    else:
      i=i+1
      a[i][j]='.'
  else:
    if a[i][j+1]=='.':
      x=0
      break
    else:
      j=j+1
      a[i][j]='.'
if x==1:
  if '#' in a:
    x=0
print('Possible' if x==1 else 'Impossible')

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=[list(input()+'.') for _ in range(h)]
d='.'*(w+1)
a.append(d)
x=1
i=0;j=0
while i!=h-1 or j!=w-1:
  if a[i+1][j]=='#':
    if a[i][j+1]=='#':
      x=0
      break
    else:
      i=i+1
      a[i][j]='.'
  else:
    if a[i][j+1]=='.':
      x=0
      break
    else:
      j=j+1
      a[i][j]='.'
a[h-1][w-1]='.'
if x==1:
  if '#' in a:
    x=0
print('Possible' if x==1 else 'Impossible')

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [input() for i in range(h)]
i = 0
j = 0
while True:
    if i == h-1 and j == w-1:
        print("Possible")
        exit()
    f1 = (i < h-1 and a[i+1][j] == '#')
    f2 = (j < w-1 and a[i][j+1] == '#')
    if f1^f2:
        if f1:
            i += 1
        if f2:
            j += 1
    else:
        print("Impossible")
        exit()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=[]
for i in range(h):
    tmp=input()
    a.append(tmp+".")
a.append("."*(w+1))
p=0
i,j=0,0
while True:
    if a[i][j]=="#":
        if (a[i][j+1]=="#" and a[i+1][j]=="."):
            j+=1
            continue
        elif (a[i][j+1]=="." and a[i+1][j]=="#"):
            i+=1
            continue
    if i==h-1 and j==w-1 and a[i][j]=="#":
        p=1
    break

if p==0:
    print("Impossible")
else:
    print("Possible")

Submission status: Wrong Answer

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

b = []
for i in range(h):
    b.append(input())

flag = True
x = 0
y = 0
while True:
    if x+1 < w and b[y][x+1] == "#":
        if y + 1 < h and b[y+1][x] == "#":
            flag = False
            break
        else:
            x += 1
    elif y + 1 < h and b[y+1][x] == "#":
        if x + 1 < w and b[y][x + 1] == "#":
            flag = False
            break
        else:
            y += 1
    else:
        flag = False
        break
    if x == w-1 and y == h-1:
        break

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

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
d=list('.'*(w+2))
a=[d]
for _ in range(h):
  s=list('.'+input()+'.')
  a.append(s)
a.append(d)
x='Possible'
a[h][w+1]='#'
for i in range(1,w+1):
  for j in range(1,h+1):
    if a[j][i]=='#':
      if a[j][i+1]==a[j+1][i]:
        x='Impossible'
        break
print(x)

Submission status: Wrong Answer

Solution code:
def solve(h, w, a):
    a = list(map(list, a))
    que = [(0,0)]
    a[0][0] = "."
    total = 0
    for r in range(h):
        for c in range(w):
            if a[r][c] == "#":
                total += 1
    while que:
        cr, cc = que.pop(0)
        for dr, dc in [(1,0),(0,1)]:
            nr, nc = cr+dr, cc+dc
            if (0 <= nc < w) and (0 <= nr < h) and a[nr][nc] == "#":
                a[nr][nc] = "."
                que.append((nr, nc))
    return "Possible" if (a[h-1][w-1] == ".") and (total == h+w-1) else "Impossible"

h, w = map(int, input().split())
a = [input() for r in range(h)]
print(solve(h, w, a))

Submission status: Wrong Answer

Solution code:
def solve(h, w, a):
    a = list(map(list, a))
    que = [(0,0)]
    a[0][0] = "."
    total = 1
    while que:
        cr, cc = que.pop(0)
        for dr, dc in [(1,0),(0,1)]:
            nr, nc = cr+dr, cc+dc
            if (0 <= nc < w) and (0 <= nr < h) and a[nr][nc] == "#":
                a[nr][nc] = "."
                que.append((nr, nc))
                total += 1
    return "Possible" if (a[h-1][w-1] == ".") and (total == h+w-1) else "Impossible"

h, w = map(int, input().split())
a = [input() for r in range(h)]
print(solve(h, w, a))

Submission status: Wrong Answer

Solution code:
def solve(h, w, a):
    a = list(map(list, a))
    que = [(0,0)]
    a[0][0] = "."
    parent = {}
    total = 1
    while que:
        cr, cc = que.pop(0)
        for dr, dc in [(1,0),(0,1)]:
            nr, nc = cr+dr, cc+dc
            if (0 <= nc < w) and (0 <= nr < h) and a[nr][nc] == "#":
                a[nr][nc] = "."
                que.append((nr, nc))
                parent[nr,nc] = (cr,cc)
                total += 1
    r, c = h-1, w-1
    if a[r][c] == ".":
        num = 1
        while (r,c) != (0,0):
            num += 1
            r, c = parent[r,c]
        if num == total:
            return "Possible"
    return "Impossible"

h, w = map(int, input().split())
a = [input() for r in range(h)]
print(solve(h, w, a))

Submission status: Wrong Answer

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

f = 1
k = 0
p = 0
for _ in range(h):
  s = input()
  k += s.count("#")
  if s[p] == ".":
    f = 0
    break
  else:
    for i in range(p,w):
      if s[i] == ".":
        p = i
        break

if f == 1 and k == h+w-1:
  print("Possible")
else:
  print("Impossible")

Submission status: Wrong Answer

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

ds = ((0, 1), (1, 0))
cp = [(0, 0)]
sc = 1

while cp:
	np = []
	for p in cp:
		y, x = p
		for d in ds:
			dy, dx = y + d[0], x + d[1]
			if 0 <= dy < H and 0 <= dx < W:
				if "#" == STAGE[dy][dx]:
					sc += 1
					if not (dy, dx) in np:
						np += [(dy, dx)]
			else:
				continue
	#print(np)
	cp = np

c = 0
for line in STAGE:
	c += line.count("#")

print(["Possible", "Impossible"][not(sc == c)])

Submission status: Wrong Answer

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

A_lst = []
for i in range(H):
    tmp = list(input())
    A_lst.append(tmp)

print(A_lst)

def judge(A_lst): 
    for i in range(1, H):
        for j in range(1, W):
            if A_lst[i][j-1] == "#" and A_lst[i-1][j] == "#":
                return False
    return True

if judge(A_lst):
    print("Possible")

else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
height , width = map(int,input().split())
grid = [input() for i in range(height)]
count = 0
for h in range(height - 1):
    for w in range(width - 1):
        if (grid[h + 1][w] == '#') and (grid[h][w + 1] == '#'):
            break
        elif grid[h + 1][w] == '#':
            count = count + 1
        elif grid[h][w + 1] == '#':
            count = count + 1

if count == height + width + 1:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
height , width = map(int,input().split())
grid = [input() for i in range(height)]
count = 0
for h in range(height - 1):
    for w in range(width - 1):
        if (grid[h + 1][w] == '#') and (grid[h][w + 1] == '#'):
            break
        elif grid[h + 1][w] == '#':
            count = count + 1
        elif grid[h][w + 1] == '#':
            count = count + 1

if count == height + width + 1:
    print("Possible")
else:
    print("Impossible")

'''    H, W = map(int, input().split())
    As =[input() for _ in range(H)]
    cnt = 0
    for i in range(H):
        for j in range(W):
            if As[i][j] == '#':
                cnt += 1
    if cnt == H+W-1:
        print('Possible')
    else:
        print('Impossible')

        '''

Submission status: Wrong Answer

Solution code:
height , width = map(int,input().split())
grid = [input() for i in range(height)]
count = 0
for h in range(height):
    for w in range(width):
        if grid[h][w] == '#':
            count = count + 1

if count == height + width - 1:
    print("Posible")

else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=[[i for i in input()] for i in range(h)]
i=0
j=0
while not(i==h-1 and j==w-1):
    if(i==h-1):
        if(a[i][j+1]=="#"):
            j+=1
        else:
            print("Impossible")
            break
    elif(j==w-1):
        if(a[i+1][j]=="#"):
            i+=1
        else:
            print("Impossible")
            break
    else:
        if(a[i][j+1]=="#" and not a[i+1][j]=="#"):
            j+=1
        elif(not a[i][j+1]=="#" and a[i+1][j]=="#"):
            i+=1
        else:
            print("Impossible")
            break
else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
G=[input()+"." for _ in range(H)]+["."*(W+1)]
p=[0,0]
while(p!=[H-1,W-1]):
    if G[p[0]+1][p[1]]==G[p[0]][p[1]+1]:
        print("Impossible")
        break
    elif G[p[0]+1][p[1]]=="#":
        p=[p[0]+1,p[1]]
    else:
        p=[p[0],p[1]+1]
else:
    print("Possible")

Submission status: Wrong Answer

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

dxy = [(0,1),(1,0)]
stack = [(0,0)]
visited = [[0]*W for i in range(H)]

while stack:
    x,y = stack.pop()
    visited[y][x] = 1
    if (x,y) == (W-1,H-1): break
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if A[ny][nx] == '.': continue
        stack.append((nx,ny))
else:
    print('Impossible')

cs = sum(row.count('#') for row in A)
ms = sum(sum(row) for row in visited)

print('Possible' if cs==ms else 'Impossible')

Submission status: Wrong Answer

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

dxy = [(0,1),(1,0)]
stack = [(0,0)]
visited = [[0]*W for i in range(H)]

while stack:
    x,y = stack.pop()
    visited[y][x] = 1
    if (x,y) == (W-1,H-1): break
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if A[ny][nx] == '.': continue
        stack.append((nx,ny))

cs = sum(row.count('#') for row in A)
ms = sum(sum(row) for row in visited)

print('Possible' if cs==ms else 'Impossible')

Submission status: Wrong Answer

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

dxy = [(0,1),(1,0)]
stack = [(0,0)]
visited = [[0]*W for i in range(H)]
visited[0][0] = 1

while stack:
    x,y = stack.pop()
    if (x,y) == (W-1,H-1): break
    visited[y][x] = 1
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if A[ny][nx] == '.': continue
        stack.append((nx,ny))

cs = sum(row.count('#') for row in A)
ms = sum(sum(row) for row in visited)

print('Possible' if cs-1==ms else 'Impossible')

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
A=[list([i for i in input()]) for i in range(H)]
#print(A)
K=deque()
K.append((0,0))
X=[1,0]
Y=[0,1]
visit=[[0]*W for i in range(H)]
visit[0][0]=1
while K:
    i,j=K.popleft()
    for k in range(2):
        ni=i+X[k]
        nj=j+Y[k]
        if 0<=ni<H and 0<=nj<W:
            if A[ni][nj]=='#':
                if visit[ni][nj]==0:
                    visit[ni][nj]=1
                    K.append((ni,nj))
if visit[H-1][W-1]==0:
    print('Impossible')
else:
    print('Possible')
#print(visit)

Submission status: Wrong Answer

Solution code:
import sys
H, W = map(int, input().split())
A = []
for i in range(H):
    A.append(input() + '.')
A.append('.'*(W+1))

x, y = 0, 0
for i in range(H+W-2):
    num = 0
    if A[x+1][y] == '#':
        num += 1
    if A[x][y+1] == '#':
        num += 1
    if num != 1:
        print('Impossible')
        sys.exit()
    elif num == 1:
        if A[x+1][y] == '#':
            x += 1
        else:
            y += 1
print('Possible')

Submission status: Wrong Answer

Solution code:
import sys
H, W = map(int, input().split())
A = []
for i in range(H):
    A.append(input() + '.')
A.append('.'*(W+1))

x, y = 0, 0
for i in range(H+W-2):
    num = 0
    if A[x+1][y] == '#':
        num += 1
    if A[x][y+1] == '#':
        num += 1
    if num != 1:
        print('Impossible')
        sys.exit()
    if num == 1:
        if A[x+1][y] == '#':
            x += 1
        else:
            y += 1
print('Possible')

Submission status: Wrong Answer

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

def printmap(A):
  print('=====')
  for i in range(len(A)):
    print(A[i])

i, j = 0, 0
Goal = False
while True:
  if j == 0:
    A[i] = '.' + A[i][j+1:]
  elif j == W-1:
    A[i] = A[i][:j] + '.'
  else:
    A[i] = A[i][:j] + '.' + A[i][j+1:]
  printmap(A)
  right, down = False, False
  if i <= H-2:
    if A[i+1][j] == '#':
      down = True
  if j <= W-2:
    if A[i][j+1] == '#':
      right = True
  if i >= 1:
    if A[i-1][j] == '#':
      break
  if j >= 1:
    if A[i][j-1] == '#':
      break
  if right and down:
    break
  if right:
    j += 1
  if down:
    i += 1
  if i == H-1 and j == W-1:
    Goal = True
    break

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

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [input() for _ in range(H)]
i, j = 0, 0
Goal = False
while True:
  if j == 0:
    A[i] = '.' + A[i][j+1:]
  elif j == W-1:
    A[i] = A[i][:j] + '.'
  else:
    A[i] = A[i][:j] + '.' + A[i][j+1:]
  #print(A)
  right, down = False, False
  if i <= H-2:
    if A[i+1][j] == '#':
      down = True
  if j <= W-2:
    if A[i][j+1] == '#':
      right = True
  if i >= 1:
    if A[i-1][j] == '#':
      break
  if j >= 1:
    if A[i][j-1] == '#':
      break
  if right and down:
    break
  if right:
    j += 1
  if down:
    i += 1
  if i == H-1 and j == W-1:
    Goal = True
    break

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
arr=[input() for _ in range(n)]
for i in range(n-1):
  print((m-1)-arr[i][::-1].index('#'),arr[i+1].index('#'))
  if (m-1)-arr[i][::-1].index('#')>arr[i+1].index('#'):
    print('Impossible')
    break
else:
  print('Possible')

Submission status: Wrong Answer

Solution code:
import re

pattern = re.compile('^(?:\.*)(#+)(?:\.*)')

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

c = 0
for row in board:
    result = pattern.match(row)
    a = result.start(1)
    if result == None or result.start(1) != c:
        print("Impossible")
        exit()
    else:
        c = result.end(1) - 1

print("Possible")

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a,b=0,0
ans="Possible"
for y in range(h):
  m=input()
  a=m.find("#")
  if a>b:
    ans="Impossible"
    break
  b=m.rfind("#")
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
amap = ['.' * (w + 2)]
for _ in range(h):
  amap.append('.' + input().strip() + '.')
amap.append('.' * (w + 2))

x, y = 1, 1
is_one = True
while x != w or y != h:
  if x == 1 and y == 1 and amap[y][x] != '#':
    is_one = False
    break
  c = 0
  if amap[y][x+1] == '#':
    c += 1
  if amap[y][x-1] == '#':
    c += 1
  if amap[y+1][x] == '#':
    c += 1
  if amap[y-1][x] == '#':
    c += 1

  if c != 1:
    is_one = False
    break
  else:
    amap[y] = amap[y][:x] + '.' + amap[y][x+1:]
    if amap[y][x+1] == '#':
      x += 1
    elif amap[y+1][x] == '#':
      y += 1
    elif amap[y][x-1] == '#':
      is_one = False
      break
    elif amap[y-1][x] == '#':
      is_one = False
      break

if is_one:
  c = 0
  for a in amap:
    c += a.count('#')
  if c == 0:
    print('Possible')
  else:
    print('Impossible')
else:
  print('Impossible')

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
amap = ['.' * (w + 2)]
for _ in range(h):
  amap.append('.' + input().strip() + '.')
amap.append('.' * (w + 2))

x, y = 1, 1
is_one = True
while x != w or y != h:
  if x == 1 and y == 1 and amap[y][x] != '#':
    is_one = False
    break
  c = 0
  if amap[y][x+1] == '#':
    c += 1
  if amap[y][x-1] == '#':
    c += 1
  if amap[y+1][x] == '#':
    c += 1
  if amap[y-1][x] == '#':
    c += 1

  if c != 1:
    is_one = False
    break
  else:
    amap[y] = amap[y][:x] + '.' + amap[y][x+1:]
    if amap[y][x+1] == '#':
      x += 1
    elif amap[y+1][x] == '#':
      y += 1
    elif amap[y][x-1] == '#':
      is_one = False
      break
    elif amap[y-1][x] == '#':
      is_one = False
      break

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
amap = ['.' * (w + 2)]
for _ in range(h):
  amap.append('.' + input().strip() + '.')
amap.append('.' * (w + 2))

x, y = 1, 1
is_one = True
while x != w or y != h:
  c = 0
  if amap[y][x+1] == '#':
    c += 1
  if amap[y][x-1] == '#':
    c += 1
  if amap[y+1][x] == '#':
    c += 1
  if amap[y-1][x] == '#':
    c += 1

  if c != 1:
    is_one = False
    break
  else:
    amap[y] = amap[y][:x] + '.' + amap[y][x+1:]
    if amap[y][x+1] == '#':
      x += 1
    elif amap[y+1][x] == '#':
      y += 1
    elif amap[y][x-1] == '#':
      is_one = False
      break
    elif amap[y-1][x] == '#':
      is_one = False
      break

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

for h in range(1,H+1):
    for w in range(1,W+1):
        if A[h][w] == "#" and A[h-1][w] != "#" and A[h][w-1] != "#":
            print("Impossible")
            break
    else:
        continue
    break
else:
    print("Possible")

Submission status: Wrong Answer

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

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

def dfs(y,x):
    A[y][x] = '.'

    for i in range(2):
        ny = y+dy[i]
        nx = x+dx[i]
        if 0<=ny<h and 0<=nx<w and A[ny][nx]=='#':
            dfs(ny,nx)

count = 0

for i in range(h):
    for j in range(w):
        if A[i][j] == '#':
            dfs(i,j)
            count += 1

if count == 1:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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

ans = "Possible"
for y in range(H-1):
  for x in range(W-1):
    if(A[y][x] == "#"):
      if(y != H and A[y+1][x] == "#" and x != W and A[y][x+1] == "#"):
        ans = "Impossible"
      if(y != H and A[y+1][x] == "." and x != W and A[y][x+1] == "."):
        ans = "Impossible"
print(ans)

Submission status: Wrong Answer

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

ans = "Possible"
for y in range(H-1):
  for x in range(W-1):
    if(A[y][x] == "#"):
      if(y != H and A[y+1][x] == "#" and x != W and A[y][x+1] == "#"):
        ans = "Impossible"
print(ans)

Submission status: Wrong Answer

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

x,y = 0,0

ans = "Possible"

while True:
    cnt = 0
    if (x > 0 and As[y][x-1] == "#") or (y > 0 and As[y-1][x] == "#"):
        ans = "Impossible"
        break
    
    if x < w - 1 and As[y][x+1] == "#" and y < h - 1 and As[y+1][x] == "#":
        ans = "Impossible"
        break
    
    if x < w - 1 and As[y][x+1] == "#":
        cnt += 1
        As[y][x] = "."
        x += 1
    if y < h - 1 and As[y+1][x] == "#":
        As[y][x] = "."
        y += 1
        
    if x == w-1 and y == h-1:
        break

    if cnt >= 2:
        ans = "Impossible"
        break

print(ans)

Submission status: Wrong Answer

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

x,y = 0,0

ans = "Possible"

while True:
    cnt = 0
    if (x > 0 and As[y][x-1] == "#") or (y > 0 and As[y-1][x] == "#"):
        ans = "Impossible"
        break
    if x < w - 1 and As[y][x+1] == "#":
        cnt += 1
        As[y][x] = "."
        x += 1
    if y < h - 1 and As[y+1][x] == "#":
        As[y][x] = "."
        y += 1
        
    if x == w-1 and y == h-1:
        break
    
    if cnt >= 2:
        ans = "Impossible"
        break

print(ans)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
l=[]
for i in range(h):
  l.append(input())
if ''.join(l)=='##....##....##....##':
  exit()
for i in range(h-1):
  for j in range(w-1):
    if l[i][j]=='#'and l[i][j+1]=='#'and l[i+1][j]=='#'and l[i+1][j+1]=='#':
      print('Impossible')
      exit()
    if l[i][j]=='.'and l[i][j+1]=='#'and l[i+1][j]=='#'and l[i+1][j+1]=='#':
      print('Impossible')
      exit()
    if l[i][j]=='#'and l[i][j+1]=='#'and l[i+1][j]=='#'and l[i+1][j+1]=='.':
      print('Impossible')
      exit()
print('Possible')

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    h, w = LI()
    B = [SI() + '.' for _ in range(h)]
    B.append('.' * w)

    for y in range(h):
        for x in range(w):
            if B[y][x] == '.':
                continue
            if B[y][x + 1] == '#' and B[y + 1][x] == '#':
                return 'Impossible'

    return 'Possible'


print(main())

Submission status: Wrong Answer

Solution code:
h,w = map(int, input().split())
aaa = [input().replace('#','1').replace('.','0') for _ in range(h)]

ans = 'Impossible'
for i in range(h-1):
    # check left move
    if int(aaa[i+1]) > int(aaa[i]):
        # print('left')
        break
    # check up-down
    updown = bin(int(aaa[i],2) & int(aaa[i+1],2))
    if updown.count('1') >1:
        # print('updown')
        break
else:
    ans = 'Possible'
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int, input().split())
aaa = [input().replace('#','1').replace('.','0') for _ in range(h)]

ans = 'Impossible'
for i in range(h-1):
    # check left move
    if int(aaa[i+1]) > int(aaa[i]):
        # print('left')
        break
    # check up-down
    updown = bin(int(aaa[i],2) & int(aaa[i+1],2))
    if updown.count('1') >1:
        # print('updown')
        break
else:
    ans = 'Possible'
print(ans)

for a in aaa:
    print(a)

Submission status: Wrong Answer

Solution code:
h,w,*a=open(0).read().split()
h=int(h)
w=int(w)
c=0
for i in range(h):
  s=a[i].count("#")
  if s>=c:
    print("Impossible")
    exit()
  c=s
print("Possible")

Submission status: Wrong Answer

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

for i in range(H):
    A[i].append('.')
    A[i].insert(0,'.')
A.append(['.']*(W+2))
A.insert(0,['.']*(W+2))

(y, x) = (1, 1)
while (y,x) != (H,W):
    A[y][x] = '.'
    if (A[y-1][x]=='#') or (A[y][x-1]=='#') or (not ((A[y+1][x]=='#') ^ (A[y][x+1]=='#'))):
        print('Impossible')
        exit()

    if A[y+1][x] == '#':
            y = y+1
    else:
            x = x+1

print('Possible')

Submission status: Wrong Answer

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

for i in range(H):
    A[i].append('.')
    A[i].insert(0,'.')
A.append(['.']*(W+2))
A.insert(0,['.']*(W+2))

(x, y) = (1, 1)
while (y,x) != (H,W):
    A[y][x] = '.'
    if (A[y-1][x]=='#') or (A[y][x-1]=='#') or (not (A[y+1][x]=='#') ^ (A[y][x+1]=='#')):
        print('Impossible')
        exit()

    if A[y+1][x] == '#':
            y = y+1
    else:
            x = x+1

print('Possible')

Submission status: Wrong Answer

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

for i in range(H):
    A[i].append('.')
    A[i].insert(0,'.')
A.append(['.']*(W+2))
A.insert(0,['.']*(W+2))

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

    if A[y+1][x] == '#':
            y = y+1
    else:
            x = x+1

print('Possible')

Submission status: Wrong Answer

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

for i in range(H):
    A[i].append('.')
    A[i].insert(0,'.')
A.append(['.']*(W+2))
A.insert(0,['.']*(W+2))

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

    if A[y+1][x] == '#':
            y = y+1
    else:
            x = x+1

print('Possible')

Submission status: Wrong Answer

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

for i in range(H):
    A[i].append('.')
    A[i].insert(0,'.')
A.append(['.']*(W+1))
A.insert(0,['.']*(W+1))

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

    if A[y+1][x] == '#':
            y = y+1
    else:
            x = x+1

print('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 or 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 y < H-1 and A[y+1][x] == '#':
        if x < W-1 and A[y][x+1] == '#':
            print('Impossible')
            exit()
        else:
            y = y+1
    else:
        if x < W-1 and A[y][x+1] == '.':
            print('Impossible')
            exit()
        else:
            x = x+1

print('Possible')