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 dfs(grid, start, wall, h, w):
    stack = []
    push, pop = stack.append, stack.pop
    push(start)
    grid[start[0]][start[1]] = wall
    dxy = [(0,1), (1,0)]

    while stack:
        h, w = pop()
        for dx,dy in dxy:
            x, y = w+dx, h+dy
            if grid[y][x] == wall:
                continue
            push((y,x))
            grid[y][x] = wall
            break
    for i in range(1, h+1):
        for j in range(1, w+1):
            if grid[i][j] != wall:
                return False
    return True


def resolve():
    h, w = map(int, input().split())
    grid = {}
    wall = '.'
    edges = [wall] * (w+2)
    grid = [edges]
    for i in range(h):
        s = input()
        grid.append([wall] + list(s) + [wall])
    grid.append(edges)
    print("Possible" if dfs(grid, (1, 1), wall, h, w) else "Impossible")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def dfs(x,y):
    if x == W-1 and y == H-1:
        return print('Possible')
    if x+1 != W and A[y][x+1] == '#':
        if y+1 != H and A[y+1][x] == '#':
            print('Impossible')
            sys.exit()
        dfs(x+1, y)
    elif y+1 != H and A[y+1][x] == '#':
        dfs(x, y+1)
    else:
        print('Impossible')
        sys.exit()
    return

if __name__ == '__main__':
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for i in range(H) ]
    dfs(0, 0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def dfs(x,y):
    if x == W-1 and y == H-1:
        return print('Possible')
    if x+1 != W-1 and A[y][x+1] == '#':
        if y+1 != H-1 and A[y+1][x] == '#':
            print('Impossible')
            sys.exit()
        dfs(x+1, y)
    elif y+1 != H-1 and A[y+1][x] == '#':
        dfs(x, y+1)
    else:
        print('Impossible')
        sys.exit()
    return

if __name__ == '__main__':
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for i in range(H) ]
    dfs(0, 0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def dfs(x,y):
    if x == W-1 and y == H-1:
        return print('Possible')
    if x+1 != W-1 and A[y][x+1] == '#':
        if y+1 != H-1 and A[y+1][x] == '#':
            print('Impossible')
            sys.exit()
        dfs(x+1, y)
    if y+1 != H-1 and A[y+1][x] == '#':
        dfs(x, y+1)
    else:
        print('Impossible')
        sys.exit()
    return

if __name__ == '__main__':
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for i in range(H) ]
    dfs(0, 0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def dfs(x,y):
    if x == W-1 and y == H-1:
        return print('Possible')
    if x+1 != W and A[y][x+1] == '#':
        if y+1 != H and A[y+1][x] == '#':
            print('Impossible')
            sys.exit()
        dfs(x+1, y)
    if y+1 != H and A[y+1][x] == '#':
        dfs(x, y+1)
    else:
        print('Impossible')
        sys.exit()
    return

if __name__ == '__main__':
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for i in range(H) ]
    dfs(0, 0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def dfs(x,y):
    if x == W-1 and y == H-1:
        return print('Possible')
    if x+1 != W and A[y][x+1] == '#':
        if y+1 != H and A[y+1][x] == '#':
            return print('Impossible')
        dfs(x+1, y)
    if y+1 != H and A[y+1][x] == '#':
        dfs(x, y+1)
    else:
        print('Impossible')
        sys.exit()
    return

if __name__ == '__main__':
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for i in range(H) ]
    dfs(0, 0)

Submission status: Wrong Answer

Solution code:
def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["#","#"]:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
        for k in range(w):
            if a[i][k] == "#":
                if a[i+1][k-1:k] == ["#","#"]:
                    print("Impossible")
                    exit()
    if a[h-2][-1] == "#":
        if a[h-1][-2] == "#":
            print("Impossible")
            exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["#","#"]:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
    if a[h-2][-1] == "#":
        if a[h-1][-2] == "#":
            print("Impossible")
            exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
S=[]
for _ in range(H):
    s=input()
    s=[a for a in s]
    S.append(s)
visited=[[-1 for _ in range(W)] for _ in range(H)]
visited[0][0]=1
stack=[[0,0]]
answer=0
while len(stack)>0:
    h,w=stack.pop()
    for x,y in ([0,1],[0,-1],[1,0],[-1,0]):
        new_w=w+x
        new_h=h+y
        if new_w<0 or new_w>=W or new_h<0 or new_h>=H:
            continue
        elif visited[new_h][new_w]==-1 and S[new_h][new_w]=='#':
            visited[new_h][new_w]=1
            stack.insert(0,[new_w,new_h])
            if x==-1 and y==0:
                answer=1
                break
            elif x==0 and y==-1:
                answer=1
                break
if answer==0:
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["#","#"]:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
        for j in range(w-2):
            if a[i][j:j+3] == ["#","#","#"]:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["#","#"]:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
            if a[i][j:j+3] == ["#","#","#"] and w > 2:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["#","#"]:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["#","#"]:
                print("!!")
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
def BFS(x,y):
  flag=False
  qu=deque([])
  qu.append([x,y])
  
  while len(qu)!=0:
    d=qu.popleft()
    now_x,now_y=d[0],d[1]
    #print(now_x,now_y)
    #print(now_x==w-1 and now_y==h-1)
    if now_x==w-1 and now_y==h-1:
      flag=True
      return flag
      
    if now_y<h-1 and a[now_y+1][now_x]=="#":
      qu.append([now_x,now_y+1])
    if now_x<w-1 and a[now_y][now_x+1]=="#":
      qu.append([now_x+1,now_y])
    if now_y<h-1 and a[now_y+1][now_x]=="#" and now_x<w-1 and a[now_y][now_x+1]=="#":
      return flag
  return flag
flag=BFS(0,0)
if flag:
  print("Possible")
else:
  print("Impossible")

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
def BFS(x,y):
  flag=False
  qu=deque([])
  qu.append([x,y])
  
  while len(qu)!=0:
    d=qu.popleft()
    now_x,now_y=d[0],d[1]
    #print(now_x,now_y)
    #print(now_x==w-1 and now_y==h-1)
    if now_x==w-1 and now_y==h-1:
      flag=True
      return flag
      
    if now_y<h-1 and a[now_y+1][now_x]=="#":
      qu.append([now_x,now_y+1])
    if now_x<w-1 and a[now_y][now_x+1]=="#":
      qu.append([now_x+1,now_y])
    if now_y<h-1 and a[now_y+1][now_x]=="#" and now_x<w-1 and a[now_y][now_x+1]=="#":
      return flag
  return flag
flag=BFS(0,0)
if flag:
  print("possible")
else:
  print("Impossible")

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
step = H+W-2
A = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  A.append(temp)
now = (0,0) #H,W
for i in range(step):
  Flag = False
  r = (now[0],now[1]+1)
  b = (now[0]+1,now[1])
  #print(now,r,b)
  if r[1] >= W:
    if A[b[0]][b[1]] == "#":
      now = b
      continue
    else:
      print("Impossible")
      exit()
  elif b[0] >= H:
    if A[r[0]][r[1]] == "#":
      now = r
      continue
    else:
      print("Impossible")
      exit()
  elif A[b[0]][b[1]] == "#" and A[r[0]][r[1]] == "#":
    print("Impossible")
    exit()
  elif A[b[0]][b[1]] == "." and A[r[0]][r[1]] == ".":
    print("Impossible")
    exit()
  elif A[b[0]][b[1]] == "#":
    now = b
    continue
  elif A[r[0]][r[1]] == "#":
    now = r
    continue
  else:
    print("Impossible")
    exit()
print("Possible")

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
M = [list(str(input())) for _ in range(H)]

def dfs(x, y):
    if x==W-1 and y==H-1:
        return 1
    ret = 0
    if x+1<W and M[y][x+1]=='#':
        ret += dfs(x+1, y)
    if y+1<H and M[y+1][x]=="#":
        ret += dfs(x, y+1)
    return ret

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve():
    n, m = getList()
    tmp = 0
    for i in range(n):
        s = getS()
        stop = False
        for i, c in enumerate(s):
            if i < tmp:
                if c == "#":
                    print("Impossible")
                    return
            else:
                if not stop:
                    if c == ".":
                        stop = True
                        tmp = i-1
                else:
                    if c == "#":
                        print("Impossible")
                        return

    print("Possible")
    return



    nums = getList()

    ans = 0
    for i, num in enumerate(nums):
        ans += 2 * (min(abs(k - num), num))


    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def dfs(x,y,cnt):
    cnt += 1
    if x == W-1 and y == H-1:
        # return print("Possible")
        return cnt
    if x+1 != W and A[y][x+1] == '#':
        cnt =dfs(x+1, y, cnt)
    if y+1 != H and A[y+1][x] == '#':
        cnt = dfs(x, y+1, cnt)
    return cnt

if __name__ == '__main__':
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for i in range(H) ]
    cnt = 0
    cnt = dfs(0, 0, cnt)
    if cnt == H+W:
        print('Possible')
    else:
        print('Impossible')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def dfs(x,y,cnt):
    cnt += 1
    if x == W-1 and y == H-1:
        # return print("Possible")
        return cnt
    if x+1 != W and A[y][x+1] == '#':
        cnt =dfs(x+1, y, cnt)
    if y+1 != H and A[y+1][x] == '#':
        cnt = dfs(x, y+1, cnt)
    return cnt

if __name__ == '__main__':
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for i in range(H) ]
    print(A)
    cnt = 0
    cnt = dfs(0, 0, cnt)
    if cnt == H+W:
        print('Possible')
    else:
        print('Impossible')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def dfs(x,y,cnt):
    cnt += 1
    print(cnt)
    if x == W-1 and y == H-1:
        # return print("Possible")
        return cnt
    if x+1 != W and A[y][x+1] == '#':
        cnt =dfs(x+1, y, cnt)
    if y+1 != H and A[y+1][x] == '#':
        cnt = dfs(x, y+1, cnt)
    return cnt

if __name__ == '__main__':
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for i in range(H) ]
    print(A)
    cnt = 0
    cnt = dfs(0, 0, cnt)
    if cnt == H+W:
        print('Possible')
    else:
        print('Impossible')

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
L = []
for i in range(h):
    L.append(list(input()))
    
from collections import deque
from copy import deepcopy

d = [[False]*w for i in range(h)]
visited = [[False]*w for i in range(h)]
q = deque([])
move = ((1,0),(0,1))
for y in range(h):
    for x in range(w):
        #print(x,y)
        co = deepcopy(L)
        if co[y][x] == "#":
            co[y][x] = "."
        visited[y][x] = True
        q.append((y,x))
        while q:
            #print(q)
            q.popleft()
            for dy,dx in move:
                ny,nx = y +dy,x+dx
                if ny<0 or ny>=h or nx<0 or nx>=w or visited == True:
                    continue
                if co[ny][nx] == "#":
                    co[ny][nx] = "."
                    visited[ny][nx] = True
                    #print(visited)
                    q.append((ny,nx))
                #print(q)
        if [all(co[i][j] =="." for i in range(len(co)) for j in range(len(co[i])))]:
            print("Possible")
            exit()
print("Impossible")

Submission status: Wrong Answer

Solution code:
def check(grid, h, w):
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                return False
    return True


def main():
    h, w = map(int, input().split())

    grid = []
    for _ in range(h):
        grid.append(list(input()))
    # 右、下、左、上
    dy = [0, 1]
    dx = [1, 0]
    stack = [[0, 0]]
    grid[0][0] = 'D'
    while stack:
        y, x = stack.pop()
        for i in range(2):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if 0 <= next_y < h and 0 <= next_x < w and grid[next_y][next_x] == '#':
                grid[next_y][next_x] = 'D'
                stack.append([next_y, next_x])
                break
    print(grid)
    if check(grid, h, w):
        print('Possible')
        return
    print('Impossible')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def check(grid, h, w):
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                return False
    return True


def main():
    h, w = map(int, input().split())

    grid = []
    for _ in range(h):
        grid.append(list(input()))
    # 右、下、左、上
    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    stack = [[0, 0]]
    grid[0][0] = 'D'
    while stack:
        y, x = stack.pop()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if 0 <= next_y < h and 0 <= next_x < w and grid[next_y][next_x] == '#':
                if i not in frozenset([0, 1]):
                    print('Impossible')
                    return
                grid[next_y][next_x] = 'D'
                stack.append([next_y, next_x])
    if check(grid, h, w):
        print('Possible')
        return
    print('Impossible')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    grid = []
    for _ in range(h):
        grid.append(list(input()))
    # 右、下、左、上
    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    stack = [[0, 0]]
    grid[0][0] = 'D'
    while stack:
        y, x = stack.pop()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if 0 <= next_y < h and 0 <= next_x < w and grid[next_y][next_x] == '#':
                if i not in frozenset([0, 1]):
                    print('Impossible')
                    return
                grid[next_y][next_x] = 'D'
                stack.append([next_y, next_x])
    if grid[h - 1][w - 1] == 'D':
        print('Possible')
    else:
        print('Impossible')

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def dfs(h,w,c):
  if h == H - 1 and w == W - 1:
    return c + 1

  if H - 1 < h or W -1 < w:
    return 0
  
  if GRID[h][w] != "#":
    return 0
  
  
  right = dfs(h+1,w,c+1)
  down = dfs(h,w+1,c+1)
  c += max(right,down)

  return c

NUM = sum([GRID[x].count("#") for x in range(H)])

n = dfs(0,0,0)

if n == NUM:
  print("Possible")
else:
  print("Impossible")

Submission status: Wrong Answer

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

tmp = 0

for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            if j < tmp:
                print("Impossible")
                exit()
            else:
                tmp = j
        print(tmp)

print("Possible")

Submission status: Wrong Answer

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

a = [list(input()) for _ in range(h)]
Pass = True
for x in range(h-1):
    for y in range(w-1):
        if a[x][y] == '#':
            if a[x+1][y] == a[x][y+1]:
                Pass = False

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

Submission status: Wrong Answer

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

a = [list(input()) for _ in range(h)]
Pass = True
for x in range(h-1):
    for y in range(w-1):
        if a[x][y] == '#':
            if a[x+1][y] == '#' and a[x][y+1] == '#':
                Pass = False

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

Submission status: Wrong Answer

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

ans='Possible'
for i in range(h-1):
    for j in range(w-1):
        if r[i][j]=='#'and r[i][j+1]=='#' and r[i+1][j]=='#' and r[i+1][j+1]=='#':
            ans='Impossible'
        elif r[i][j]=='.' and r[i][j+1]=='#' and r[i+1][j]=='#' and r[i+1][j+1]=='#':
            ans='Impossible'

print(ans)

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
A=[input() for i in range(H)]
p=0
for i in range(H):
    if A[i][p]==".":
        print("Impossible")
        break
    for j in range(p,W):
        if A[i][j]=="#":
            A[i]=A[i][:j]+"."+A[i][j+1:]
        else:
            p=j-1
            break
    if "#" in A[i]:
        print("Impossible")
        exit()
else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
A=[input() for i in range(H)]
p=0
for i in range(H):
    for j in range(p,W):
        if A[i][j]=="#":
            A[i]=A[i][:j]+"."+A[i][j+1:]
        else:
            p=j-1
            break
    if "#" in A[i]:
        print("Impossible")
        exit()
else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = [list(str(input())) for _ in range(H)]
for i in range(H):
  A[i] += '.'
A += [list('.'*(W+1))]
y,x = 0,0
ans = 'Impossible'
while y < H and x < W:
  if A[y+1][x] == '#' and A[y][x+1] == '#':
    break
  elif A[y+1][x] == '#':
    if '#' in A[y+1][:x]:
      break
    y += 1
  elif A[y][x+1] == '#':
    if '#' in A[y][x+3:]:
      break
    x += 1
  else:
    break
  if y == H-1 and x == W-1:
    ans = 'Possible'
    break
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = [list(str(input())) for _ in range(H)]
for i in range(H):
  A[i] += '.'
A += [list('.'*(W+1))]
y,x = 0,0
ans = 'Impossible'
while y < H and x < W:
  if A[y+1][x] == '#' and A[y][x+1] == '#':
    break
  elif A[y+1][x] == '#':
    if '#' in A[y+1][:x]:
      break
    y += 1
  elif A[y][x+1] == '#':
    x += 1
  else:
    break
  if y == H-1 and x == W-1:
    ans = 'Possible'
    break
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = [list(str(input())) for _ in range(H)]
for i in range(H):
  A[i] += '.'
A += [list('.'*(W+1))]
y,x = 0,0
ans = 'Impossible'
while y < H and x < W:
  if A[y+1][x] == '#' and A[y][x+1] == '#':
    break
  elif A[y+1][x] == '#':
    y += 1
  elif A[y][x+1] == '#':
    x += 1
  else:
    break
  if y == H-1 and x == W-1:
    ans = 'Possible'
    break
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = [list(str(input())) for _ in range(H)]
for i in range(H):
  A[i] += '.'
A += [list('.'*(W+1))]
y,x = 0,0
ans = 'Impossible'
while y < H and x < W:
  if A[y+1][x] == '#' and A[y][x+1] == '#':
    break
  elif A[y+1][x] == '#':
    y += 1
  elif A[y][x+1] == '#':
    x += 1
  else:
    break
  print(y,x)
  if y == H-1 and x == W-1:
    ans = 'Possible'
    break
print(ans)

Submission status: Wrong Answer

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

sh, sw = 0, 0
gh, gw = H-1, W-1
move = [(1, 0), (0, 1)]

f = 0
queue= [[sh, sw]]
# print(grid)

if grid[0][0] == ".":
    f = 1
else:
    while sh != gh or sw != gw:
        sh, sw = queue.pop(0)
        cnt = 0
        for i, j in move:
            if sh+i >= H or sw+j >= W:
                continue
            if grid[sh+i][sw+j] == "#":
                if cnt:
                    print("Impossible")
                    exit()
                else:
                    cnt += 1
                    if sh+i == gh and sw+j == gw:
                        print("Possible")
                        exit()
                    queue.append([sh+i, sw+j])
        if not queue:
            f = 1
            break
if f:
    print("Impossible")

Submission status: Wrong Answer

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

sh, sw = 0, 0
gh, gw = H-1, W-1
move = [(1, 0), (0, 1)]

queue= [[0, 0]]
# print(grid)
if grid[0][0] == ".":
    print("Impossible")
elif H == 1 and W == 1 and grid[0][0] =="#":
    print("Possible")
else:
    while sh != gh or sw != gw:
        sh, sw = queue.pop(0)
        cnt = 0
        for i, j in move:
            if sh+i >= H or sw+j >= W:
                continue
            if grid[sh+i][sw+j] == "#":
                if cnt:
                    print("Impossible")
                    exit()
                else:
                    cnt += 1
                    queue.append([sh+i, sw+j])
        # print(queue)
        if queue:
            if queue[0][0] == gh and queue[0][1] == gw:
                print("Possible")
                exit()
        else:
            print("Impossible")
            exit()

Submission status: Wrong Answer

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

sh, sw = 0, 0
gh, gw = H-1, W-1
move = [(1, 0), (0, 1)]

queue= [[0, 0]]

if grid[0][0] == ".":
    print("Impossible")
else:
    while sh != gh or sw != gw:
        sh, sw = queue.pop(0)
        cnt = 0
        for i, j in move:
            if sh+i >= H or sw+j >= W:
                continue
            if grid[sh+i][sw+j] == "#":
                if cnt:
                    print("Impossible")
                    exit()
                else:
                    cnt += 1
                    queue.append([sh+i, sw+j])
        # print(queue)
        if queue:
            if queue[0][0] == gh and queue[0][1] == gw:
                print("Possible")
                exit()
        else:
            print("Impossible")
            exit()

Submission status: Wrong Answer

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

sh, sw = 0, 0
gh, gw = H-1, W-1
move = [(1, 0), (0, 1)]

queue= [[0, 0]]

if grid[0][0] == ".":
    print("Impossible")
else:
    while sh != gh or sw != gw:
        sh, sw = queue.pop(0)
        cnt = 0
        for i, j in move:
            if sh+i >= H or sw+j >= W:
                continue
            if grid[sh+i][sw+j] == "#":
                if cnt:
                    print("Impossible")
                    exit()
                else:
                    cnt += 1
                    queue.append([sh+i, sw+j])
        if not queue:
            print("Impossible")
            exit()
    print("Possible")

Submission status: Wrong Answer

Solution code:
def main():
    h,w=map(int,input().split())
    a=[]
    for _ in range(h):
        a.append(input())
    now = (0, 0)
    end = (h-1, w-1)
    visited = set([now])
    while now != end:
        nxt = None
        #print(now)
        if now[0]+1 < len(a) and a[now[0]+1][now[1]] == "#":
            nxt = (now[0]+1, now[1])
        if now[1]+1 < len(a[now[0]]) and a[now[0]][now[1]+1] == "#":
            if nxt is not None:
                print("Impossible")
                return
            nxt = (now[0], now[1]+1)
        #print("next", nxt)
        if now[0]-1 >= 0 and a[now[0]-1][now[1]] == "#":
            if (now[0]-1,now[1]) not in visited:
                print("Impossible")
                return
        if now[1]-1 >= 0 and a[now[0]][now[1]-1] == "#":
            if (now[0],now[1]-1) not in visited:
                print("Impossible")
                return
            
        if nxt is None:
            print("Impossible")
            return
        now = nxt
        visited.add(nxt)
    print("Possible")
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    h,w=map(int,input().split())
    a=[]
    for _ in range(h):
        a.append(input())
    now = [0, 0]
    end = [h-1, w-1]
    while now != end:
        nxt = None
        if now[0]+1 < len(a) and a[now[0]+1][now[1]] == "#":
            nxt = now[:]
            nxt[0] += 1
        if now[1]+1 < len(a[now[0]]) and a[now[0]][now[1]+1] == "#":
            if nxt is not None:
                print("Impossible")
                return
            nxt = now[:]
            nxt[1] += 1
        if nxt is None:
            print("Impossible")
            return
        now = nxt
    print("Possible")
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    h,w=map(int,input().split())
    a=[]
    for _ in range(h):
        a.append(input())
    now = [0, 0]
    end = [h-1, w-1]
    while now != end:
        is_legal = False
        #print(now)
        if now[0]+1 < len(a) and a[now[0]+1][now[1]] == "#":
            now[0] += 1
            is_legal = not is_legal
        if now[1]+1 < len(a[now[0]]) and a[now[0]][now[1]+1] == "#":
            now[1] += 1
            is_legal = not is_legal
        if not is_legal:
            print("Impossible")
            return
    print("Possible")
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
list1=[]
ans=0
count1=0
count2=0
count3=0
for i in range(h):
    list1.append(list(input()))
for i in range(h):
    count3+=list1[i].count("#")
if count3!=h+w-1:
    ans=1
for i in range(h+w-3):
    if count2!=w-1:
        if list1[count1][(count2)+1]=="#":
            count2+=1
    if count1!=h-1:
        if list1[count1+1][count2]=="#":
            count1+=1
    if count2!=w-1:
        if count1!=h-1:
            if list1[count1+1][count2]=="." and list1[count1][count2+1]==".":
                ans=1
                break
        else:
            if list1[count1][count2+1]==".":
                ans=1
                break
    elif count1!=h-1:
        if list1[count1+1][count2]==".":
            ans=1
            break
if count1!=h-1 or count2!=w-1:
    ans=1
if ans==1:
    print("Impossible")
else:
    print("Possible")

Submission status: Wrong Answer

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

edge = [["." for _ in range(W+2)]]
center = [["."] + list(input()) + ["."] for i in range(H)]
A_array = edge + center + edge

def is_there_OK_move(before_i,before_j,before_move,route):
    if before_move == "right":
        i = before_i
        j = before_j + 1
    elif before_move == "down":
        i = before_i + 1
        j = before_j
    
    if i == H and j == W:
        return route
    else:
        up = A_array[i-1][j]
        down = A_array[i+1][j]
        right = A_array[i][j+1]
        left = A_array[i][j-1]

        if (down == right == "#") or (before_move == "right" and up == "#") or (before_move == "down" and left == "#"):
            return -1
        else:
            route.append((i,j))
            if down == "#":
                return is_there_OK_move(i,j,"down",route)
            elif right == "#":
                return is_there_OK_move(i,j,"right",route)

route = is_there_OK_move(0,1,"down",[(0,1)])

if route == -1:
    print("Impossible")
else:           
    print("Possible")