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:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

h,w = inpl()
s = [list(input()) for i in range(h)]
cnt = 0
for i in s:
    cnt += i.count('#')
if cnt != h+w-1:
    print('Impossible')
    quit()
for fl in itertools.combinations(range(h+w-2),h-1):
    nx = 0; ny = 0
    for i in range(h+w-2):
        if i in fl:
            ny += 1
        else:
            nx += 1
        if s[ny][nx] == '#':
            continue
        break
    else:
        print('Possible')
        break
else:
    print('Impossible')

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    h, w = map(int, input().split())
    a = list()
    for i in range(h):
        a.append(input())

    count = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                count += 1

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

Submission status: Accepted

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

sp = 0
for line in A:
  if line.find("#") != sp:  
    print("Impossible")
    exit()
  sp = line.rfind("#")
print("Possible")

Submission status: Accepted

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

cnt = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            cnt += 1

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

Submission status: Accepted

Solution code:
def main():
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    cnt = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                cnt += 1
    if H+W-1 == cnt:
        print("Possible")
    else:
        print("Impossible")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            if max_h>i or max_w>j:
                print('Impossible')
                exit()
            else:
                max_h=max(max_h,i)
                max_w=max(max_w,j)
print('Possible')

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from sys import stdin,setrecursionlimit
from itertools import groupby
setrecursionlimit(10**7)
h,w = map(int,stdin.readline().rstrip().split())
li = [["" for i in range(w)]for j in range(h)]
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]
now = 0
last = 0
for i in range(h):
    flag = True
    for j in range(w):
        lin = []
        for key, value in groupby(li[i]):
            lin.append(key)
        if lin.count("#") >= 2:
            print("Impossible")
            exit()
        if li[i][j] == "#" and flag:
            flag = False
            now = j
        if i >= 1 and flag == False and now != last:
            print("Impossible")
            exit()
        if (flag == False and li[i][j] == "."):
            last = j-1
            break
        if  (not flag and j == w-1):
            last = j
            break
if last == w-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#大きさがN*Mの庭がある. そこに雨が降り, 水溜りができた.
#水溜りは8近傍で隣接している場合に繋がっているとみなす.
#全部でいくつの水溜りがあるか.(8近傍とは, 次のWに対する*の部分を指す)
# ***
# *W*
# ***
#"W"は水溜りを, "."は水溜りでない所を表すとする
#1<=n,m<=100
n,m=map(int,input().split())
s = [list(input()) for i in range(n)]
def dfs(x,y):
    c=False
    s[x][y]='.'
    for i in range(0,2):
        for j in range(0,2):
            if i==1 and j==1:
                continue
            nx=i+x
            ny=j+y
            if 0<=nx<n and 0<=ny<m and s[nx][ny]=='#':
                #print(nx,ny)
                c=True
                dfs(nx,ny)
            if c:
                break
        if c:
            break
ans=0
for i in range(n):
    for j in range(m):
        if s[i][j]=='#':
            #print("------------")
            #print(i,j)
            dfs(i,j)
            ans+=1
            #print(s)
if ans<=1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

min_ = 0
max_ = 0
for i in range(h):
    flag = 1
    for j in range(w):
        if flag == 1 and A[i][j] == '#':
            min_ = j
            if min_ < max_:
                print('Impossible')
                exit()
            flag = 0
        if flag == 0 and A[i][j] == '#':
            max_ = j
else:
    print('Possible')

Submission status: Accepted

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
            count = 0
            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))
                count += 1
            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))
                count += 1
            if count == 2:
                possible = False
                break
    else:
        if not visited[H-1][W-1]: possible = False
    print("Possible" if possible else "Impossible")

    return 0

if __name__ =="__main__":
    solve()

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
num=0
s=[str(input()) for i in range(h)]
for i in range(h):
  num+=s[i].count("#")
if num>h+w-1:
  print("Impossible")
  exit()
print("Possible")

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for i in range(H)]
    seen = [[0]*W for i in range(H)]

    def bfs(sy, sx):
        que = deque()

        seen[sy][sx] = 1
        que.append((sy, sx))
        d = ((1, 0), (0, 1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if seen[next_y][next_x] != 0:
                    continue
                if c[next_y][next_x] == '.':
                    continue
                seen[next_y][next_x] = 1
                que.append((next_y, next_x))
                break
    bfs(0, 0)
    num = 0
    cnt = 0
    for h in range(H):
        for w in range(W):
            if c[h][w] == "#":
                num += 1
            if seen[h][w] == 1:
                cnt += 1
    # print(*seen, sep="\n")
    if seen[-1][-1] == 1 and num == cnt:
        print("Possible")
    else:
        print("Impossible")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for _ in range(H)]
    cnt = sum([1 if A[i][j]=='#' else 0 for i in range(H) for j in range(W)])

    ans = False
    stack = [(0, 0, 1)]
    while stack:
        i, j, d = stack.pop()
        if i == H-1 and j == W-1:
            if d == cnt:
                ans = True
            break
        for di, dj in [(0,1), (1,0)]:
            ni, nj = i+di, j+dj
            if ni >= H or nj >= W: continue
            if A[ni][nj] != '#': continue
            stack.append((ni, nj, d+1))
    print('Possible' if ans else 'Impossible')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
a = [STR() for _ in range(h)]
nextstrtj = 0
for i in range(h):
    flag1 = False #.のあとに#が出たか
    flag2 = False ##が出たか
    for j in range(nextstrtj):
        if a[i][j] == '#':
            print('Impossible')
            exit()
    for j in range(nextstrtj, w):
        if flag1 and a[i][j] == '#':
            print('Impossible')
            exit()
        elif a[i][j] == '#':
            flag2 = True
            nextstrtj = j
        elif flag2 and a[i][j] == '.':
            flag1 = True
    if not flag2:
        print('Impossible')
        exit()

print('Possible')

Submission status: Accepted

Solution code:
# マンハッタン距離のように移動
# H + W - 1 ならPossible

H,W = map(int,input().split())

cnt = 0
for _ in range(H):
    cnt += list(input()).count("#")

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

Submission status: Accepted

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]
co=sum(i.count("#")for i in s)
if co!=h+w-1:print("Impossible")
elif ok[-1][-1]:print("Possible")
else:print("Impossible")

Submission status: Accepted

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-1:
    print("Impossible")
else:
    print("Possible")

Submission status: Accepted

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

field = [list(input()) for _ in range(H)]
count = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            count += 1
            
if count <= (H + W - 1):
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

Submission status: Accepted

Solution code:

h,w = map(int,input().split())
a = []
count = 0

for i in range(h):
    a.append(list(map(str,input().split())))

for j in range(h):
    c = str(a[j])
#    print(c)
    count += c.count("#")
#    print(count)

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

Submission status: Accepted

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 a[y-1][x] == "#" or a[y][x-1] == "#":
        f = False
    if f:
        print("Possible")
    else:
        print("Impossible")

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
moves = 0
for h in range(H):
  S = str(input())
  for s in S:
    if s == '#':
      moves += 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
maze = []
h, w = map(int,input().split())
for _ in range(h):
    maze.append(list(input()))
#print(maze)
x,y = 0,0
while True:
    maze[y][x] = "."
    if x == w-1 and  y == h-1:
        break
    if x != w-1 and maze[y][x+1]== "#":
        x += 1
        continue
    if y != h-1 and maze[y+1][x]=="#":
        y += 1
        continue
    break
from pprint import pprint
#pprint(maze)
f= True
for i in range(h):
    if maze[i].count("#") != 0:
        f = False
print("Impossible" if not f else "Possible")

Submission status: Accepted

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 = '.'
    rightup = '.'
    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 i != 0:
            rightup = mat[i-1][j+1]
    
    if down == right:
        print('Impossible')
        exit()
    elif down == '#': 
        if downleft == down:
            print('Impossible')
            exit()
        i+=1
    else: 
        if rightup == right:
            print('Impossible')
            exit()
        j+=1

print('Possible')

Submission status: Accepted

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

Submission status: Accepted

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('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

i = 0
j = 0
while i < H or j < W:
    if i < H-1 and A[i+1][j] == "#":
        i += 1
        A[i][j] = "."
    elif j < W-1 and A[i][j+1] == "#":
        j += 1
        A[i][j] = "."
    else:
        break

cnt = 0
for i in range(H):
    cnt += A[i].count("#")
if cnt == 1 and i == H-1 and j == W-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

Submission status: Accepted

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

rc = 0
for _ in range(h):
  rc += input().count('#')

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
data=[]
for i in range(h):
    a=input()
    data.append(a)
ans="Possible"
r=0
for i in range(h):
    for j in range(w):
        if data[i][j]=="#":
            if j<r:
                ans="Impossible"
                break
            else:
                r=j
    if ans=="Impossible":
        break
print(ans)

Submission status: Accepted

Solution code:
#shink and stone
h,w=map(int,input().split())
flag=True
dif=[]
for i in range(h):
    s=input()
    lists=[]
    for i in range(w):
        if s[i]=="#":
            lists.append(i+1)
    for i in range(len(lists)-1):
        if lists[i+1]-lists[i]>1:
            flag=False
            break
    dif.append((lists[0],lists[-1]))
if flag:
    subflag=True
    for i in range(h-1):
        if dif[i+1][0]!=dif[i][1]:
            subflag=False
            break
    if subflag:
        print("Possible")
    else:
        print("Impossible")
else:
    print("Impossible")

Submission status: Accepted

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

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

Submission status: Accepted

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

temp = 0
for i in range(h):
    temp += input().count('#')
print("Possible" if temp == h+w-1else "Impossible")

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
cnt = 0
for i 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())

A = [input() for _ in range(h)]

flag = True

#初期位置
x,y=0,0
for _ in range(h+w-2):
    #枠内にいることと現在位置の右隣が'#'であることを確認する
    if x+1 < h and A[x+1][y] == '#':
        #進む
        x += 1
        continue
    #枠内にいることと現在位置の直下が'#'であることを確認する
    if y+1 < w and A[x][y+1] == '#':
        #進む
        y += 1
        continue
    #一度でも上に引っかからなかったら
    flag = False
    break

flag = flag and (sum(x.count('#') for x in A) == h+w-1)
ans = 'Possible' if flag else 'Impossible'
print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(H):
    cnt += tb[i].count('#')

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

Submission status: Accepted

Solution code:
import numpy as np

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

print("Possible" if np.count_nonzero(a == '#') == h+w-1 else "Impossible")

Submission status: Accepted

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

r = 0
for j in range(W):
    if map[0][j] == "#":
        r = j
for i in range(1,H):
    flag = 1
    for j in range(W):
        if flag and map[i][j] == "#":
            if r != j:
                print('Impossible')
                exit()
            flag = 0
        elif map[i][j] == "#":
            r = j

print('Possible')

Submission status: Accepted

Solution code:
from collections import deque

# 下右1マスを検索するために必要とする
dis_x = [1, 0]
dis_y = [0, 1]

# 迷路の縦幅,横幅
max_h, max_w = map(int, input().split())

s = []
av_count = 0
for _ in range(max_h):
    line = input()
    av_count += line.count("#")
    # 横1マスを壁でPadding. これでindex out of boundを防ぐ
    s.append(list(".{}.".format(line)))

# 縦1マスを壁でPadding. これでindex out of boundを防ぐ
s = [list("." * (max_w + 2))] + s + [list("." * (max_w + 2))]

# 迷路と同じサイズの距離表を作成.
# 値が0 -> 未訪問, それ以外 -> スタート地点からそれまでの距離となる
dist = [ [0] * (max_w + 2) for _ in range(max_h+2)]

# キューにスタート地点をプッシュ
que = deque([(1, 1)])

# キューに値が格納されている間
while que:
    # 先頭の値を取り出す
    h, w = que.popleft()

    for i in range(2):
        # 移動距離
        dx, dy = dis_x[i], dis_y[i]
        if s[h+dy][w+dx] == '#' and dist[h+dy][w+dx] == 0:
            # ここまでの距離+1して訪問済みに
            dist[h+dy][w+dx] = dist[h][w] + 1
            # キューに加える -> (h+dy, w+dx) を起点にまた上下左右4マスをチェックする,という意味
            que.append((h+dy, w+dx))
            break

dist[1][1] = 1

dis = 0
for line in dist:
  dis += len(list(filter(lambda x : x != 0, line)))

print("Possible" if av_count == dis else "Impossible")

Submission status: Accepted

Solution code:
from collections import deque
H,W = 0,0
A,cost = [],[]
INF = float('inf')

def dfs(x,y):
    global H,W,A,cost,INF
    q = deque([[x,y]])
    dx = [1,0]
    dy = [0,1]
    while len(q) != 0:
        tmp = q.pop()
        x,y = tmp[0],tmp[1]
        for i in range(2):
            if 0 <= x+dy[i] < H and 0 <= y+dx[i] < W:
                if A[x+dy[i]][y+dx[i]] == "#" and cost[x+dy[i]][y+dx[i]] == INF:
                    cost[x+dy[i]][y+dx[i]] = cost[x][y]+1
                    q.append([x+dy[i],y+dx[i]])
                    break


def main():
    global H,W,A,cost,INF
    H,W = map(int,input().split())
    A = [list(input()) for _ in range(H)]
    cost = [[INF]*W for _ in range(H)]
    cost[0][0] = 0
    dfs(0,0)
    ans = "Possible"
    flag = False
    for i in range(H):
        if flag:
            break
        for j in range(W):
            if A[i][j] == "#" and cost[i][j] == INF:
                ans = "Impossible"
                flag = True
                break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

h, w = list(map(int, input().split()))
num = sum(Counter(input())['#'] for _ in range(h))
print('Possible' if w + h - 1 == num else 'Impossible')

Submission status: Accepted

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

cnt_j = 0
for i in range(H):
    for j in range(W):
        if(A[i][j] == "#"):
            if(cnt_j <= j):
                cnt_j = j
            else:
                print("Impossible")
                quit()
else:
    print("Possible")

Submission status: Accepted

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

grid = [[1 if i == '#' else 0 for i in input()] for _ in range(h)]

total = 0
for i in grid:
  total += sum(i)
  
  
if total == (h+w-1):
  print('Possible')
else:
  print('Impossible')

Submission status: Accepted

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

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

al = []

for _ in range(h):
   a = list(input())
   al.append(a)

i,j = 0,0
while True:
    al[i][j] = "."
    if j + 1 < w and al[i][j+1] == "#":
        al[i][j+1] = "."
        j += 1
    elif i + 1 < h and al[i+1][j] == "#":
        al[i+1][j] = "."
        i += 1
    else:
        print("Impossible")
        exit()
    if j == w-1 and i == h-1:
        break

for i in range(h):
    for j in range(w):
        if al[i][j] == '#':
            print("Impossible")
            exit()
print("Possible")

Submission status: Accepted

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

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

stack = [[0 for _ in range(w)] for _ in range(h)]

def dfs(y, x):
    stack[y][x] = 1
    if x == w-1 and y == h-1:
        return
    for i in range(2):
        ny = y + dy[i]
        nx = x + dx[i] 
        if ny < 0 or ny >= h or nx < 0 or nx >= w:
            continue
        if a[ny][nx] == "#":
            dfs(ny, nx)
            break
    return

dfs(0, 0)
for i in range(h):
    for j in range(w):
        if a[i][j] == "#" and stack[i][j] == 0:
            print('Impossible')
            exit()
print('Possible')

Submission status: Accepted

Solution code:
import sys

h,w=map(int,input().split())
m=[list(input()) for _ in range(h)]

s=[]

i_b,j_b=0,0
for i in range(h):
    for j in range(w):
        if m[i][j] =="#":
            if i<i_b or j<j_b:
                print("Impossible")
                sys.exit()
            else:
                i_b,j_b=i,j
print("Possible")

Submission status: Accepted

Solution code:
# A - Shik and Stone
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
from collections import deque
def bfs(sy,sx):
    q = deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x = q.popleft()
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if ny<0 or ny>h-1 or nx<0 or nx>w-1 or a[ny][nx]==".":
                continue
            if a[ny][nx]=="#" and visited[ny][nx]==-1:
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])
    ret=-1
    for i in range(h):
        for j in range(w):
            ret=max(visited[i][j],ret)
    return ret
h,w=nm()
a=[input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
dist=0
dist=bfs(0,0)
cnt=0
for aa in a:
    cnt+=aa.count('#')
if dist==h+w-2 and dist==cnt-1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
# AGC007a
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    h, w = map(int, input().split())

    cou = 0
    for _ in range(h):
        cou += input().count('#')
    if cou == h+w-1:
        print('Possible')
        exit(0)
    print('Impossible')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
H, W = map(int, input().split())
A = [input() for _ in range(H)]
homon = [[False]*W for _ in range(H)]
dx = [0, 1]
dy = [1, 0]

def dfs(x, y):
    homon[y][x] = True
    if x == W-1 and y == H-1:
        return
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if A[ny][nx] == '#':
            dfs(nx, ny)
            break
    return 

if __name__ == '__main__':
    dfs(0, 0)
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#' and homon[i][j] == False:
                print('Impossible')
                exit()
    print('Possible')

Submission status: Accepted

Solution code:
H,W = map(int, input().split())
A = [list(map(str, input())) for _ in range(H)]
cnt = 0
for i in range(H):
	for j in range(W):
		if A[i][j] == "#":
			cnt += 1

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

Submission status: Accepted

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

q = [[0,0]]

while q != []:
	ans = 0
	cx,cy = q.pop()
	A[cx][cy] = "."

	if [cx,cy] == [H-1,W-1]:
		ans = 1
		for i in range(H):
			for j in range(W):
				if A[i][j] == "#":
					ans = 0
		break

	nps = [[cx+1,cy],[cx,cy+1]]
	for nx,ny in nps:
		if 0 <= nx < H and 0 <= ny < W:
			if A[nx][ny] == "#":
				q.append([nx,ny])
				break

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
X = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]

Q = [0]
D = [[0] * W for _ in range(H)]
D[0][0] = 1
while Q:
    x = Q.pop()
    i, j = x//W, x%W
    for di, dj in ((1, 0), (0, 1)):
        ni, nj = i+di, j+dj
        if ni < H and nj < W and X[ni][nj]:
            if D[ni][nj] == 0:
                D[ni][nj] = 1
                Q.append(ni*W + nj)
if D[-1][-1] and sum([sum(x) for x in X]) == H + W - 1:
    print("Possible")
else:
    print("Impossible")