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())
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])
    
        
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):
  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])

dfs(0,0)

Submission status: Wrong Answer

Solution code:
h, w = map(int,input().split())
a = [list(input()) for i in range(h)]
sum = 0
for b in a:
    sum+=b.count('#')

if sum == h+w-1:
    print('possible')
else:
    print('impossible')

Submission status: Wrong Answer

Solution code:
import sys
h,w = map(int,input().split())
A = []
for i in range(h):
    A.append(list(input()))
for i in range(h-1):
    for j in range(w-1):
        if A[i][j] == "#":
            if A[i+1][j] == "#" and A[i][j+1] == ".":
                continue
            elif A[i+1][j] == "." and A[i][j+1] == "#":
                continue
            else:
                print("Impossible")
                sys.exit()
print("Possible")

Submission status: Wrong Answer

Solution code:
"""
深さ優先探索
goalにつけるかを判定する
通った点は.に書き換える。
"""
from itertools import chain
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

def dfs(x,y):
    if not(0 <= x <= W-1) or not(0 <= y <= H-1) or A[y][x] == ".":
        return
    if x == W-1 and y == H-1:
        A[y][x] = "."
        if "#" not in chain.from_iterable(A):
            print("Possible")
            exit()
    A[y][x] = "."
    dfs(x+1, y)
    dfs(x, y+1)

dfs(0,0)
print("Impossible")

Submission status: Wrong Answer

Solution code:
"""
深さ優先探索
goalにつけるかを判定する
通った点は.に書き換える。
"""
from itertools import chain
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

def dfs(x,y):
    if x == W-1 and y == H-1:
        A[y][x] = "."
        if "#" not in chain.from_iterable(A):
            print("Possible")
            exit()
    if not(0 <= x <= W-1) or not(0 <= y <= H-1) or A[y][x] == ".":
        return
    A[y][x] = "."
    dfs(x+1, y)
    dfs(x, y+1)

dfs(0,0)
print("Impossible")

Submission status: Wrong Answer

Solution code:
def myAnswer(H:int,W:int,A:list) -> str:
   i = 0
   j = 0
   if(A[i][j] == "."):return "Impossible"
   while True:
      if(i == H -1 and j == W - 1):
         return "Possible"
      else:
         tmp = []
         if(j != W - 1 and A[i][j + 1] == "#"):
            tmp.append([i,j + 1])
         if(i != H - 1 and A[i + 1][j] == "#"):
            tmp.append([i + 1,j])
         if(len(tmp) == 1):
            i,j = tmp[0][0],tmp[0][1]
         else:
            return "Impossible"


def modelAnswer():
   return
def main():
   H,W = map(int,input().split())
   A = []
   for _ in range(H):
      A.append(list(input()))
   print(myAnswer(H,W,A))
if __name__ == '__main__':
   main()

Submission status: Wrong Answer

Solution code:
def myAnswer(H:int,W:int,A:list) -> str:
   i = 0
   j = 0
   if(A[i][j] == "."):return "Impossible"
   while True:
      if(i == H -1 and j == W - 1):
         return "Possible"
      if(i == H - 1):
         if(A[i][j+1] == "#"):
            j += 1
         else:
            return "Impossible"
      elif(j == W - 1):
         if(A[i + 1][j] == "#"):
            i += 1
         else:
            return "Impossible"
      else:
         tmp = []
         if(A[i][j + 1] == "#"):
            tmp.append([i,j+1])
         if(A[i + 1][j] == "#"):
            tmp.append([i + 1, j])
         if(len(tmp)== 1):
            i,j = tmp[0][0],tmp[0][1]
         else:
            return "Impossible"

def modelAnswer():
   return
def main():
   H,W = map(int,input().split())
   A = []
   for _ in range(H):
      A.append(list(input()))
   print(myAnswer(H,W,A))
if __name__ == '__main__':
   main()

Submission status: Wrong Answer

Solution code:
A,B=list(map(int,input().split()))
l=[]
for i in range(A):
   l.append(list(input()))
c=0
for i in range(A):
   c+=l[i].count("#")
print("POSSIBLE" if A+B-1 == c else "IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
A,B=list(map(int,input().split()))
l=[]
for i in range(A):
   l.append(list(input()))
c=0
for i in range(A):
   c+=l[i].count("#")
print(c)
print("POSSIBLE" if A+B-1 == c else "IMPOSSIBLE")

Submission status: Wrong Answer

Solution code:
A,B=list(map(int,input().split()))
l=[]
for i in range(A):
   l.append(list(input()))
if l[0][0] ==".":
   print("IMPOSSIBLE")
   exit()
from collections import deque
que=deque([[0,0]])
after=deque()
c=0
for i in range(A):
   c+=l[i].count("#")
while que != deque([]):
   coord=que.popleft()
   after.append(coord)
   if coord[1] != B-1:
      if l[coord[0]][coord[1]+1] == "#":
         if[coord[0],coord[1]+1] in after:
            continue
         else:que.append([coord[0],coord[1]+1])
   if coord[0] != A-1:
      if l[coord[0]+1][coord[1]] == "#":
         if[coord[0]+1,coord[1]] in after:
            continue
         else:que.append([coord[0]+1,coord[1]])
if [A-1,B-1] in after and len(after) == c:
   print("Possible")
else:
   print("Impossible")

Submission status: Wrong Answer

Solution code:
# A - Shik and Stone
import numpy as np

H, W = map(int, input().split())
r = np.zeros((H+1, W+1), dtype=int)

r[0,1] = 1

for i in range(1,H+1):
    s = input()
    for j in range(1,W+1):
        r[i,j] = int(s[j-1]=='#' and r[i-1,j]+r[i,j-1]>0)

ans = ['Impossible', 'Possible']
print(ans[r[H,W]])

Submission status: Wrong Answer

Solution code:
import sys
h, w = map(int, input().split())
x = -1
for _ in range(h):
    for j, k in enumerate(input()):
        if k == '#':
            if j < x:
                print('Impossible')
                sys.exit()
            elif j > x:
                x += 1
        elif j >= x:
            if x == w - 1:
                print('Impossible')
                sys.exit()
            else:
                break
print('Possible') if x == w - 1 else print('Impossible')

Submission status: Wrong Answer

Solution code:
import sys
h, w = map(int, input().split())
x = -1
for _ in range(h):
    for j, k in enumerate(input()):
        if k == '#':
            if j < x:
                print('Impossible')
                sys.exit()
            elif j > x:
                x += 1
        elif j >= x:
            break
print('Possible') if x == w - 1 else print('Impossible')

Submission status: Wrong Answer

Solution code:
import sys
h, w = map(int, input().split())
x = -1
for _ in range(h):
    for j, k in enumerate(input()):
        if k == '#':
            if j < x:
                print('Impossible')
                sys.exit()
            elif j > x:
                x += 1
        elif j > x:
            break
print('Possible') if x == w - 1 else print('Impossible')

Submission status: Wrong Answer

Solution code:
import numpy as np

# 盤面の受け取り
H,W = map(int,input().split())
board = [[] for _ in range(H)]
for i in range(H):
    board[i] = list(input())

board = np.array(board)

minnum = W
maxnum = 0
for row in board[::-1]:
    S = "".join(row)
    left = S.find("#")
    right = len(S) - 1 - S[::-1].find("#")
    if right > minnum:
        print("Impossible")
        exit()
    minnum = left
    maxnum = right

board = board.T

minnum = W
maxnum = 0
for row in board[::-1]:
    S = "".join(row)
    left = S.find("#")
    right = len(S) - 1 - S[::-1].find("#")
    if right > minnum:
        print("Impossible")
        exit()
    minnum = left
    maxnum = right

print("Possible")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    H, W = map(int, readline().split())
    A = [[''] for _ in range(H)]
    for i in range(H):
        A[i] = readline().decode('utf-8').strip()
    if A[0][0]=='.' or A[H-1][W-1]=='.':
        print('Impossible')
        sys.exit()
    start = (0,0)
    goal = (W-1,H-1)
    dx = (1,0)
    dy = (0,1)
    visit = [[False]*W for _ in range(H)]
    Q = deque([start])
    while Q:
        q = Q.popleft()
        x = q[0]
        y = q[1]
        if visit[y][x] == True:
            print('Impossible')
            sys.exit()
        visit[y][x] = True
        if x == goal[0] and y == goal[1]:
            print('Possible')
            break
        else:
            for i in range(2):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<W and 0<=ny<H and A[ny][nx]=='#':
                    Q.append((nx,ny))
    else:
        print('Impossible')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = 0
for i in range(h):
  ans += input().count("#")
  print(ans)

print("Possible" if h + w - 1 == ans else "Impossible")

Submission status: Wrong Answer

Solution code:
h , w = map(int,input().split())
ma = [list(input()) for i in range(h)]
cou = 0
for i in range(h):
    p = 0
    for j in range(cou,w):
        if p == 0 and ma[i][j] == "#":
            p = 1
            cou = j
    if p == 0:
        print("Impossible")
        exit()
print("Possible")

Submission status: Wrong Answer

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

pos = (0, 0)
pre = 1
nxt = 0
while pos!=(w-1, h-1):
    x, y = pos
    if x<w-1 and a[y][x+1]=='#':
        nxt += 1
        pos = (x+1, y)
    if y<h-1 and a[y+1][x]=='#':
        nxt += 1
        pos = (x, y+1)
    if x>0 and a[y][x-1]=='#':
        pre += 1
    if y>0 and a[y-1][x]=='#':
        pre += 1
    if nxt!=1 or pre!=1:
        print('Impossible')
        break
    pre = 0
    nxt = 0
else:
    print('Possible')

Submission status: Wrong Answer

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

pos = (0, 0)
while pos!=(w-1, h-1):
    x, y = pos
    cnt = 0
    if x<w-1 and a[y][x+1]=='#':
        cnt += 1
        pos = (x+1, y)
    if y<h-1 and a[y+1][x]=='#':
        cnt += 1
        pos = (x, y+1)
    if cnt!=1:
        print('Impossible')
        break
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
c = 0
A = [["" for _ in range(w)] for _ in range(h)]
for i in range(h):
    a = input()
    for j in range(w):
        A[i][j] = a[j]
    c += list(a).count("#")

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

def bfs(x, y):
    if x == w - 1 and y == h - 1 and A[y][x] == "#":
        return 1
    if A[y][x] == ".":
        return 0
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < w and 0 <= ny and ny < h and A[y][x] == "#":
            return bfs(nx, ny) + 1

s = "Impossible"
if c == h + w - 1:
    if bfs(0, 0) == h + w - 1:
        s = "Possible"
print(s)

Submission status: Wrong Answer

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

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

def bfs(x, y):
    if x == w - 1 and y == h - 1 and A[y][x] == "#":
        return 1
    if A[y][x] == ".":
        return 0
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < w and 0 <= ny and ny < h and A[y][x] == "#":
            return bfs(nx, ny) + 1

if bfs(0, 0) == h + w - 1:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()
  if start[0]!=H-1 and start[1]!=W-1 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]+1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=0 and start[1]!=0 and listA[start[0]-1][start[1]]=="#" and listA[start[0]][start[1]-1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#":
    start=[start[0]+1,start[1]]
    continue  
  if start[1]!=W-1 and listA[start[0]][start[1]+1]=="#":
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()
  if start[1]==W-1 and start[0]!=H-1:
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]+1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=0 and start[1]!=0 and listA[start[0]-1][start[1]]=="#" and listA[start[0]][start[1]-1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#":
    start=[start[0]+1,start[1]]
    continue  
  if listA[start[0]][start[1]+1]=="#":
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()
  if start[1]==W-1 and start[0]!=H-1:
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]+1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#":
    start=[start[0]+1,start[1]]
    continue  
  if listA[start[0]][start[1]+1]=="#":
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()
  if start[1]==W-1 and start[0]!=H-1:
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]+1]=="#":
    print("Impossible")
    sys.exit()
  if start[1]!=0 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]-1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#":
    start=[start[0]+1,start[1]]
    continue  
  if listA[start[0]][start[1]+1]=="#":
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()
  if (start[1]==W-1 and start[0]!=H-1) or (start[0]!=H-1 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]+1]=="#"):
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#":
    start=[start[0]+1,start[1]]
    continue  
  if listA[start[0]][start[1]+1]=="#":
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()
  if start[1]==W-1 and start[0]!=H-1:
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#":
    start=[start[0]+1,start[1]]
    continue  
  if listA[start[0]][start[1]+1]=="#":
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")

Submission status: Wrong Answer

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

def solve(i, j, ok):
    if i == H-1 and j == W-1:
        print('Possible')
        exit()
        # ok2 = True
        # return ok2

    if 0 <= i < H-1 and 0 <= j < W-1:
        if A[i+1][j] == '#' and A[i][j+1] == '#':
            ok = False
        elif A[i+1][j] != '#' and A[i][j+1] != '#':
            ok = False
        elif A[i+1][j] == '#' and A[i][j+1] != '#':
            solve(i+1, j, ok)
        else:
            solve(i, j+1, ok)
    elif i == H-1 and 0 <= j < W-1:
        if A[i][j+1] == '#':
            solve(i, j+1, ok)
        else:
            ok = False
    else:
        if A[i+1][j] == '#':
            solve(i+1, j, ok)
        else:
            ok = False

solve(0, 0, ok)
print('Impossible')

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    H,W = readInts()
    FIELD = [input() for _ in range(H)]
    ARRIVED = [[False]*W for _ in range(H)]
    def Move(y,x):
        ARRIVED[y][x] = True
        if y == H-1 and x == W-1:
            print('Possible')
            exit()
        y_ = True
        x_ = True
        if y+1 < H:
            y_ = True
        else:
            y_ = False
        if x+1 < W:
            x_ = True
        else:
            x_ = False
        xu = True if x - 1 >= 0 else False
        yu = True if y - 1 >= 0 else False
        if y_ and FIELD[y+1][x] == '#':
            if x_ and FIELD[y][x+1] == '#':
                print('Impossible')
                exit()
            elif yu and FIELD[y-1][x] == '#' and not ARRIVED[y-1][x]:
                #print(y-1,x)
                print('Impossible')
                exit()
            else:
                Move(y+1,x)
        elif x_ and FIELD[y][x+1] == '#':
            if y_ and FIELD[y+1][x] == '#':
                print('Impossible')
                exit()
            elif xu and FIELD[y][x-1] == '#'  and not ARRIVED[y][x-1]:
                #print(y,x-1)
                print('Impossible')
                exit()
            else:
                Move(y,x+1)
        else:
            print('Impossible')
            exit()
    # 最初は (0,0)です
    Move(0,0)
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    H,W = readInts()
    FIELD = [input() for _ in range(H)]
    ARRIVED = [[False]*W for _ in range(H)]
    def Move(y,x):
        ARRIVED[y][x] = True
        if y == H-1 and x == W-1:
            print('Possible')
            exit()
        y_ = True
        x_ = True
        if y+1 < H:
            y_ = True
        else:
            y_ = False
        if x+1 < W:
            x_ = True
        else:
            x_ = False
        xu = True if x - 1 >= 0 else False
        yu = True if y - 1 >= 0 else False
        if y_ and FIELD[y+1][x] == '#':
            if x_ and FIELD[y][x+1] == '#':
                print('Impossible')
                exit()
            elif yu and FIELD[y-1][x] == '#' and not ARRIVED[y-1][x]:
                print(y-1,x)
                print('Impossible')
                exit()
            else:
                Move(y+1,x)
        elif x_ and FIELD[y][x+1] == '#':
            if y_ and FIELD[y+1][x] == '#':
                print('Impossible')
                exit()
            elif xu and FIELD[y][x-1] == '#'  and not ARRIVED[y][x-1]:
                print(y,x-1)
                print('Impossible')
                exit()
            else:
                Move(y,x+1)
        else:
            print('Impossible')
            exit()
    # 最初は (0,0)です
    Move(0,0)
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    H,W = readInts()
    FIELD = [input() for _ in range(H)]
    ARRIVED = [[False]*W for _ in range(H)]
    def Move(y,x):
        ARRIVED[y][x] = True
        if y == H-1 and x == W-1:
            print('Possible')
            exit()
        y_ = True
        x_ = True
        if y+1 < H:
            y_ = True
        else:
            y_ = False
        if x+1 < W:
            x_ = True
        else:
            x_ = False
        xu = True if x - 1 >= 0 else False
        yu = True if y - 1 >= 0 else False
        if y_ and FIELD[y+1][x] == '#':
            if x_ and FIELD[y][x+1] == '#':
                print('Impossible')
                exit()
            elif xu and FIELD[y-1][x] == '#' and not ARRIVED[y-1][x]:
                print('Impossible')
                exit()
            else:
                Move(y+1,x)
        elif x_ and FIELD[y][x+1] == '#':
            if y_ and FIELD[y+1][x] == '#':
                print('Impossible')
                exit()
            elif yu and FIELD[y][x-1] == '#'  and not ARRIVED[y][x-1]:
                print('Impossible')
                exit()
            else:
                Move(y,x+1)
        else:
            print('Impossible')
            exit()
    # 最初は (0,0)です
    Move(0,0)
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    H,W = readInts()
    FIELD = [input() for _ in range(H)]
    ARRIVED = [[False]*W for _ in range(H)]
    def Move(y,x):
        ARRIVED[y][x] = True
        if y == H-1 and x == W-1:
            print('Possible')
            exit()
        y_ = True
        x_ = True
        if y+1 < H:
            y_ = True
        else:
            y_ = False
        if x+1 < W:
            x_ = True
        else:
            x_ = False
        xu = True if x - 1 >= 0 else False
        yu = True if y - 1 >= 0 else False
        if y_ and FIELD[y+1][x] == '#':
            if x_ and FIELD[y][x+1] == '#':
                print('Impossible')
                exit()
            elif xu and FIELD[y][x-1] == '#' and not ARRIVED[y][x-1]:
                print('Impossible')
                exit()
            else:
                Move(y+1,x)
        elif x_ and FIELD[y][x+1] == '#':
            if y_ and FIELD[y+1][x] == '#':
                print('Impossible')
                exit()
            elif yu and FIELD[y-1][x] == '#'  and not ARRIVED[y-1][x]:
                print('Impossible')
                exit()
            else:
                Move(y,x+1)
        else:
            print('Impossible')
            exit()
    # 最初は (0,0)です
    Move(0,0)
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    H,W = readInts()
    FIELD = [input() for _ in range(H)]
    def Move(y,x):
        if y == H-1 and x == W-1:
            print('Possible')
            exit()
        y_ = True
        x_ = True
        if y+1 < H:
            y_ = True
        else:
            y_ = False
        if x+1 < W:
            x_ = True
        else:
            x_ = False
        if y_ and FIELD[y+1][x] == '#':
            if x_ and FIELD[y][x+1] == '#':
                print('Impossible')
                exit()
            else:
                Move(y+1,x)
        elif x_ and FIELD[y][x+1] == '#':
            if y_ and FIELD[y+1][x] == '#':
                print('Impossible')
                exit()
            else:
                Move(y,x+1)
        else:
            print('Impossible')
            exit()
    # 最初は (0,0)です
    Move(0,0)
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ma = []
for _ in range(h):
    ma.append(list(input()))
li = [[0,0]]
def che(lis):
    lll = lis.pop(0)
    x = lll[0]
    y = lll[1]
    tmp = []
    if x+1 < w:
        #print(x+1,y,w,h,ma)
        if ma[y][x+1] == '#':
            tmp.append([x+1,y])
        if x+1 == w -1 and y == h -1:
            print('Possible')
            exit()
    if y+1 < h:
        if ma[y+1][x] == '#':
            tmp.append([x,y+1])
        if x == w -1 and y+1 == h -1:
            print('Possible')
            exit()
    if len(tmp) == 0:
        print('Impossible')
        exit()
    else:
        lis += tmp
    tmp = []
    #print(lis)
while len(li)>0:
    che(li)

Submission status: Wrong Answer

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

A = []
B = ["."] * (w + 2)
A.append(B)
temp = 0
for i in range(h):
    T = ['.'] + list(input()) + ['.']
    A.append(T)
    temp += T.count('#')
A.append(B)

t = 1
print(A)
x = 1
y = 1
ans = 0
while t:
    if A[x][y] == '#':
        C = []
        C.append(A[x][y + 1])
        C.append(A[x+1][y])
        if C.count('#') > 1:
            t = 0
        else:
            A[x][y] = '?'
            if A[x][y+1] == '#':
                y = y + 1
            else:
                x = x + 1
            ans += 1
    else:
        t = 0

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

Submission status: Wrong Answer

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

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

for i in range(H):
  for j in range(W):
    if A[i][j] == '#' and (i,j) != (H-1,W-1):
      count = 0
      for k in range(2):
        y = i + dy[k]
        x = j + dx[k]
        if y < H and x < W:
          if A[y][x] == '#':
            count += 1
      if count != 1:
        print('Impossible')
        exit()

# ゴールの上と左をみる
gcount = 0
for k in range(2):
  y = H-1 - dy[k]
  x = W-1 - dx[k]
  if A[y][x] == '#':
    gcount += 1
if gcount == 1:
  print('Possible')
else:
  print('Impossible')

Submission status: Wrong Answer

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

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

for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      count = 0
      if (i,j) == (H-1,W-1):
        continue
      for k in range(2):
        y = i + dy[k]
        x = j + dx[k]
        if 0 <= y < H and 0 <= x < W:
          if A[y][x] == '#':
            count += 1
      if count != 1:
        print('Impossible')
        exit()
print('Possible')

Submission status: Wrong Answer

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

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

for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      flag = True
      if (i,j) == (H-1,W-1):
        flag = False
      for k in range(2):
        y = i + dy[k]
        x = j + dx[k]
        if 0 <= y < H and 0 <= x < W:
          if A[y][x] == '#':
            flag = False
      if flag:
        print('Impossible')
        exit()
print('Possible')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W=map(int,input().split())
    A=[['.']*(W+2) for _ in range(H+2)]
    for i in range(1,H+1):
        A[i][1:W+1]=list(input())
    v=(1,1)
    while v!=(H,W):
        if A[v[0]+1][v[1]]=='#' and A[v[0]][v[1]+1]=='#':
            print('Impossible')
            exit()
        elif A[v[0]+1][v[1]]=='#':
            v=(v[0]+1,v[1])
        elif A[v[0]][v[1]+1]=='#':
            v=(v[0],v[1]+1)
        else:
            print('Impossible')
            exit()
    print('Possible')
    

if __name__ == '__main__':
    main()