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: Accepted

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
            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(answer(matrix))

Submission status: Accepted

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

visited = [[False]*W for i in range(H)]
visited[0][0] = True
d = [[0, 0, -1, -1]]
while d:
  x, y, px, py = d.pop()
  num = 0
  flag = False
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    if 0<=x+dx<H and 0<=y+dy<W and [x+dx, y+dy]!=[px, py] and A[x+dx][y+dy]=='#' and not visited[x+dx][y+dy]:
      visited[x+dx][y+dy] = True
      num += 1
      d.append([x+dx, y+dy, x, y])
      if dx < 0 or dy < 0:
        flag = True
  if (num >= 2) or flag:
    print('Impossible')
    quit()

print('Possible')

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
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 fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W=MI()
    grid=[ST() for _ in range(H)]
    
    ans = True
    stack = [(0,0)]
    visited = set()
    while(stack):
        v = stack.pop()
        visited.add(v)
        for dh,dw in [(-1,0), (1,0), (0,-1), (0,1)]:
            to_h,to_w = v[0]+dh, v[1]+dw
            if(not(0<=to_h<H) or not(0<=to_w<W)):
                continue
            if(to_h,to_w) in visited:
                continue
            if(grid[to_h][to_w] == "#" and -1 in (dh,dw)):
                ans = False
            if(grid[to_h][to_w] == "#"):
                stack.append((to_h,to_w))
        if(len(stack) >= 2): 
            ans = False   
    if(ans):
        print("Possible")
    else:
        print("Impossible")
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# '#'の数がH+W-1

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    h,w = map(int, input().split())
    s = 0
    for _ in range(h):
        a = input().rstrip()
        s += a.count('#')

    if s == h+w-1:
        print('Possible')
    else:
        print('Impossible')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    h,w = map(int, input().split())
    a = [list(input().rstrip()) for _ in range(h)]
    
    s = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                if s != j:
                    print('Impossible')
                    exit()
                s +=  1
        s -= 1

    if s == w-1:
        print('Possible')
    else:
        print('Impossible')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
M = []
ans = []

def main():
    H,W = map(int, input().split())  
    for i in range(H):
        M.append(input())
        ans.append('.' * W)

    bfs(0,0)

    for i in range(H):
        if(M[i] != ans[i]):
            print('Impossible')
            return
    print('Possible')


def bfs(x,y):
    if(x>=len(M) or y>=len(M[0])):
        return False
    if(M[x][y]=='#'):
        str_list = list(ans[x])
        str_list[y] = '#'
        ans[x] = "".join(str_list) 
        if(bfs(x,y+1) & bfs(x+1,y)):
            #失敗にする、気持ち悪いけど楽…
            str_list = list(ans[0])
            str_list[0] = '.'
            ans[0] = "".join(str_list) 
        return True
    return False


if __name__ == '__main__':
    main()

Submission status: Accepted

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

x = 1
y = 1

flag = 1
while flag:
    li[y][x] = 'o'

    if li[y][x+1] == '#':
        x += 1
    elif li[y+1][x] == '#':
        y += 1
    else:
        break

for i in range(h+2):
    for j in range(w+2):
        if li[i][j] == '#':
            print('Impossible')
            break
    else:
        continue
    break
else:
    print('Possible')

Submission status: Accepted

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

Submission status: Accepted

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

r = 0

for a in A:
    flag = False
    if '#' in a[:r]:
        print('Impossible')
        exit()
    for i in range(r, W):
        if a[i] == '#':
            if flag:
                print('Impossible')
                exit()
            r = i
        else:
            flag = True
            
print('Possible')

Submission status: Accepted

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

tmp=0
for i in range(h):
    for j in range(w):
        if field[i][j]=='#':
            tmp+=1
if (h+w-1)==tmp:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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:
          cou = 0
          for i in l:
            for j in i:
              if j=="#":
                cou += 1
          if cou==2:
            return print("Possible")
          else:
            return print("Impossible")
        else:
          l[b+m[i]][a+n[i]] = "."
          #print(l)
          return dfs(a+n[i],b+m[i])
  else:
    return print("Impossible")
      
    
        
dfs(0,0)

Submission status: Accepted

Solution code:
# AGC057 A Shik and Stone
from collections import Counter

h,w = map(int, input().split())

_list = []
for i in range(h):
    _list += list(input())

if _list.count("#") == (h+w-1):
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
h,w=map(int,input().split());print(("Imp"if sum(input().count("#")for i in[0]*h)!=h+w-1 else"P")+"ossible")

Submission status: Accepted

Solution code:
h,w=map(int,input().split());print(("Imp"if sum(input().count("#")for i in [0]*h)!=h+w-1 else "P")+"ossible")

Submission status: Accepted

Solution code:
import sys
h, w = map(int, input().split())
a = [input() for i in range(h)]
t = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            if j < t:
                print("Impossible")
                sys.exit()
            t = j
print("Possible")

Submission status: Accepted

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: Accepted

Solution code:
import sys
h,w = map(int,input().split())
A = []
for i in range(h):
    A.append(list(input()))
dx = [1,0,]
dy = [0,1,]
B = [[0,0]]
while B:
    S = B.pop()
    cnt = 0
    if S == [w-1,h-1]:
        A[h-1][w-1] = "."
        for L in A:
            if L.count("#") != 0:
                print("Impossible")
                sys.exit()
        else:
            print("Possible")
            break
    for i in range(2):
        x = S[0] + dx[i]
        y = S[1] + dy[i]
        if 0 <= x <= w-1 and 0 <= y <= h-1 and A[y][x] == "#":
            B.append([x,y])
            cnt += 1
    else:
        if cnt != 1:
            print("Impossible")
            break
        else:
            A[S[1]][S[0]] = "."

Submission status: Accepted

Solution code:
H, W = [int(hoge) for hoge in input().split()]
print("Possible") if sum([input().count("#") for h in range(H)]) == H+W-1 else print("Impossible")

Submission status: Accepted

Solution code:
def solve():
    H, W = map(int, input().split())
    A = [[i for i in input()] for _ in range(H)]
    
    x, y = 0, 0
    A[y][x] = '.'
    while True:
        if 0 <= x+1 < W and 0 <= y < H and A[y][x+1] == '#':
            x=x+1
            A[y][x] = '.'
        elif 0 <= x < W and 0 <= y+1 < H and A[y+1][x] == '#':
            y=y+1
            A[y][x] = '.'
        else:
            break
    
    for row in A:
        if '#' in row:
            return 'Impossible'

    return 'Possible' if x == W-1 and y == H-1 else 'Impossible'

print(solve())

Submission status: Accepted

Solution code:
import sys

H, W = map(int, sys.stdin.readline().strip().split())

grid = []
for _ in range(H):
    grid.append(list(sys.stdin.readline().strip()))

count = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            count += 1

if count == H + W - 1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
N,M=map(int,input().split(' '))
maze = [list(input()) for i in range(N)]
tmp = 0
for i in range(N):
    tmp += maze[i].count('#')
if tmp == N+M-1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
from itertools import chain

H, W = map(int, input().split())
count = 0
for _ in range(H):
    l = list(input())
    count += l.count("#")

if count == H+W - 1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
l=[]
for _ in range(a):
    l1=input()
    l.append(l1)
flag=True
for i in range(b):
    for j in range(a):
        if i>=1 and j!=a-1 and l[j][i]=='#':
            for k1 in range(i):
                for k2 in range(j+1,a):
                    if l[k2][k1]=='#':
                        flag=False
                        break
for i in range(b):
    for j in range(a):
        if i!=b-1 and j>=1 and l[j][i]=='#':
            for k3 in range(j):
                for k4 in range(i+1,b):
                    if l[k3][k4]=='#':
                        flag=False
                        break
if flag==True:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
def myAnswer(H:int,W:int,A:list) -> str:
   counter = 0
   for a in A:
      counter += a.count("#")
   return "Possible" if(counter == H + W - 1) else "Impossible"

   # i = 0
   # j = 0
   # if(A[i][j] == "." or A[H-1][W -1] == "."):return "Impossible"
   # while True:
   #    print(i,j)
   #    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: Accepted

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: Accepted

Solution code:
# 631

h, w = map(int, input().split())
a = [str(input()) for _ in range(h)]
jud = [[] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            jud[i].append(j)

# print(jud)

flag = True

for k in range(len(jud) - 1):
    if max(jud[k]) in jud[k + 1] and jud[k][-1] == jud[k + 1][0]:
        continue
    else:
        flag = False

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

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    h, w = ns()
    mat = [list(sys.stdin.readline()) for _ in range(h)]

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

    if cnt != total:
        print("Impossible")
        exit(0)

    def dfs(x, y):
        if x == w-1 and y == h-1:
            print("Possible")
            exit(0)

        if x + 1 < w:
            if mat[y][x + 1] == "#":
                dfs(x + 1, y)
        if y + 1 < h:
            if mat[y + 1][x] == "#":
                dfs(x, y + 1)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# A - Shik and Stone

H, W = map(int, input().split())
now = 0
judge = 0

for h in range(H):
    route = input()
    w = 0
    while w<W and route[w]=='.':
        w += 1
    if w!=now:
        break
    while w<W-1 and route[w+1]=='#':
        w += 1
    now = w
    while w<W-1 and route[w+1]=='.':
        w += 1
    if w<W-1:
        break
    if h==H-1 and now==W-1:
        judge = 1

ans = ['Impossible', 'Possible']
print(ans[judge])

Submission status: Accepted

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

Submission status: Accepted

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

  count = 0

  for i in range(H):
    row = input()
    for j in range(W):
      if(row[j] == '#'):
        count += 1

  print("Possible" if W + H - 1 == count else "Impossible")

if __name__ == "__main__":
  main()

Submission status: Accepted

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

  count = 0

  for i in range(H):
    row = input()
    for j in range(W):
      if(row[j] == '#'):
        count += 1

  print("Possible" if W + H - 1 == count else "Impossible")

if __name__ == "__main__":
  main()

Submission status: Accepted

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

ans = "Possible"
for i in range(h-1):
    for j in range(w-1):
        if a[i][j+1] == a[i+1][j] == "#":
            ans = "Impossible"
            break
print(ans)

Submission status: Accepted

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

now_x = 0
now_y = 0
while(True):
    if now_x+1 <w and a[now_y][now_x+1] == "#":
        a[now_y][now_x] = "."
        now_x+=1

    elif now_y+1 <h and a[now_y+1][now_x] == "#":
        a[now_y][now_x] = "."
        now_y+=1

    else:
        a[now_y][now_x] = "."
        break

check = True
for i in a:
    for j in i:
        if j == "#":
            check = False

print("Possible" if check else "Impossible")

Submission status: Accepted

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 = H
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: Accepted

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

from collections import deque
queue = deque([((0,0), [])])

cand = []
while queue:
  p, path = queue.popleft()
  x, y = p
  path = path + [p]
  for dx,dy in D:
    nx,ny = x+dx, y+dy
    if not (0<=nx < h and 0<= ny < w):
      continue
    if A[nx][ny] != '#':
      continue
    if nx == h-1 and ny == w-1:
      cand.append(path+[(nx,ny)])
      continue
    queue.append(((nx,ny),path))

for c in cand:
  for i in range(h):
    for j in range(w):
      if A[i][j] == '.':
        continue
      elif (i,j) not in c:
        break
    else:
      continue
    break
  else:
    print('Possible')
    break
else:
  print('Impossible')

Submission status: Accepted

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, input().split())
    c = 0
    for _ in range(h):
        a = list(input())
        c += a.count("#")
    print(("Possible" if c == h + w - 1 else "Impossible"))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
h , w = map(int,input().split())
ma = [list(input()) for i in range(h)]
ans = []
for i in range(h):
    kar = []
    for j in range(w):
        if ma[i][j] =="#":
            kar.append(j)
    ans.append(kar)


for i in range(h-1):
    if max(ans[i]) != min(ans[i+1]):
        print("Impossible")
        exit()
        
print("Possible")

Submission status: Accepted

Solution code:
import numpy as np
h, w = map(int,input().split())
way = []
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == "#":
            way.append([i,j])

for i in range(len(way)-1):
    if (way[i+1][0]-way[i][0])+(way[i+1][1]-way[i][1]) == 1 and (way[i+1][0]-way[i][0])*(way[i+1][1]-way[i][1]) == 0:
        continue
    else:
        print("Impossible")
        exit()

print("Possible")

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    H, W = [int(item) for item in input().split()]

    grid = [[item for item in input()] for _ in range(H)]

    cnt = 0
    for line in  grid:
        for i in line:
            if i == '#':
                cnt += 1

    if cnt > H + W -1:
        print('Impossible')
    else:
        print('Possible')

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

pos = (0, 0)
pre = 1
nxt = 0
while True:
    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 pos==(w-1, h-1) and nxt==0 and pre==1:
        print('Possible')
        break
    if nxt!=1 or pre!=1:
        print('Impossible')
        break
    pre = 0
    nxt = 0

Submission status: Accepted

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:
    tmp = 0
    for i in a:
        tmp += i.count('#')
    if tmp!=h+w-1:
        print('Impossible')
    else:
        print('Possible')

Submission status: Accepted

Solution code:
import collections
h,w = map(int,input().split())
a = []
cnt = 0
for i in range(h):
    aa = list(input())
    c = collections.Counter(aa)
    cnt += c['#']
    a.append(aa)
cnt -= 1
if cnt == h+w-2:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

import numpy as np

input = sys.stdin.readline


def bfs(H, W, maze, dist, sh, sw):
    queue = deque([[sh, sw]])
    dist[sh][sw] = 0
    while queue:
        h, w = queue.popleft()
        for i, j in [(1, 0), (0, 1)]:
            next_h, next_w = h + i, w + j
            if not ((0 <= next_h <= H - 1) and (0 <= next_w <= W - 1)):
                continue
            if maze[next_h][next_w] and (dist[next_h][next_w] == -1):
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append([next_h, next_w])


def main():
    H, W = map(int, input().split())
    A = np.full((H, W), False, dtype=bool)
    for i in range(H):
        A[i] = [True if s == "#" else False for s in input().rstrip()]

    n_path = np.sum(A) - 1
    dist = [[-1] * W for _ in range(H)]
    bfs(H, W, A, dist, 0, 0)

    if dist[H-1][W-1] == n_path:
        print("Possible")
    else:
        print("Impossible")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    H, W = (int(_) for _ in input().split())
    board = [input() for _ in range(H)]
    num = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == '#': num += 1

    def dfs(x, y, n):
        if x == H-1 and y == W-1: return n == num
        nx = x + 1
        if 0 <= nx < H and board[nx][y] == '#':
            if dfs(nx, y, n+1):
                return True
        ny = y + 1
        if 0 <= ny < W and board[x][ny] == '#':
            if dfs(x, ny, n+1):
                return True
        return False

    print('Possible' if dfs(0, 0, 1) else 'Impossible')
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

x, y = 0, 0
px, py = 0, 0
while not (x == w-1 and y == h-1):
    if not (x == 0 and y == 0):
        if px == x and py == y:
            print('Impossible')
            exit()
    px, py = x, y
    # → を検索
    if not x+1 > w-1:
        if a[y][x+1] == '#':
            a[y][x] = '.'
            x += 1
            continue
    # ↓ を検索
    if not y+1 > h-1:
        if a[y+1][x] == '#':
            a[y][x] = '.'
            y += 1
            continue

ans = True

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            if i == h-1 and j == w-1:
                pass
            else:
                ans = False

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

Submission status: Accepted

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[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==[H-1,W-1]:
    print("Possible")
    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: Accepted

Solution code:
H, W = map(int, input().split())
cnt = 0
for _ in range(H):
    s = input()
    cnt += s.count('#')

if cnt == H + W - 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
h,w,= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

cnt = 0
for i in range(h):
    cnt += input().count('#')

short = h+w-1

if cnt == short:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
cnt = 0
for i in range(H):
    A = input()
    cnt += A.count('#')
if (H + W - 1 == cnt): print('Possible')
else: print('Impossible')

Submission status: Accepted

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:
            if FIELD[y][x-1] == '#' and not ARRIVED[y][x-1]:
                print('Impossible')
                exit()
            else:
                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: Accepted

Solution code:
h,w = map(int,input().split())
ma = []
count = 0
for _ in range(h):
    tmp_li = list(input())
    for t in tmp_li:
        if t == '#':
            count += 1
    ma.append(tmp_li)
if count != w+h-1:
    print('Impossible')
    exit()
if ma[0][0]!= '#':
    print('Impossible')
    exit()

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: Accepted

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

cnt = 0
for v in A:
	cnt += v.count('#')

print('Possible') if cnt == h + w - 1 else print('Impossible')