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

a = [input() for _ in range(H)]

for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            x = i-1
            y = j+1

            if 0 <= x < H and 0 <= y < W:
                if a[x][y] == "#":
                    print("Impossible")
                    exit()
            
            x = i+1
            y = j-1
            if 0 <= x < H and 0 <= y < W:
                if a[x][y] == "#":
                    print("Impossible")
                    exit()
print("Possible")

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
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 = [input() for _ in range(H)]

cnt = 0
for a in A:
    cnt += a.count("#")
print("Possible" if cnt == W + (H-1) else "Impossible")

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
cnt = 0
for i in range(h):
    ai = input()
    for j in range(w):
        if ai[j] == '#':
            cnt += 1

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
H,W = IL()
data = SLs(H)

now = 0
for i in range(H):
  flag = 0
  for j in range(now,W):
    if data[i] == "."*now + "#"*(j+1-now) + "."*(W-(j+1)):
      now = j
      flag = 1
      break
  if flag == 0:
    print("Impossible")
    exit()
print("Possible")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[]
c=0
for i in range(h):
  a.append(input())
  c+=a[i].count('#')
flg=0
if c != h+w-1:
  flg=1
dh=0
dw=0
for i in range(h+w-2):
  if dh==h-1:
    if a[dh][dw+1]=='#':
      dw+=1
  elif dw==w-1:
    if a[dh+1][dw]=='#':
      dh+=1
  else:
    if a[dh+1][dw]=='#':
      dh+=1
    elif a[dh][dw+1]=='#':
      dw+=1
    else:
      flg=1
if flg==0:
  print('Possible')
else:
  print('Impossible')

Submission status: Accepted

Solution code:
def main():
    h,w=map(int,input().split())
    a=[]
    for _ in range(h):
        a.append(input())
    now = (0, 0)
    end = (h-1, w-1)
    visited = set([now])
    while True:
        nxt = None
        #print(now)
        if now[0]+1 < len(a) and a[now[0]+1][now[1]] == "#":
            nxt = (now[0]+1, now[1])
        if now[1]+1 < len(a[now[0]]) and a[now[0]][now[1]+1] == "#":
            if nxt is not None:
                print("Impossible")
                return
            nxt = (now[0], now[1]+1)
        #print("next", nxt)
        if now[0]-1 >= 0 and a[now[0]-1][now[1]] == "#":
            if (now[0]-1,now[1]) not in visited:
                print("Impossible")
                return
        if now[1]-1 >= 0 and a[now[0]][now[1]-1] == "#":
            if (now[0],now[1]-1) not in visited:
                print("Impossible")
                return
        
        if now == end:
            break
        if nxt is None:
            print("Impossible")
            return
        now = nxt
        visited.add(nxt)
    print("Possible")
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
a = []
cnt = 0
for _ in range(h):
    a.append(list(input()))
    cnt += a[-1].count("#")
looked = [[True for _ in range(w)]for i in range(h)]
looked[0][0] = False
x,y = 0,1
now = [0,0]
ans = 1

while(True):
    look = [[min(now[y]+1,h-1),now[x]],[now[y],min(now[x]+1,w-1)]]
    flag = 1
    for i in range(2):
        if looked[look[i][x]][look[i][y]]:
            if a[look[i][x]][look[i][y]] == "#":
                now = [look[i][y],look[i][x]]
                looked[look[i][x]][look[i][y]] = False
                ans += 1
                flag = 0
                break
    if flag:
        break
if ans == cnt and now == [w-1,h-1]:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# sys.setrecursionlimit(int(pow(10, 2)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]
# @lru_cache(None)






h,w=l()
A=[input() for i in range(h)]
ans=0
for i in range(h):
    for j  in  range(w):
        if(A[i][j]=="#"):
            ans+=1



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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
left = 0
ok = True
flag = "ok"
for i in range(h):
    dum = input()
    for j in range(0,w):
        if j < left and dum[j] == "#":
            print("Impossible")
            exit()
        if dum[j] == "#":
            left_o = j
            flag = "ng"
    left = left_o
    flag = "ok"
print("Possible")

Submission status: Accepted

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

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
    
Flag= Flag and (sum(x.count("#") for x in A)==H+W-1)
if Flag:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
list1=[]
ans=0
count1=0
count2=0
count3=0
for i in range(h):
    list1.append(list(input()))
for i in range(h):
    count3+=list1[i].count("#")
if count3!=h+w-1:
    ans=1
for i in range(h+w-3):
    if count2!=w-1:
        if list1[count1][count2+1]=="#":
            count2+=1
    if count1!=h-1:
        if list1[count1+1][count2]=="#":
            count1+=1
    if count2!=w-1:
        if count1!=h-1:
            if list1[count1+1][count2]=="." and list1[count1][count2+1]==".":
                ans=1
                break
        else:
            if list1[count1][count2+1]==".":
                ans=1
                break
    elif count1!=h-1:
        if list1[count1+1][count2]==".":
            ans=1
            break
if count1!=h-1 or count2!=w-1:
    ans=1
if h==2 and w==2:
    if list1[0][0]=="#" and list1[1][1]=="#" and count3==3:
        ans=0
if ans==1:
    print("Impossible")
else:
    print("Possible")

Submission status: Accepted

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

edge = [["." for _ in range(W+2)]]
center = [["."] + list(input()) + ["."] for i in range(H)]
A_array = edge + center + edge

def is_there_OK_move(before_i,before_j,before_move):
    if before_move == "right":
        i = before_i
        j = before_j + 1
    elif before_move == "down":
        i = before_i + 1
        j = before_j

    up = A_array[i-1][j]
    down = A_array[i+1][j]
    right = A_array[i][j+1]
    left = A_array[i][j-1]
    
    if i == H and j == W:
        if up == left == "#":
            return -1
        else:
            return 1
    elif (down == right == "#") or (before_move == "right" and up == "#") or (before_move == "down" and left == "#"):
        return -1
    else:
        if down == "#":
            return is_there_OK_move(i,j,"down")
        elif right == "#":
            return is_there_OK_move(i,j,"right")


ans = is_there_OK_move(0,1,"down")

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

Submission status: Accepted

Solution code:
def main():
    h, w = list(map(int, input().split()))
    A = [['.'] * (w + 2)] + [['.', ] + list(input()) + ['.', ] for _ in range(h)] + [['.'] * (w + 2)]
    i, j = 1, 1
    while True:
        A[i][j] = '.'
        if i == h and j == w:
            break
        if A[i + 1][j] == A[i][j + 1]:
            print('Impossible')
            exit()
        if A[i + 1][j] == '#':
            i += 1
        else:
            j += 1
    for a in A:
        if any([i == '#' for i in a]):
            print('Impossible')
            break
    else:
        print('Possible')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

h,w = iim()
l = []
for _ in range(h):
    l.append(list(input()))

flag = True
for i in range(h):
    for j in range(w):
        if l[i][j] == '#' and (i != h-1 or j != w-1):
            if i < h-1 and j < w-1:
                if l[i][j+1] == l[i+1][j]:
                    flag = False
            elif i == h-1:
                if l[i][j+1] != '#':
                    flag = False
            elif j == w-1:
                if l[i+1][j] != '#':
                    flag = False

for i in range(h):
    for j in range(w):
        if l[i][j] == '#' and i*j != 0:
            if i > 0 and j > 0:
                if l[i][j-1] == l[i-1][j]:
                    flag = False
            elif i == 0:
                if l[i][j-1] != '#':
                    flag = False
            elif j == 0:
                if l[i-1][j] != '#':
                    flag = False


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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
A = []
res_w = []
for i in range(h):
    line = [s for s in input()]
    c = []
    for j in range(len(line)):
        if line[j] == '#':
            c.append(j)
            if (len(c) > 1) and (c[-2] - c[-1] > 1):
                print('Impossible')
                exit()
            if j not in res_w:
                res_w.append(j)
            else:
                if max(res_w) > j:
                    
                    print('Impossible')
                    exit()
print('Possible')

Submission status: Accepted

Solution code:
from collections import deque


H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]
q = deque([(0, 0, [(0, 0)])])
visited = {(0, 0)}
while q:
    i, j, path = q.popleft()
    if (i, j) == (H - 1, W - 1):
        for pi, pj in path:
            field[pi][pj] = "."
        break
    for di, dj in ((1, 0), (0, 1)):
        ni, nj = i + di, j + dj
        if (
            0 <= ni < H
            and 0 <= nj < W
            and field[ni][nj] == "#"
            and (ni, nj) not in visited
        ):
            visited.add((ni, nj))
            q.append((ni, nj, path + [(ni, nj)]))

if any("#" in row for row in field):
    print("Impossible")
else:
    print("Possible")

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
tizu = [list(input()) for _ in range(h)]
pos = 1
for row in tizu:
    pos -= 1
    for i, index in enumerate(row):
        if i == pos:
            if index == "#":
                pos += 1
        else:
            if index == "#":
                print("Impossible")
                exit()
print("Possible")

Submission status: Accepted

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

flag = True

prev = 0
for a in A:
    if prev > 0:
        if '#' in a[:prev]:
            flag *= False
    prev = max([n for n, v in enumerate(a) if v == '#'])
if flag:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    M = [''] * H
    f = False
    for h in range(H):
        M[h] = list(input().strip())
        if '#' in M[h]:
            f = True
    s = deque([(0, 0)])
    if not f:
        print('Impossible')
        return
    if M[0][0] == '.':
        print('Impossible')
        return
    M[0][0] = '.'
    while s:
        (h, w) = s.popleft()
        if h + 1 < H:
            if M[h+1][w] == '#':
                M[h+1][w] = '.'
                s.append((h+1, w))
                continue
        if w + 1 < W:
            if M[h][w+1] == '#':
                M[h][w+1] = '.'
                s.append((h, w+1))

    for h in range(H):
        if '#' in M[h]:
            print('Impossible')
            return
    else:
        print('Possible')
        return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
a = [list(input()) for nesya in range(h)]
c = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      c += 1

if c == 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 i in range(h):
    cnt += a[i].count("#")
print("Possible" if cnt == h + w - 1 else "Impossible")

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a = [list(input()) for _ in range(h)]
a[0][0] = "."
q=[(0,0)]
dy=[0,1]
dx=[1,0]
while len(q)>0:
    y,x=q.pop(0)
    if y == h-1 and x == w-1:
        break
    for i in range(2):
        if not (0<=dy[i]+y<h and 0<=dx[i]+x<w):
            continue
        if a[dy[i]+y][dx[i]+x] != "#":
            continue
        else:
            a[dy[i]+y][dx[i]+x] = "."
            q.append((dy[i]+y,dx[i]+x))
            break
f = True
for i in range(h):
    for j in range(w):
        #print(a[i][j])
        if a[i][j] == "#":
            f = False
if f:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    q = collections.deque()

    q.append((0, 0))
    v = set()
    v.add((0, 0))

    while q:
        c = q.popleft()

        cnt = 0
        for nj, ni in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
            if 0 <= nj + c[0] < H and 0 <= ni + c[1] < W:
                if (nj + c[0], ni + c[1]) in v or A[nj + c[0]][ni + c[1]] == '.':
                    continue
                cnt += 1
                if nj < 0 or ni < 0:
                    print("Impossible")
                    return
                q.append((nj + c[0], ni + c[1]))
                v.add((nj + c[0], ni + c[1]))

        if cnt > 1:
            print("Impossible")
            return

    print("Possible")



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [input() for _i in range(h)]
p = 0
for i in range(h):
    x = [j for j in range(w) if a[i][j]=="#"]
    for j in range(len(x)-1):
        if x[j]+1==x[j+1]:
            continue
        else:
            import sys
            print("Impossible")
            sys.exit()
    if p==x[0]:
        p = x[-1]
    else:
        import sys
        print("Impossible")
        sys.exit()
print("Possible")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

board = []
board.append(['.'] * (w+2))
for i in range(h):
    board.append(list('.' + input() + '.'))
board.append(['.'] * (w+2))

for i in range(1,h+1):
    for j in range(1,w+1):
        left = board[i][j-1]
        upper = board[i-1][j]
        if left == '#' and upper == '#':
            print('Impossible')
            exit()
print('Possible')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
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 operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

h,w=mii()

mat=[list(ss()) for _ in range(h) ]
cnt=0
for i in range(h):
    for j in range(w):
        if mat[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())
G = [input() for i in range(H)]
done = [[False]*W for i in range(H)]
def dfs(h, w):
    done[h][w] = True
    if h == H-1 and w == W-1:
        return
    if w+1 < W and G[h][w+1] == "#":
        dfs(h, w+1)
    elif h+1 < H and G[h+1][w] == "#":
        dfs(h+1, w)
dfs(0, 0)
ans = True
for i in range(H):
    for j in range(W):
        if G[i][j] == "#":
            if not done[i][j]:
                ans = False
if ans:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))
#list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################


#5230



h,w = list(map(int, input().split()))
data=[]

for i in range(h):
    data.append(input())

now = [0,0]
goal = [h-1,w-1]

count = 0
for i in range(h):
    for j in range(w):
        if(data[i][j]=='#'): count+=1
#
if(count!=h+w-1):
    print("Impossible")
    exit()
            
            
while(True):
    if(now==goal):
        print("Possible")
        exit()
    a1='?'
    a2='?'
    if(now[1]!= w-1): a1 = data[now[0]][now[1]+1]
    if(now[0]!= h-1): a2 = data[now[0]+1][now[1]]
    if(a1=='#' and a2!='#'):
        now = AddV2(now,[0,1])
        continue
    if(a2=='#' and a1!='#'):
        now = AddV2(now,[1,0])
        continue
    if(a1!='#' and a2!='#'):
        print("Impossible")
        exit()
    if(a1=='#' and a2=='#'):
        print("Impossible")
        exit()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

s = [list(input()) for _ in range(H)]

sharp_count = 0

for h in range(H):
  sharp_count += s[h].count("#")

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

cnt = sum([row.count("#") for row in a])
print("Possible" if cnt == h + w - 1 else "Impossible")

Submission status: Accepted

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

queue = deque()
queue.append([0, 0])
visited = [[False] * w for _ in range(h)]
visited[0][0] = True

def judge():
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#" and not visited[i][j]:
                return False
    return True
def bfs(queue):
    while len(queue) > 0:
        n_y, n_x = queue.popleft()
        if 0 <= n_x < w - 1 and 0 <= n_y < h - 1:
            if a[n_y][n_x + 1] == "#" and a[n_y + 1][n_x] == "#":
                print("Impossible")
                exit()
        for i, j in [[0, 1], [1, 0]]:
            y, x = n_y + i, n_x + j
            if 0 <= x < w and 0 <= y < h:
                if a[y][x] == "#":
                    queue.append([y, x])
                    visited[y][x] = True
    print("Possible" if judge() else "Impossible")
bfs(queue)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
L = [input() for _ in range(h)]
r = 0
for i in range(h):
    for j in range(w):
        if L[i][j] == '#':
            if j < r:
                print('Impossible')
                exit()
            else:
                r = j
else:
    print('Possible')

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
a = [input() for _ in range(H)]
num = sum([row.count('#') for row in a])
if num==H+W-1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
import sys
h, w = map(int, input().split())
f = [list(map(str, input().rstrip())) for _ in range(h)]

for i in range(h - 1):
    for j in range(w - 1):
        if (f[i][j] == "#" and f[i][j + 1] == "#" and f[i + 1][j] == '#') or (f[i][j + 1] == "#" and f[i + 1][j] == "#" and f[i + 1][j + 1] == "#"):
            print("Impossible")
            sys.exit()

print("Possible")

Submission status: Accepted

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

cnt = 0
for x in range(h):
    for y in range(w):
        cnt += (a[x][y]=='#')
if(cnt > h+w-1):
    print('Impossible')
    exit()


x,y = 0,0
while(x+y<h+w-2):
    dx,dy=0,0

    if(x!=h-1):
        if(a[x+1][y]=='#'):
            dx = 1
    if(y!=w-1):
        if(a[x][y+1]=='#'):
            dy = 1
    if(dx+dy!=1):
        print('Impossible')
        exit()

    x += dx
    y += dy

print('Possible')