Problem:


Score : 200 points

Problem Statement

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

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

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

Constraints

2 \leq H, W \leq 8

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

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

Input

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

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

Output

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

Sample Input 1

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

Sample Output 1

Possible

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

Sample Input 2

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

Sample Output 2

Impossible

Sample Input 3

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

Sample Output 3

Impossible



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


Sample output:
Possible

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip("\n") for _ in range(H)]
    q = deque()
    q.append((0, 0))
    visited = [[False] * W for _ in range(H)]
    possible = True
    while q:
        nh, nw = q.popleft()
        if not visited[nh][nw]:
            visited[nh][nw] = True
            if 0 <= nh + 1 < H and A[nh + 1][nw] == "#":
                if 0 <= nw - 1 and A[nh+1][nw-1] == "#":
                    possible = False
                    break
                q.append((nh+1, nw))
            if 0 <= nw + 1 < W and A[nh][nw+1] == "#":
                if 0 <= nh - 1 and A[nh-1][nw+1] == "#":
                    possible = False
                    break
                q.append((nh, nw+1))
    else:
        if not visited[H-1][W-1]: possible = False
    print("Possible" if possible else "Impossible")

    return 0

if __name__ =="__main__":
    solve()

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
B = ["."+input()+"." for k in range(H)]
B = ["."*(W+2)] + B + ["."*(W+2)]
x, y = 1,1
while True:
    if B[y][x+1] == "#" and B[y+1][x] == ".":
        x += 1
    elif B[y+1][x] == "#" and B[y][x+1] == ".":
        y += 1
    elif x == W and y == H:
        print("Possible")
        exit(0)
    else:
        print("Impossible")
        exit(0)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[list(input())for _ in range(h)]
ok=[w*[0]for _ in range(h)]
ok[0][0]=1
for i in range(h):
  for j in range(w):
    if i==0:
      if j!=0:
        if s[i][j]=="#":ok[i][j]=ok[i][j-1]
    else:
      if s[i][j]=="#":ok[i][j]|=ok[i-1][j]
      if j==0:continue
      if s[i][j]=="#":ok[i][j]|=ok[i][j-1]
if ok[-1][-1]:print("Possible")
else:print("Impossible")

Submission status: Wrong Answer

Solution code:
#移動できる回数が限られている。
#具体的には、#の数がh+w個ピッタリじゃなくてはならない
h, w = map(int, input().split())
grid = []
sharp_count = 0
for i in range(h):
    grid.append(list(input()))
    sharp_count += grid[i].count('#')
if sharp_count != h+w:
    print("Impossible")
else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
def main():
    h, w = map(int, input().split())
    a = [["." for j in range(w+2)] for i in range(h+2)]
    for i in range(h):
        s = list(input().rstrip())
        for j in range(w):
            a[i+1][j+1] = s[j]
    y, x = 1, 1
    f = True
    while y != h or x != w:
        a[y][x] = "."
        if a[y-1][x] == "#" or a[y][x-1] == "#" or (a[y+1][x] == "#" and a[y][x+1] == "#"):
            f = False
            break
        else:
            if a[y+1][x] == "#":
                y += 1
            else:
                x += 1
    if f:
        print("Possible")
    else:
        print("Impossible")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
r = 0
for i in range(H):
    line = input().strip()
    nr = 0
    for j in range(W):
        if line[j] == '#':
            nr = j
    if nr < r:
        print('Impossible')
        exit()
    r = nr
print('Possible')

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W = map(int, input().split())
Grid = np.empty((H+2, W+2), str)
Grid[0, :] = '.'
Grid[H+1, :] = '.'
for h in range(H):
  tmp = [str(s) for s in str(input())]
  Grid[h+1, 1:W+1] = tmp
  Grid[h+1, 0] = '.'
  Grid[h+1, W+1] = '.'

reached = np.empty_like(Grid, bool)
reached[:, :] = False

import sys
sys.setrecursionlimit(2500100)

def search(r, c):
  if r < 0 or H+2 <= r or c < 0 or W+2 <= c:
    return
  if Grid[r, c] == '.':
    return

  reached[r, c] = True

  if Grid[r+1, c] == '#' and Grid[r, c+1] == '#':
    return
  if Grid[r-1, c] == '#' and Grid[r, c-1] == '#':
    return

  if Grid[r+1, c] == '#':
    search(r+1, c)
  if Grid[r, c+1] == '#':
    search(r, c+1)

search(1, 1)

if reached[H, W]:
  print('Possible')
else:
  print('Impossible')

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W = map(int, input().split())
Grid = np.empty((H, W), str)
for h in range(H):
  tmp = [str(s) for s in str(input())]
  Grid[h, :] = tmp

reached = np.empty_like(Grid, bool)
reached[:, :] = False

import sys
sys.setrecursionlimit(2500100)

def search(r, c):
  if r < 0 or H <= r or c < 0 or W <= c:
    return
  if Grid[r, c] == '.':
    return

  reached[r, c] = True

  if r < H-1 and c < W-1:
    if Grid[r+1, c] == '#' and Grid[r, c+1] == '#':
      return
  if r < H-1:
    if Grid[r+1, c] == '#':
      search(r+1, c)
  if c < W-1:
    if Grid[r, c+1] == '#':
      search(r, c+1)

search(0, 0)

if reached[H-1, W-1]:
  print('Possible')
else:
  print('Impossible')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
mat = [input() for _ in range(n)]
i = 0
j = 0

while i != n-1 or j != m-1:
    down = '.'
    right = '.'
    downleft = '.'
    if i != n-1:
        down = mat[i+1][j]
        if j != 0:
            downleft = mat[i+1][j-1]
    if j != m-1:
        right = mat[i][j+1]
    
    if down == right:
        print('Impossible')
        exit()
    elif down == '#': 
        if downleft == down:
            print('Impossible')
            exit()
        i+=1
    else: j+=1

print('Possible')

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
mat = [input() for _ in range(n)]
i = 0
j = 0

while i != n-1 or j != m-1:
    down = '.'
    right = '.'
    if i != n-1:
        down = mat[i+1][j]
    if j != m-1:
        right = mat[i][j+1]
    
    if down == right:
        print('Impossible')
        exit()
    elif down == '#': i+=1
    else: j+=1

print('Possible')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]
hi = wi = 0
r = "Possible"
while hi != h - 1 or wi != w - 1:
    if hi != h - 1:
        if a[hi+1][wi] == "#":
            if wi == w - 1:
                hi += 1
                continue
            else:
                if a[hi][wi+1] == "#":
                    r = "Impossible"
                    break
                else:
                    hi += 1
                    continue
        else:
            if wi != w - 1:
                if a[hi][wi+1] == "#":
                    wi += 1
                    continue
                else:
                    r = "Impossible"
                    break
            else:
                r = "Impossible"
                break
    if wi != w - 1:
        if a[hi][wi+1] == "#":
            wi += 1
            continue
        else:
            r = "Impossible"
            break
print(r)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]
hi = wi = 0
r = "Possible"
while hi != h-1 or wi != w-1:
    if hi != h-1:
        if a[hi+1][wi] == "#":
            if wi != w-1:
                if a[hi][wi+1] == "#":
                    r = "Impossible"
                    break
                else:
                    hi += 1
                    continue
            else:
                hi += 1
                continue
        elif wi != w-1:
                if a[hi][wi+1] == "#":
                    wi += 1
                    continue
                else:
                    r = "Impossible"
                    break
        else:
            r = "Impossible"
            break
    else:
        if a[hi][wi+1] == "#":
            wi += 1
            continue
        else:
            r = "Impossible"
            break
print(r)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a = [input() for i in range(h)]
a_count = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            a_count += 1
if a_count == (h+w)-1:
    print('Posiible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s = [input() for i in range(h)]
def im():
  print("Impossible")
if s[0][0]!="#":
  im()
  exit()
x=0
y=0
while 1==1:
  if x==0 and y==0:
    if s[x+1][y]=="#" and s[x][y+1]=="#":
      im()
      exit()
    elif s[x+1][y]=="#":
      x+=1
    elif s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()
  elif (x==0 and y!=w-1) or (y==0 and x!=h-1):
    if s[x+1][y]=="#" and s[x][y+1]=="#":
      im()
      exit()
    elif s[x+1][y]=="#":
      x+=1
    elif s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()
  elif x==h-1 and y!=w-1:
    if s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()
  elif x!=h-1 and y==w-1:
    if s[x+1][y]=="#":
      x+=1
    else:
      im()
      exit()
  elif x==h-1 and y==w-1:
    print("Possible")
    exit()
  else:
    #はじっこでない
    c=0
    if s[x+1][y]=="#":
      c+=1
    if s[x][y+1]=="#":
      c+=1
    if s[x-1][y]=="#":
      c+=1
    if s[x][y-1]=="#":
      c+=1
    if c!=2:
      im()
      exit()
    if s[x+1][y]=="#" and s[x][y+1]=="#":
      im()
      exit()
    elif s[x+1][y]=="#":
      x+=1
    elif s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s = [input() for i in range(h)]
def im():
  #print(x,y)
  print("Impossible")
x=0
y=0
while 1==1:
  if x==0 and y==0:
    if s[x+1][y]=="#" and s[x][y+1]=="#":
      im()
      exit()
    elif s[x+1][y]=="#":
      x+=1
    elif s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()
  elif (x==0 and y!=w-1) or (y==0 and x!=h-1):
    if s[x+1][y]=="#" and s[x][y+1]=="#":
      im()
      exit()
    elif s[x+1][y]=="#":
      x+=1
    elif s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()
  elif x==h-1 and y!=w-1:
    if s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()
  elif x!=h-1 and y==w-1:
    if s[x+1][y]=="#":
      x+=1
    else:
      im()
      exit()
  elif x==h-1 and y==w-1:
    print("Possible")
    exit()
  else:
    #はじっこでない
    c=0
    if s[x+1][y]=="#":
      c+=1
    if s[x][y+1]=="#":
      c+=1
    if s[x-1][y]=="#":
      c+=1
    if s[x][y-1]=="#":
      c+=1
    if c!=2:
      im()
      exit()
    if s[x+1][y]=="#" and s[x][y+1]=="#":
      im()
      exit()
    elif s[x+1][y]=="#":
      x+=1
    elif s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s = [input() for i in range(h)]
def im():
  print(x,y)
  print("Impossible")
x=0
y=0
while 1==1:
  if x==0 and y==0:
    if s[x+1][y]=="#" and s[x][y+1]=="#":
      im()
      exit()
    elif s[x+1][y]=="#":
      x+=1
    elif s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()
  elif (x==0 and y!=w-1) or (y==0 and x!=h-1):
    if s[x+1][y]=="#" and s[x][y+1]=="#":
      im()
      exit()
    elif s[x+1][y]=="#":
      x+=1
    elif s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()
  elif x==h-1 and y!=w-1:
    if s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()
  elif x!=h-1 and y==w-1:
    if s[x+1][y]=="#":
      x+=1
    else:
      im()
      exit()
  elif x==h-1 and y==w-1:
    print("Possible")
    exit()
  else:
    #はじっこでない
    c=0
    if s[x+1][y]=="#":
      c+=1
    if s[x][y+1]=="#":
      c+=1
    if s[x-1][y]=="#":
      c+=1
    if s[x][y-1]=="#":
      c+=1
    if c!=2:
      im()
      exit()
    if s[x+1][y]=="#" and s[x][y+1]=="#":
      im()
      exit()
    elif s[x+1][y]=="#":
      x+=1
    elif s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s = [input() for i in range(h)]
def im():
  print("Impossible")
x=0
y=0
while 1==1:
  if x==0 and y==0:
    if s[x+1][y]=="#" and s[x][y+1]=="#":
      im()
      exit()
    elif s[x+1][y]=="#":
      x+=1
    elif s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()
  elif (x==0 and y!=w-1) or (y==0 and x!=h-1):
    if s[x+1][y]=="#" and s[x][y+1]=="#":
      im()
      exit()
    elif s[x+1][y]=="#":
      x+=1
    elif s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()
  elif x==h-1 and y!=w-1:
    if s[x][y+1]=="#":
      y+=1
    else:
      im()
      exit()
  elif x!=h-1 and y==w-1:
    if s[x+1][y]=="#":
      x+=1
    else:
      im()
      exit()
  elif x==h-1 and y==w-1:
    print("Possible")
    exit()
  else:
    #はじっこでない
    c=0
    if s[x+1][y]=="#":
      c+=1
      x+=1
    if s[x][y+1]=="#":
      c+=1
      y+=1
    if s[x-1][y]=="#":
      c+=1
    if s[x][y-1]=="#":
      c+=1
    if c!=2:
      im()
      exit()

Submission status: Wrong Answer

Solution code:
def main():
  h, w = input_list()
  route = []
  maze = []
  for _ in range(h):
    maze.append(list(input()))
    route.append([False]*w)
  dfs(route, maze, 0, 0, w, h)
  print("Possible")
  
  
def dfs(route, maze, x, y, w, h):
  if maze[y][x] == '.':
    return
  
  route[y][x] = True
  if x + 1 < w and maze[y][x+1] == '#':
    dfs(route, maze, x+1, y, w, h)
  if y + 1 < h and maze[y+1][x] == '#':
    dfs(route, maze, x, y+1, w, h)
  if y - 1 > 0 and maze[y-1][x] == '#' and route[y-1][x] is False:
    ans = False
    print("Impossible")
    exit()
    
  if x - 1 > 0 and maze[y][x-1] == '#' and route[y][x-1] is False:
    ans = False
    print("Impossible")
    exit()
    

def input_list():
  return map(int, input().split())

import math
main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe


# my functions here!
#標準エラー出力
def printargs2err(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' : '+repr(arg) for arg in args),file=sys.stderr)
def debug(x):
    print(x,file=sys.stderr)
def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())

#繰り返し自乗法だよ
#これはnのp乗をmで割ったあまりをだすよ
def modular_w_binary_method (n,m,p):
    ans=1 if n>0 else 0
    while(p>0):
        if p%2==1:
            ans=(ans*n)%m
        n=(n**2)%m
        p//=2
    return ans
#mod上でのaの逆元を出すよ
"""
    フェルマーの小定理より a**(p)%p==a isTrue
    これを利用すれば a**(p-2)%p==a**(-1) isTrue
    元と逆元とをかけてpで割れば1が余るよ！
"""
def modular_inverse(a,prime):
    return(modular_w_binary_method(a,prime,prime-2))
#逆元を使うと容易に頑張れるｃ
def conbination(n,a,mod=10**9+7):
    #cはイラない
    res=1 
    for s in range(a):
        res=(res*(n-s)*(modular_inverse(s+1,mod)))%mod

        
    return res
#操作から作れるものの組み合わせは何個かー＞同じものでも違う方法で構成できるかから考える方法もある
"""
"""

#solution:

#input
H,W=pin()
h=0
for i in range(H):
    t=list(input())
    for j in t:
        if j=="#":
            h+=1
#print(h)
print(["Impossible","possible"][h==(H+W-1)])
#print(m)
#print(["No","Yes"][cond])
#print([["NA","YYMM"],["MMYY","AMBIGUOUS"]][cMMYY][cYYMM])
"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe


# my functions here!
#標準エラー出力
def printargs2err(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' : '+repr(arg) for arg in args),file=sys.stderr)
def debug(x):
    print(x,file=sys.stderr)
def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())

#繰り返し自乗法だよ
#これはnのp乗をmで割ったあまりをだすよ
def modular_w_binary_method (n,m,p):
    ans=1 if n>0 else 0
    while(p>0):
        if p%2==1:
            ans=(ans*n)%m
        n=(n**2)%m
        p//=2
    return ans
#mod上でのaの逆元を出すよ
"""
    フェルマーの小定理より a**(p)%p==a isTrue
    これを利用すれば a**(p-2)%p==a**(-1) isTrue
    元と逆元とをかけてpで割れば1が余るよ！
"""
def modular_inverse(a,prime):
    return(modular_w_binary_method(a,prime,prime-2))
#逆元を使うと容易に頑張れるｃ
def conbination(n,a,mod=10**9+7):
    #cはイラない
    res=1 
    for s in range(a):
        res=(res*(n-s)*(modular_inverse(s+1,mod)))%mod

        
    return res
#操作から作れるものの組み合わせは何個かー＞同じものでも違う方法で構成できるかから考える方法もある
"""
"""

#solution:

#input
H,W=pin()
h=0
for i in range(H):
    t=list(input())
    for j in t:
        if j=="#":
            h+=1
print(h)
print(["Impossible","possible"][h==(H+W-1)])
#print(m)
#print(["No","Yes"][cond])
#print([["NA","YYMM"],["MMYY","AMBIGUOUS"]][cMMYY][cYYMM])
"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""

Submission status: Wrong Answer

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

tb = [list(input()) for _ in range(H)]
mx, my = 0, 0
def dfs(x, y):
    # 今いるところを . に置き換える
    tb[x][y] = "."
    global mx
    global my

    # 移動する2方向をループ
    for dx in range(1, -1,-1):
        for dy in range(1, -1,-1):
            if dx==dy:
                continue
            # x, y 方向それぞれに dx, dy 移動した場所を (nx, ny) とする
            nx = x + dx
            ny = y + dy
            mx = max(mx,nx)
            my = max(my,ny)

            if 0 <= nx and nx < H and 0 <= ny and ny < W and tb[nx][ny] == "#" and (nx>=mx or ny>=my):
                dfs(nx, ny)

dfs(0,0)

fl = True
for i in range(H):
    if '#' in tb[i]:
        fl = False

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

Submission status: Wrong Answer

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

tb = [list(input()) for _ in range(H)]
mx, my = 0, 0
def dfs(x, y):
    # 今いるところを . に置き換える
    tb[x][y] = "."
    global mx
    global my

    # 移動する2方向をループ
    for dx in range(1, -1,-1):
        for dy in range(1, -1,-1):
            if dx==dy:
                continue
            # x, y 方向それぞれに dx, dy 移動した場所を (nx, ny) とする
            nx = x + dx
            ny = y + dy
            mx = max(mx,nx)
            my = max(my,ny)

            if 0 <= nx and nx < H and 0 <= ny and ny < W and tb[nx][ny] == "#" and (nx>=mx or ny>=my):
                dfs(nx, ny)

dfs(0,0)
print(tb)

fl = True
for i in range(H):
    if '#' in tb[i]:
        fl = False

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

Submission status: Wrong Answer

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

tb = [list(input()) for _ in range(H)]
mx, my = 0, 0
def dfs(x, y):
    # 今いるところを . に置き換える
    tb[x][y] = "."
    global mx
    global my

    # 移動する2方向をループ
    for dx in range(0, 2):
        for dy in range(0, 2):
            if dx==dy:
                continue
            # x, y 方向それぞれに dx, dy 移動した場所を (nx, ny) とする
            nx = x + dx
            ny = y + dy
            mx = max(mx,nx)
            my = max(my,ny)

            if 0 <= nx and nx < H and 0 <= ny and ny < W and tb[nx][ny] == "#" and (nx>=mx or ny>=my):
                dfs(nx, ny)

dfs(0,0)

fl = True
for i in range(H):
    if '#' in tb[i]:
        fl = False

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

Submission status: Wrong Answer

Solution code:
import numpy as np

NOT_VISITED = '.'; CHECKED = '.'
VISITED = '#'

def dfs(x, y, m):
    # 右下端に到達した場合
    if x == h - 1 and y == w - 1:
        m[x][y] = CHECKED
        print("Possible" if (a == CHECKED).all() else "Impossible")
        exit()

    if not (0 <= x < h) or not (0 <= y < w) or m[x][y] == NOT_VISITED:
        return

    m[x][y] = CHECKED

    if (y == w - 1 and x != h - 1) or (x == h - 1 and y != h - 1):
        print("Impossible")
        exit()

    dfs(x, y+1, m)  # 右を探索
    dfs(x+1, y, m)  # 下を探索


h, w = [int(i) for i in input().split()]
a = np.array([list(input()) for _ in range(h)])

dfs(0, 0, a)
print("Possible" if a[h-1][w-1] == CHECKED else "Impossible")

Submission status: Wrong Answer

Solution code:
import numpy as np

NOT_VISITED = '.'; CHECKED = '.'
VISITED = '#'

def dfs(x, y, m):
    if x == h - 1 and y == w - 1:
        m[x][y] = CHECKED
        print("Possible" if (a == CHECKED).all() else "Impossible")
        exit()

    if not (0 <= y < w):
        print("Possible" if (a == CHECKED).all() else "Impossible")
        exit()

    if not (0 <= x < h) or not (0 <= y < w) or m[x][y] == NOT_VISITED:
        return

    m[x][y] = CHECKED

    dfs(x, y + 1, m)  # 右を探索
    dfs(x + 1, y, m)  # 下を探索


h, w = [int(i) for i in input().split()]
a = np.array([list(input()) for _ in range(h)])

dfs(0, 0, a)
print(a)
print("Possible" if a[h - 1][w - 1] == CHECKED else "Impossible")

Submission status: Wrong Answer

Solution code:
import numpy as np

NOT_VISITED = '.'; CHECKED = '.'
VISITED = '#'

def dfs(x, y, m):
    if x == h - 1 and y == w - 1:
        m[x][y] = CHECKED
        print("Possible" if (a == CHECKED).all() else "Impossible")
        exit()

    if not (0 <= x < h) or not (0 <= y < w) or m[x][y] == NOT_VISITED:
        return

    m[x][y] = CHECKED

    dfs(x, y+1, m)  # 右を探索
    dfs(x+1, y, m)  # 下を探索


h, w = [int(i) for i in input().split()]
a = np.array([list(input()) for _ in range(h)])

dfs(0, 0, a)
print("Possible" if a[h-1][w-1] == CHECKED else "Impossible")

Submission status: Wrong Answer

Solution code:
import numpy as np

H,W = [int(zz) for zz in input().split()]
map = [list(input()) for _ in range(H)]

def dfs(h,w):
    if not (0<=h<=H-1 and 0<=w<=W-1) or map[h][w]=='.':
        return
    map[h][w]='.'
    if h == H-1 and w == W-1:
        for i in range(H):
            if '#' in map[i]:
                print('Impossible')
                exit()
    dfs(h+1,w)
    dfs(h,w+1)

dfs(0,0)
for i in range(H):
    if '#' in map[i]:
        print('Impossible')
        exit()
print('Possible')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(5000000)
H, W = [int(i) for i in input().split()]
A = ['a'*(W+2)]
for _ in range(H):
    A.append(''.join(['a', input(), 'a']))
A.append('a'*(W+2))


def search(h, w):
    if h == H and w == W:
        print("Possible")
        exit()
    if h < H and A[h+1][w] == "#" and A[h][w+1] != '#':
        search(h+1, w)
    if w < W and A[h][w+1] == "#" and A[h+1][w] != '#':
        search(h, w+1)


search(1, 1)

print("Impossible")

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = [int(zz) for zz in input().split()]
map = [list('.'+input()+'.') for _ in range(H)]

check = [[-1]*W for _ in range(H)]
q = deque([(0,0)])
check[0][0] = 0

while q:
    y,x = q.popleft()
    for i,j in [[1,0],[0,1]]:
        if y+i < H and x+j < W and check[y+i][x+j] == -1 and map[y+i][x+j] == '#':
            q.append([y+i,x+j])
            check[y+i][x+j] = check[y][x] + 1

li = []
for i in range(H):
    for j in range(W):
        if map[i][j] == '#':
            li.append(check[i][j])

if -1 in li:
    print('Impossible')
    exit()

if len(li) != len(set(li)):
    print('Impossible')
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = [int(zz) for zz in input().split()]
map = [list('.'+input()+'.') for _ in range(H)]

check = [[-1]*W for _ in range(H)]
q = deque([(0,0)])
map[0][0] = 0

while q:
    y,x = q.popleft()
    for i,j in [[1,0],[0,1]]:
        if y+i < H and x+j < W and check[y+i][x+j] == -1 and map[y+i][x+j] == '#':
            q.append([y+i,x+j])
            check[y+i][x+j] = check[y][x] + 1

li = []
for i in range(H):
    for j in range(W):
        if map[i][j] == '#':
            li.append(check[i][j])

if -1 in li:
    print('Impossible')
    exit()

if len(li) != len(set(li)):
    print('Impossible')
else:
    print('Possible')

Submission status: Wrong Answer

Solution code:
from collections import deque

H,W = [int(zz) for zz in input().split()]
map = [list('.'+input()+'.') for _ in range(H)]

check = [[-1]*W for _ in range(H)]
map[-1][-1] = 'G'
q = deque([(0,0)])
map[0][0] = 0

while q:
    y,x = q.popleft()
    for i,j in [[1,0],[0,1]]:
        if y+i < H and x+j < W and check[y+i][x+j] == -1 and map[y+i][x+j] == '#':
            q.append([y+i,x+j])
            check[y+i][x+j] = check[y][x] + 1

li = []
for i in range(H):
    for j in range(W):
        if map[i][j] == '#':
            li.append(check[i][j])

if -1 in li:
    print('Impossible')
    exit()

if len(li) != len(set(li)):
    print('Impossible')
else:
    print('Possible')

Submission status: Wrong Answer

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

for i in range(H+W-1):
  if i < W:
    x = i
    y = 0
  else:
    x = W-1
    y = i-x
  cnt = 0
  while(x > 0 and y < H):
    if A[y][x] == '#':
      cnt += 1
    #print(x,y,cnt)
    if cnt > 1:
      print('Impossible')
      exit()
    x -= 1
    y += 1
print('Possible')

Submission status: Wrong Answer

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

print('Possible')

Submission status: Wrong Answer

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

print('Possible')

Submission status: Wrong Answer

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

print('Possible')