Problem:


Score : 200 points

Problem Statement

   #nck {
      width: 30px;
      height: auto;
   }

We have a grid of H rows and W columns. Initially, there is a stone in the top left cell. Shik is trying to move the stone to the bottom right cell. In each step, he can move the stone one cell to its left, up, right, or down (if such cell exists). It is possible that the stone visits a cell multiple times (including the bottom right and the top left cell).

You are given a matrix of characters a_{ij} (1 \leq i \leq H, 1 \leq j \leq W). After Shik completes all moving actions, a_{ij} is # if the stone had ever located at the i-th row and the j-th column during the process of moving. Otherwise, a_{ij} is .. Please determine whether it is possible that Shik only uses right and down moves in all steps.

Constraints

2 \leq H, W \leq 8

a_{i,j} is either # or ..

There exists a valid sequence of moves for Shik to generate the map a.

Input

The input is given from Standard Input in the following format:

H W
a_{11}a_{12}...a_{1W}
:
a_{H1}a_{H2}...a_{HW}

Output

If it is possible that Shik only uses right and down moves, print Possible. Otherwise, print Impossible.

Sample Input 1

4 5
##...
.##..
..##.
...##

Sample Output 1

Possible

The matrix can be generated by a 7-move sequence: right, down, right, down, right, down, and right.

Sample Input 2

5 3
###
..#
###
#..
###

Sample Output 2

Impossible

Sample Input 3

4 5
##...
.###.
.###.
...##

Sample Output 3

Impossible



Sample input:
4 5
##...
.##..
..##.
...##


Sample output:
Possible

Submission status: Wrong Answer

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

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("Imossible")
else:           
    print("Ppossible")

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    h, w = list(map(int, input().split()))
    A = ['.' * (w + 2),  ] + ['.' + input() + '.' for _ in range(h)] + ['.' * (w + 2),  ]
    i, j = 1, 1
    while True:
        if i == h and j == w:
            break
        if A[i + 1][j] == A[i][j + 1]:
            print('Impossible')
            exit()
        if A[i + 1][j] == '#':
            i += 1
        else:
            j += 1
    print('Possible')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    h, w = list(map(int, input().split()))
    A = [['.'] * (w + 2), ] + [['.', ] + list(input()) + ['.', ] for _ in range(h)] + [['.'] * (w + 2), ]
    stack = deque([[1, 1]])
    dxy = [[1, 0], [0, 1]]
    g = False
    while stack:
        x, y = stack.popleft()
        A[x][y] = '.'
        for (dx, dy) in dxy:
            X, Y = x + dx, y + dy
            if A[X][Y] == '#':
                stack.append([X, Y])
            else:
                pass
            if X == h and Y == w:
                A[X][Y] = '.'
                g = True
            else:
                pass
        if g:
            break
    else:
        print('Impossible')
        exit()
    for a in A:
        if any([i == '#' for i in a]):
            print('Impossible')
            break
    else:
        print('Possible')



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    h, w = list(map(int, input().split()))
    A = [['.'] * (w + 2), ] + [['.', ] + list(input()) + ['.', ] for _ in range(h)] + [['.'] * (w + 2), ]
    stack = deque([[1, 1]])
    dxy = [[1, 0], [0, 1]]
    g = False
    while stack:
        x, y = stack.popleft()
        A[x][y] = '.'
        for (dx, dy) in dxy:
            X, Y = x + dx, y + dy
            if A[X][Y] == '#':
                stack.append([X, Y])
            else:
                pass
            if X == w and Y == h:
                g = True
            else:
                pass
        if g:
            break
    else:
        print('Impossible')
        exit()
    for a in A:
        if any([i == '#' for i in a]):
            print('Impossible')
            break
    else:
        print('Possible')



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
    h, w = list(map(int, input().split()))
    A = ['.' * (w + 2), ] + ['.' + input() + '.' for _ in range(h)] + ['.' * (w + 2), ] 
    stack = deque([[1, 1]])
    dxy = [[1, 0], [0, 1]]
    while stack:
        x, y = stack.popleft()
        for (dx, dy) in dxy:
            X, Y = x + dx, y + dy
            if X == w and Y == h:
                print('Possible')
                exit()
            if A[X][Y] == '#':
                stack.append([X, Y])
    print('Impossible')



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

h,w = iim()
l = []
for _ in range(h):
    l.append(list(input()))

flag = True
for i in range(h):
    for j in range(w):
        if l[i][j] == '#' and (i != h-1 or j != w-1):
            if i < h-1 and j < w-1:
                if l[i][j+1] == l[i+1][j]:
                    flag = False
            elif i == h-1:
                if l[i][j+1] != '#':
                    flag = False
            elif j == w-1:
                if l[i+1][j] != '#':
                    flag = False
print('Possible' if flag else 'Impossible')

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
S[0][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
            S[new_h][new_w]='.'
            stack.append([new_w,new_h])
            if x==-1 and y==0:
                answer=1
                break
            elif x==0 and y==1:
                answer=1
                break
for s in S:
    if '#' in s:
        answer=1
        break
if answer==0:
    print('Possible')
else:
    print('Impossible')

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:
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
            S[new_h][new_w]='.'
            stack.append([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:
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
            S[new_h][new_w]='.'
            stack.append([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('Possiible')
else:
    print('Impossible')

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
            S[new_h][new_w]='.'
            stack.append([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('Posiible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a = [list(input()) for nesya in range(h)]
if a.count('#') == h+w-1:
  print('Possible')
else:
  print('Impossible')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

h,w=mii()

mat=[list(ss()) for _ in range(h) ]

chk=True
cnt=0
for i in range(h-1):
    for j in range(w-1):

        if mat[i][j]=="#":
            if mat[i+1][j]=="#" and mat[i][j+1]=="#":
                chk=False

for j in range(w):
    if mat[h-1][j]=="#" and mat[h-2][j]=="#":
        cnt+=1

cnt2=0
cnt3=0
for k in range(h):
    if mat[k][w-1]=="#" and mat[k][w-2]=="#":
        cnt2+=1
    if mat[k][0]=="#" and mat[k][1]=="#":
        cnt3+=1

if chk and cnt==1 and cnt2==1 and cnt3==1:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

h,w=mii()

mat=[list(ss()) for _ in range(h) ]

chk=True
cnt=0
for i in range(h-1):
    for j in range(w-1):

        if mat[i][j]=="#":
            if mat[i+1][j]=="#" and mat[i][j+1]=="#":
                chk=False

for j in range(w):
    if mat[h-1][j]=="#" and mat[h-2][j]=="#":
        cnt+=1

cnt2=0

for k in range(h):
    if mat[k][w-1]=="#" and mat[k][w-2]=="#":
        cnt2+=1

if chk and cnt==1 and cnt2==1:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

h,w=mii()

mat=[list(ss()) for _ in range(h) ]

chk=True
cnt=0
for i in range(h-1):
    for j in range(w-1):

        if mat[i][j]=="#":
            if mat[i+1][j]=="#" and mat[i][j+1]=="#":
                chk=False

for j in range(w):
    if mat[h-1][j]=="#" and mat[h-2][j]=="#":
        cnt+=1

if chk and cnt==1:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))
#list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################


#5230



h,w = list(map(int, input().split()))
data=[]

for i in range(h):
    data.append(input())

now = [0,0]
goal = [h-1,w-1]

while(True):
    if(now==goal):
        print("Possible")
        exit()
    a1='?'
    a2='?'
    if(now[1]!= w-1): a1 = data[now[0]][now[1]+1]
    if(now[0]!= h-1): a2 = data[now[0]+1][now[1]]
    if(a1=='#' and a2!='#'):
        now = AddV2(now,[0,1])
        continue
    if(a2=='#' and a1!='#'):
        now = AddV2(now,[1,0])
        continue
    if(a1!='#' and a2!='#'):
        print("Impossible")
        exit()
    if(a1=='#' and a2=='#'):
        print("Impossible")
        exit()

Submission status: Wrong Answer

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

s = [list(input()) for _ in range(H)]


flag = 0

for h in range(H-2):
  for w in range(W-2):
    if (s[h][w] =="#")and(s[h+1][w] == "#") and (s[h][w+1] == "#"):
      flag = 1
      break
    if (s[h+1][w+1] =="#")and(s[h+1][w] == "#") and (s[h][w+1] == "#"):
      flag = 1
      break
      
if flag == 1:
  print("Impossible")
else:
  print("Possible")

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

queue = deque()
queue.append([0, 0])
visited = [[False] * w for _ in range(h)]
visited[0][0] = True

def judge():
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#" and not visited[i][j]:
                return False
    return True
def bfs(queue):
    while len(queue) > 0:
        n_y, n_x = queue.popleft()

        if a[n_y][n_x + 1] == "#" and a[n_y + 1][n_x] == "#":
            print("Impossible")
            exit()
        for i, j in [[0, 1], [1, 0]]:
            y, x = n_y + i, n_x + j
            if 0 <= x < w and 0 <= y < h:
                if x != w - 1 and y != h -1:
                    if a[y][x] == "#" :
                        queue.append([y, x])
                        visited[y][x] = True
    for i in range(h):
        print(visited[i])
    print("Possible" if judge() else "Impossible")
bfs(queue)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

queue = deque()
queue.append([0, 0])
visited = [[False] * w for _ in range(h)]
visited[0][0] = True

def judge():
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#" and not visited[i][j]:
                return False
    return True
def bfs(queue):
    while len(queue) > 0:
        n_y, n_x = queue.popleft()
        for i, j in [[0, 1], [1, 0]]:
            y, x = n_y + i, n_x + j
            if 0 <= x < w and 0 <= y < h:
                if x != w - 1 and y != h -1:
                    if a[y][x + 1] == "#" and a[y + 1][x] == "#":
                        print("Impossible")
                        exit()
                if a[y][x] == "#" :
                    queue.append([y, x])
                    visited[y][x] = True
    print("Possible" if judge() else "Impossible")
bfs(queue)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

queue = deque()
queue.append([0, 0])
visited = [[False] * w for _ in range(h)]
visited[0][0] = True

def judge():
    for i in range(h - 1):
        for j in range(w - 1):
            if (a[i][j] == "#" and not visited[i][j]) or (visited[i][j + 1] and visited[i + 1][j]):
                return False
    return True
def bfs(queue):
    while len(queue) > 0:
        n_y, n_x = queue.popleft()
        for i, j in [[0, 1], [1, 0]]:
            y, x = n_y + i, n_x + j
            if 0 <= x < w and 0 <= y < h:
                if x != w - 1 and y != h -1:
                    if a[y][x + 1] == "#" and a[y + 1][x] == "#":
                        print("Impossible")
                        exit()
                if a[y][x] == "#" :
                    queue.append([y, x])
                    visited[y][x] = True
    print("Possible" if judge() else "Impossible")
bfs(queue)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

queue = deque()
queue.append([0, 0])
def bfs(queue):
    while len(queue) > 0:
        n_y, n_x = queue.popleft()
        for i, j in [[0, 1], [1, 0]]:
            y, x = n_y + i, n_x + j
            if 0 <= x < w and 0 <= y < h:
                if x != w - 1 and y != h -1:
                    if a[y][x + 1] == "#" and a[y + 1][x] == "#":
                        print("Impossible")
                        exit()
                if a[y][x] == "#" :
                    queue.append([y, x])
    print("Possible")
bfs(queue)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

queue = deque()
queue.append([0, 0])
visited = [[False] * w for _ in range(h)]
visited[0][0] = True

def judge():
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#" and not visited[i][j]:
                return False
    
    return True

def bfs(queue):
    while len(queue) > 0:
        n_y, n_x = queue.popleft()
        for i, j in [[0, 1], [1, 0]]:
            y, x = n_y + i, n_x + j
            if 0 <= x < w and 0 <= y < h:
                if x != w - 1 and y != h -1:
                    if a[y][x + 1] == "#" and a[y + 1][x] == "#":
                        print("Impossible")
                        exit()
                if a[y][x] == "#" :
                    queue.append([y, x])
                    visited[y][x] = True
    print("Possible" if judge() else "Impossible")
bfs(queue)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

queue = deque()
queue.append([0, 0])
visited = [[False] * w for _ in range(h)]
visited[0][0] = True

def judge():
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#" and not visited[i][j]:
                return False
    
    return True

def bfs(queue):
    while len(queue) > 0:
        n_y, n_x = queue.popleft()
        for i, j in [[0, 1], [1, 0]]:
            y, x = n_y + i, n_x + j
            if 0 <= x < w and 0 <= y < h:
                if x != w - 1 and y != h -1:
                    if a[y][x + 1] == "#" and a[y + 1][x] == "#":
                        print("Impossible")
                        exit()
                if a[y][x] == "#" :
                    queue.append([y, x])
                    visited[y][x] = True
    
    
    for i in range(h):
        print(visited[i])
    
    print("Possible" if judge() else "Impossible")
bfs(queue)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

queue = deque()
queue.append([0, 0])
visited = [[False] * w for _ in range(h)]
visited[0][0] = True

def judge():
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#" and not visited[i][j]:
                return False
    
    return True

def bfs(queue):
    while len(queue) > 0:
        y, x = queue.popleft()
        for i, j in [[0, 1], [1, 0]]:
            y, x = y + i, x + j
            if 0 <= x < w and 0 <= y < h:
                if a[y][x] == "#" :
                    queue.append([y, x])
                    visited[y][x] = True
            
    print("Possible" if judge() else "Impossible")
bfs(queue)

Submission status: Wrong Answer

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

x,y = 0,0
while(x+y<h+w-2):
    dx,dy=0,0
    if(x!=0):
        if(a[x-1][y]=='#'):
            print('Impossible')
            exit()
    if(y!=0):
        if(a[x][y-1]=='#'):
            print('Impossible')
            exit()

    if(x!=h-1):
        if(a[x+1][y]=='#'):
            dx = 1
    if(y!=w-1):
        if(a[x][y+1]=='#'):
            dy = 1
    if(dx+dy!=1):
        print('Impossible')
        exit()

    x += dx
    y += dy

print('Possible')

Submission status: Wrong Answer

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

x,y = 0,0
while(x+y<h+w-2):
    dx,dy=0,0
    if(x!=h-1):
        if(a[x+1][y]=='#'):
            dx = 1
    if(y!=w-1):
        if(a[x][y+1]=='#'):
            dy = 1
    if(dx+dy!=1):
        print('Impossible')
        exit()

    x += dx
    y += dy

print('Possible')

Submission status: Wrong Answer

Solution code:
def answer(matrix):
    h = len(matrix)
    w = len(matrix[0])
    P, IM = ("Possible", "Impossible")
    cp = [0, 0] # current position
    rightBottom = [len(matrix)-1, len(matrix[0])-1]
    while(True):
        matrix[cp[0]][cp[1]] = '.'
        # Up
        if cp[0] > 0 and matrix[cp[0]-1][cp[1]] == '#': return IM
        # Left
        if cp[1] > 0 and matrix[cp[0]][cp[1]-1] == '#': return IM
        # Bottom
        if cp[0]+1 < h and matrix[cp[0]+1][cp[1]] == '#':
            if cp[1]+1 < w and matrix[cp[0]][cp[1]+1] == '#':
                return IM
            cp[0] = cp[0]+1
            print(cp)
            continue
        # Right
        if cp[1]+1 < w and matrix[cp[0]][cp[1]+1] == '#':
            cp[1] = cp[1]+1
            continue
        if cp[0] == rightBottom[0] and cp[1] == rightBottom[1]:
            return P
    return P

h, w = map(int, input().split())
matrix = []
for _ in range(h):
    row = [c for c in input()]
    matrix.append(row)
print(matrix)
print(answer(matrix))

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]
i = 0
j = 0
while True:
    right_most = j
    bit = 0
    for k in range(w):
        if a[i][k] == "#":
            if k < j:
                print("Impossible")
                exit()
            if not bit:
                right_most = k
            else:
                print("Impossible")
                exit()
        else:
            if k > j:
                bit = 1
    j = right_most
    if i == h - 1 and j == w - 1:
        print("Possible")
        exit()
    else:
        down_most = i
        bit = 0
        for k in range(h):
            if a[k][j] == "#":
                if k < i:
                    print("Impossible")
                    exit()
                if not bit:
                    down_most = k
                else:
                    print("Impossible")
                    exit()
            else:
                if k > i:
                    bit = 1
        i = down_most
        if i >= h - 1 and j >= w - 1:
            print("Possible")
            exit()

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]
i = 0
j = 0
while True:
    right_most = j
    bit = 0
    for k in range(j, w):
        if a[i][k] == "#":
            if not bit:
                right_most = k
            else:
                print("Impossible")
                exit()
        else:
            bit = 1
    j = right_most
    if i == h - 1 and j == w - 1:
        print("Possible")
        exit()
    else:
        down_most = i
        bit = 0
        for k in range(i, h):
            if a[k][j] == "#":
                if not bit:
                    down_most = k
                else:
                    print("Impossible")
                    exit()
            else:
                bit = 1
        i = down_most
        if i >= h - 1 and j >= w - 1:
            print("Possible")
            exit()

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
l = [list(input()) for _ in range(h)]
n = [0,1,0,-1]
m = [1,0,-1,0]

def dfs(a,b):
  if 0<=a+n[0] and a+n[0]<=w-1 and 0<=b+m[0] and b+m[0]<=h-1 and 0<=a+n[1] and a+n[1]<=w-1 and 0<=b+m[1] and b+m[1]<=h-1:
    if l[b+m[0]][a+n[0]]=="#" and l[b+m[1]][a+n[1]]=="#":
      return print("Impossible")
  for i in range(4):
    if 0<=a+n[i] and a+n[i]<=w-1 and 0<=b+m[i] and b+m[i]<=h-1:
      if l[b+m[i]][a+n[i]]=="#":
        if i==2 or i==3:
          return print("Impossible")

        elif a+n[i]==w-1 and b+m[i]==h-1:
          return print("Possible")
        else:
          return dfs(a+n[i],b+m[i])
  else:
    return print("Impossible")
        
    
        
dfs(0,0)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
l = [list(input()) for _ in range(h)]
n = [0,1,0,-1]
m = [1,0,-1,0]

def dfs(a,b):
  if 0<=a+n[0] and a+n[0]<=w-1 and 0<=b+m[0] and b+m[0]<=h-1 and 0<=a+n[1] and a+n[1]<=w-1 and 0<=b+m[1] and b+m[1]<=h-1:
    if l[b+m[0]][a+n[0]]=="#" and l[b+m[1]][a+n[1]]=="#":
      return print("Impossible")
  for i in range(4):
    if 0<=a+n[i] and a+n[i]<=w-1 and 0<=b+m[i] and b+m[i]<=h-1:
      if l[b+m[i]][a+n[i]]=="#":
        if i==2 or i==3:
          return print("Impossible")

        elif a+n[i]==w-1 and b+m[i]==h-1:
          return print("Possible")
        else:
          return dfs(a+n[i],b+m[i])
      else:
        return print("Impossible")
    
        
dfs(0,0)