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:
H,W = map(int,input().split())
step = H+W-2
A = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  A.append(temp)
cnt = 0
for i in range(H):
  for j in range(W):
    if A[i][j] == "#":
      cnt += 1
if cnt == step+1:
  print("Possible")
else:
  print("Impossible")

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 err():
    print('Impossible')
    quit()
n,m = inpl()
g = [list(input()) for _ in range(n)]
su = 0
for i in range(n):
    for j in range(m):
        if g[i][j] == '#':
            su += 1 
if g[0][0] == '.' or su != n+m-1:
    err()
for fl in itertools.permutations(range(n+m-2), n-1):
    # print(fl)
    now = [0,0]
    for i in range(n+m-2):
        if i in fl:
            now[0] += 1
        else:
            now[1] += 1
        y,x = now
        if g[y][x] == '.':
            break
    else:
        print('Possible')
        quit()
err()

Submission status: Accepted

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

no = "Impossible"
h, w = 0, 0
while h < H-1 or w < W-1:
    if A[h][w] == ".":
        print(no)
        break
    A[h][w] = "."
    if h > 1:
        if A[h-1][w] == "#":
            print(no)
            break
    if w > 1:
        if A[h][w-1] == "#":
            print(no)
            break
    
    if h < H-1:
        if A[h+1][w] == "#":
            h += 1
            continue

    if w < W-1:
        if A[h][w+1] == "#":
            w += 1
            continue

else:
    A[H-1][W-1] = "."
    for i in range(H):
        if A[i].count("#") > 0:
            print(no)
            break
    else:
        print("Possible")

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
M = [list(str(input())) for _ in range(H)]

cnt = 0
for i in range(H):
    for j in range(W):
        if M[i][j]=="#":
            cnt += 1
if cnt!=H+W-1:
    print("Impossible")
else:
    def dfs(x, y):
        if x==W-1 and y==H-1:
            return 1
        ret = 0
        if x+1<W and M[y][x+1]=='#':
            ret += dfs(x+1, y)
        if y+1<H and M[y+1][x]=="#":
            ret += dfs(x, y+1)
        return ret
    
    if dfs(0, 0)>0:
        print('Possible')
    else:
        print('Impossible')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(input()) for i in range(N)) #改行行列

    mi=-1
    for s in S:
        f=0
        for i,si in enumerate(s):
            if f==0 and si=="#":
                if i >=mi:
                    mi=i
                    f=1
                else:
                    print('Impossible')
                    return
            elif f==1 and si==".":
                f=2
            elif f==1 and si=="#":
                mi=i
            elif f==2 and si=="#":
                print('Impossible')
                return

    print('Possible')






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

h,w=mp()
ans=0
for i in range(h):
    ans+=input().count("#")
if ans==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)]
cnt=0
for p in A:
    for q in p:
        if q=="#":
            cnt +=1

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

Submission status: Accepted

Solution code:
x,y=map(int,input().split())
failflag=0
m=[]
for i in range(x):
  m.append(input())
for i in range(x):
  for j in range(y):
    if m[i][j]=='#':
      if i<x-1 and j>0:
        if m[i+1][j-1]=='#':
          failflag=1
if failflag==0:
  print('Possible')
else:
  print('Impossible')

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
P=sum([list(input()).count('#') for i in range(H)])
if P==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)]
c=0
for i in a:
  for j in i:
    if j=="#":c+=1
if c==h+w-1:print("Possible")
else:print("Impossible")

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc007/tasks/agc007_a
# よく考えてみれば最短距離で進むということは、横にW-1回、縦にH-1回移動するのだから
# #に成るマス目は最初の1マスも含めてH+W-1個であるはずである。
# いま最初と最後は連結であることがわかっているのだから、個数だけ確かめれば良い
# https://atcoder.jp/contests/agc007/tasks/agc007_a
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_ints(): return list(map(int, read().split()))


def read_map_as(H, replace={'#': 1, '.': 0}, pad=None):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            # 内包表記はpypyでは若干遅いことに注意
            # #numpy使うだろうからこれを残しておくけど
    else:  # paddingする
        ret = [[pad] * (W + 2)]  # Wはどっかで定義しておくことに注意
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

# 常に右、下に動いていたなら、経路は一つに決まる。
# →#をたどってそれ以外に#があるかを判別すれば良い
H, W = read_ints()
A = read_map_as(H)
n_sharp = reduce(add, reduce(add, A))
print('Possible' if n_sharp == H + W - 1 else 'Impossible')

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc007/tasks/agc007_a
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_ints(): return list(map(int, read().split()))


def read_map_as(H, replace={'#': 1, '.': 0}, pad=None):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            # 内包表記はpypyでは若干遅いことに注意
            # #numpy使うだろうからこれを残しておくけど
    else:  # paddingする
        ret = [[pad] * (W + 2)]  # Wはどっかで定義しておくことに注意
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

# 常に右、下に動いていたなら、経路は一つに決まる。
# →#をたどってそれ以外に#があるかを判別すれば良い
H, W = read_ints()
A = read_map_as(H)
i, j = 0, 0
A[i][j] = 0
while i != H - 1 or j != W - 1:
    if i + 1 < H and j + 1 < W and A[i + 1][j] and A[i][j + 1]:
        print('Impossible')
        exit()
    ni = i
    nj = j
    if i + 1 < H and A[i + 1][j]:
        ni = i + 1
    if j + 1 < W and A[i][j + 1]:
        nj = j + 1
    if ni == i and nj == j:
        print('Impossible')
        exit()
    A[ni][nj] = 0  # 簡単のために0を埋めておく
    i, j = ni, nj

res = reduce(add, reduce(add, A))
# print(*A, sep='\n')
# print(res)
print('Possible' if res == 0 else 'Impossible')

Submission status: Accepted

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

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

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


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()))
k = 0
for j in range (A):
   k += L[j].count('#')
print('Possible' if A + B - 1 == k else 'Impossible')

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

H,W = I()
maze = [list(s()) for _ in range(H)]
visited = [[-1]*W for _ in range(H)]

def dfs(x,y):
    if x < 0 or y < 0 or x >= H or y >= W:
        return
    if visited[x][y] != -1:
        return
    if maze[x][y] == '.':
        return
    visited[x][y] = 1
    dfs(x+1,y)
    dfs(x,y+1)

dfs(0,0)
cnt = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            cnt += 1
if visited[-1][-1] == -1:
    print('Impossible')
elif cnt == 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)]
h = 0
w = 0
ans = 'Possible'
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      if (i == h and j - w < 2) or (i - h < 2 and j == w):
        h = i
        w = j
      else:
        ans = 'Impossible'
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H, W = map(int, readline().split())
n = read().count(b'#')
print('Possible' if n == H + W - 1 else 'Impossible')

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
a=[]
for i in range(h):
    sub=input().rstrip()
    a.append(sub)
check=True
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            for k in range(h):
                for l in range(w):
                    if (i>k and j<l) or (i<k and j>l):
                        if a[k][l]=='#':
                            check=False
if check:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
from itertools import permutations

h,w = map(int,input().split())
nec = []
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == "#":
            nec.append([i,j])

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

Submission status: Accepted

Solution code:
def check(grid, h, w):
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                return False
    return True


def main():
    h, w = map(int, input().split())

    grid = []
    for _ in range(h):
        grid.append(list(input()))
    # 右、下、左、上
    dy = [0, 1]
    dx = [1, 0]
    stack = [[0, 0]]
    grid[0][0] = 'D'
    while stack:
        y, x = stack.pop()
        for i in range(2):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if 0 <= next_y < h and 0 <= next_x < w and grid[next_y][next_x] == '#':
                grid[next_y][next_x] = 'D'
                stack.append([next_y, next_x])
                break
    if check(grid, h, w):
        print('Possible')
        return
    print('Impossible')

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def dfs(h,w,c):
  if h == H - 1 and w == W - 1:
    return c + 1

  if H - 1 < h or W -1 < w:
    return 0
  
  if GRID[h][w] != "#":
    return 0
  
  
  right = dfs(h+1,w,c+1)
  down = dfs(h,w+1,c+1)

  return max(right,down)

NUM = sum([GRID[x].count("#") for x in range(H)])

n = dfs(0,0,0)

if n == NUM:
  print("Possible")
else:
  print("Impossible")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque

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

slst = [[] for _ in range(H)]
for i in range(H):
  for j in range(W):
    if Map[i][j] == '#':
      slst[i].append(j)

m = 0
for i in range(1,H):
  if slst[i-1][-1] != slst[i][0]:
    print('Impossible')
    exit()
    
print('Possible')

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
maze = [input() for _ in range(h)]
total = 0
for maz in maze:
    for m in maz:
        if m == "#":
            total += 1

ans = False
def search(x,y,count):
    global ans
    if x == w-1 and y == h-1 and maze[y][x] == "#" and total == count:
        ans = True
        return
    if x < w-1 and maze[y][x+1] == "#":
        search(x+1,y,count+1)
    if y < h-1 and maze[y+1][x] == "#":
        search(x,y+1,count+1)

if maze[0][0] == "#":
    search(0,0,1)
if ans:print("Possible")
else:print("Impossible")

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

# ここから書き始める
h, w = map(int, input().split())
a = [[j for j in input()] for i in range(h)]
# print(a)
y = 0
x = 0
b = [["." for j in range(w)] for i in range(h)]
while True:
    b[y][x] = "#"
    if x < w - 1 and a[y][x + 1] == "#":
        x += 1
    elif y < h - 1 and a[y + 1][x] == "#":
        y += 1
    else:
        break
for i in range(h):
    for j in range(w):
        if a[i][j] == "#" and b[i][j] == ".":
            print("Impossible")
            sys.exit()
print("Possible")

Submission status: Accepted

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

a = [list(input()) for _ in range(h)]
cnt = 1
for x in range(h):
    for y in range(w):
        if a[x][y] == '#':
            cnt += 1
            

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

Submission status: Accepted

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

ans='Possible'
for i in range(h-1):
    for j in range(w-1):
        if r[i][j]=='#'and r[i][j+1]=='#' and r[i+1][j]=='#' and r[i+1][j+1]=='#':
            ans='Impossible'
        elif r[i][j]=='.' and r[i][j+1]=='#' and r[i+1][j]=='#' and r[i+1][j+1]=='#':
            ans='Impossible'
        elif r[i][j]=='#' and r[i][j+1]=='#' and r[i+1][j]=='#' and r[i+1][j+1]=='.':
            ans='Impossible'

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (0,1)}
init_q =[]

from collections import deque

def bfs(init):
    next_q = deque([])
    for i in init:
        next_q.append(i)
        Dist[i[0]][i[1]] = 1

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h,w = next_q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            if Gmap[hs][ws]=='#' and Dist[hs][ws]==INF:
                next_q.append([hs,ws])
                Dist[hs][ws] = Dist[h][w] + 1
    return Dist

def main():
    #固定
    init_q.append([sth, stw])

    ret = bfs(init_q)
    if ret[glh][glw]>0 and ret[glh][glw]==sum([a.count('#') for a in Gmap]):
        print('Possible')
    else:
        print('Impossible')

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = [list(str(input())) for _ in range(H)]
for i in range(H):
  A[i] += '.'
A += [list('.'*(W+1))]
y,x = 0,0
ans = 'Impossible'
while y < H and x < W:
  if A[y+1][x] == '#' and A[y][x+1] == '#':
    break
  elif A[y+1][x] == '#':
    if '#' in A[y][x+1:] or '#' in A[y+1][:x]:
      break
    y += 1
  elif A[y][x+1] == '#':
    x += 1
  else:
    break
  if y == H-1 and x == W-1:
    ans = 'Possible'
    break
print(ans)

Submission status: Accepted

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

field = [list(input()) for i in range(h)]

cnt = 0

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import collections

def main():
    h, w = input_list()
    masu = []
    c = 0
    for _ in range(h):
        c += input().count('#')
    if h + w - 1 == c:
        print('Possible')
    else:
        print('Impossible')

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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    from collections import deque
    input = stdin.readline

    h, w = map(int, input().split())
    cm = [["."] * (w + 2) for _ in range(h + 2)]
    que = deque([])
    for i in range(1, h + 1):
        cm[i] = "." + input().rstrip('\n') + "."
    que.append([1, 1])
    while len(que) > 0:
        y, x = que.popleft()
        if (cm[y + 1][x] == "#" and cm[y][x + 1] == "#") or cm[y + 1][x - 1] == "#" or cm[y - 1][x + 1] == "#":
            print('Impossible')
            exit()
        if cm[y + 1][x] == "#":
            que.append([y + 1, x])
        if cm[y][x + 1] == "#":
            que.append([y, x + 1])
    print('Possible')
main()

Submission status: Accepted

Solution code:
h, w =map(int, input().split())
grid = [None]*h
count = -1
for i in range(h):
  grid[i] = input()
  count += grid[i].count("#")

x, y = 0, 0

while True:
  if x == h-1 and y == w-1:
    if count == 0:
      print("Possible")
    else:
      print("Impossible")
    break
  elif x == h-1:
    if grid[x][y+1] == ".":
      print("Impossible")
      break
    y += 1
    count -= 1
  elif y == w-1:
    if grid[x+1][y] == ".":
      print("Impossible")
      break
    x += 1
    count -= 1
  else:
    if grid[x+1][y] == grid[x][y+1]:
      print("Impossible")
      break
    if grid[x+1][y] == "#":
      x += 1
    else:
      y += 1
    count -= 1

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
point = 0
for _ in range(h):
    s = input()
    point += s.count("#")

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]

cnt_w = sum([X.count("#") for X in A])

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

H, W = MAP()
A = [input() for _ in range(H)]

cnt_w = sum([X.count("#") for X in A])

def DFS(y, x, cnt):
	if 0 <= x+1 <= W-1 and A[y][x+1] == "#":
			return DFS(y, x+1, cnt+1)
	elif 0 <= y+1 <= H-1 and A[y+1][x] == "#":
			return DFS(y+1, x, cnt+1)
	else:
		return (y, x, cnt)

if A[0][0] != "#":
	print("Impossible")
elif (H-1, W-1, cnt_w) == DFS(0, 0, 1):
	print("Possible")
else:
	print("Impossible")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

H,W = map(int,readline().split())
r = 0
for i in range(H):
  r += readline().rstrip().count("#")
  
if r != H + W - 1:
  print("Impossible")
else:
  print("Possible")

Submission status: Accepted

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

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

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

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)]
    count = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#": count += 1
    print("Possible" if count == H + W - 1 else "Impossible")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
r = 0
c = 0
for i in range(H):
    for j in range(1,W):
        if A[i][j]==A[i][j-1]=="#":
            r += 1
for j in range(W):
    for i in range(1,H):
        if A[i][j]==A[i-1][j]=="#":
            c += 1
if r==W-1 and c==H-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
b = 0
ans = 'Possible'
for i in range(H):
  a = input()
  for j in range(W):
    if a[j] == '#':
      if j>=b:
        b = j
      else:
        ans = 'Impossible'
print(ans)

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
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
h,w = readInts()
A = [input() for _ in range(h)]
cnt = 0
for y in range(h):
    for x in range(w):
        if A[y][x] == '#':
            cnt += 1
if h + w - 1 == cnt:
    print('Possible')
else:
    print('Impossible')