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 =list(map(int, input().split())) 
mat = []
for i in range(h):
    s = input()
    mat.append([s[x] for x in range(w)])

flag = True
for i in range(h-1):
    for j in range(w-1):
        if mat[i][j] == '#':
            if( (mat[i+1][j]=='#')& (mat[i][j+1]=='#') ):
                flag = False

for i in range(1,h):
    for j in range(1,w):
        if mat[i][j] == '#':
            if( (mat[i-1][j]=='.')& (mat[i][j-1]=='.') ):
                flag = False

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

Submission status: Accepted

Solution code:
h ,w = map(int, input().split())
board = [list(input()) for tate in range(h)]
now = 0
flag = False
for i in board:
    direction = i.count("#")
    if (flag != True):
        now = direction 
        flag = True
    else:
        if(direction == 1):
            continue
        else:
            now  = now + direction - 1

if (now == w):
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

count = 0

ans = True
for i in range(h):
    for j in range(w):
        if mat_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())
ban = [list(input()) for _ in range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if ban[i][j] == "#":
            cnt += 1
if cnt == H + W - 1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
"""
i-1行目の右端のマスとi行目の左端のマスが隣接しており、
それらの行においてはそれ以外のマスは隣接していないこと。

以上を満たした場合に'Possible'を出力すればよさそう。
"""
H, W = map(int, input().split())
table = [input() for _ in range(H)]
pre_row = [i for i, x in enumerate(table[0]) if x == "#"]
for i in range(1, H):
    next_row = [j for j, x in enumerate(table[i]) if x == "#"]
    if len(set(pre_row) & set(next_row)) == 1 and pre_row[-1] == next_row[0]:
        pre_row = next_row
    else:
        print('Impossible')
        exit()
print('Possible')

Submission status: Accepted

Solution code:
"""
i-1行目の右端のマスとi行目の左端のマスが隣接しており、
それらの行においてはそれ以外のマスは隣接していないこと。

以上を満たした場合に'Possible'を出力すればよさそう。
"""
H, W = map(int, input().split())
table = [input() for _ in range(H)]
for i in range(1, H):
    li_pre = [i for i, x in enumerate(table[i - 1]) if x == "#"]
    li_now = [i for i, x in enumerate(table[i]) if x == "#"]
    if len(set(li_pre) & set(li_now)) == 1 and li_pre[-1] == li_now[0]:
        continue
    else:
        print('Impossible')
        exit()
print('Possible')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque
    from itertools import combinations

    h, w = map(int, readline().split())
    a = list()
    cnt = 0
    for i in range(h):
        s = input()
        cnt += s.count("#")
        a.append(s)

    if cnt != (h + w - 1):
        return print("Impossible")

    for per in combinations(range(h + w - 2), h - 1):
        cr, cc = 0, 0
        for i in range(h + w - 2):
            if i in per:
                cr += 1
            else:
                cc += 1
            if a[cr][cc] == ".":
                break
            if (cr, cc) == (h - 1, w - 1):
                return print("Possible")
    return print("Impossible")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
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 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


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
a = [sr() for i in range(h)]
count = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            count+=1
def dfs():
    q = deque([[0,0]])
    ret = 1
    while q:
        x, y= q.popleft()
        for dx,dy in [[1,0], [0,1]]:
            nx = x+dx
            ny = y+dy
            if nx < w and ny < h and a[ny][nx] == '#':
                q.append([nx,ny])
                ret += 1
                if nx == w-1 and ny == h-1:
                    return ret
                break
    return ret
if dfs()==count:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = []
for i in range(H):
  a = [i for i in str(input())]
  A.append(a)
  
def meiro(A, h, w):
  global H
  global W
  if ('#' in A[h][:w]) or (A[h][w] != '#'):
    return False
  while A[h][w] == '#':
    w += 1
    if w == W:
      break
  if h==H-1 and w==W:
    return True
  elif h == H-1:
    return False
  elif A[h][w-1:].count('#')==1:
    return meiro(A, h+1, w-1)
  
if meiro(A, 0, 0):
  print('Possible')
else:
  print('Impossible')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')


def solve():
    n, w = [int(x) for x in input().split()]
    j = 0
    ok = 1
    for i in range(n):
        r = [x for x in input()]
        while r[j] == '#' and j+1 < w and r[j+1] == '#':
            r[j] = '.'
            j += 1
        if r[j] == '.' or r.count('#') != 1:
            ok = 0


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

    




        
    

    
    

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

2 2 2 2 2

"""

Submission status: Accepted

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

    cnt = 0
    for a in A:
        cnt += a.count("#")

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import numpy as np
h, w = map(int, input().split())
A = [input() for _ in range(h)]
B = np.empty((h+1, w+1), dtype=str)
for i in range(h):
  for j in range(w):
    B[i, j] = A[i][j]

x = y = 0
B[y, x] = '.'
while x != w-1 or y != h-1:
  if B[y, x+1] == B[y+1, x] == '#':
    print('Impossible')
    exit()
  elif B[y, x+1] == '#':
    x += 1
  else:
    y += 1
  B[y, x] = '.'

if np.any(B == '#'):
  print('Impossible')
else:
  print('Possible')

Submission status: Accepted

Solution code:
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
from decimal import *

import numpy as np

import math

import collections
import itertools
import bisect

def check(maiz):
    for i in range(h):
        for j in range(w):
            count = 0
            if i > 0 and maiz[i-1][j] =="#":
                count+=1
            if i <h-1 and maiz[i+1][j] =="#":
                count+=1
            if j > 0 and maiz[i][j-1] =="#":
                count+=1
            if j <w-1 and maiz[i][j+1] =="#":
                count+=1
            if count > 2 and  maiz[i][j] == "#":
                return False
    return True

if __name__ == '__main__':
    h, w = map(int, input().split())
    count =0
    flag =False
    maiz=[]
    for i in range(h):
        s = input()
        count+=s.count("#")
        maiz.append(list(s))

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

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
import itertools

# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    h, w = input_list()
    count = 0
    for _ in range(h):
        s = list(input())
        count += s.count('#')
    if h+w-1 == count:
        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:
H,W = map(int,input().split())

res = 0

for i in range(H):
    res += input().count('#')

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

Submission status: Accepted

Solution code:
def dfs(A, chk):
    if a[A[-1][0]][A[-1][1]] == ".":
        return
    elif A[-1] == [h, w]:
        if len(A) == cnt and chk == 0:
            print("Possible")
        else:
            print("Impossible")
        exit()

    for v in [[1, 0], [0, 1], [0, -1], [-1, 0]]:
        tmp = [A[-1][0] + v[0], A[-1][1] + v[1]]
        if tmp not in A:
            A.append(tmp)
            if v in [[0, -1], [-1, 0]]:
                dfs(A, chk + 1)
            else:
                dfs(A, chk)                
            A.pop()

h, w = map(int, input().split())
a = [["."]*w]
a.extend([list("." + input() + ".") for x in range(h)])
a.append(["."]*w)
cnt = 0
for i in range(1,h+1):
    cnt += a[i].count("#")
dfs([[1, 1]], 0)

Submission status: Accepted

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

import sys
from collections import deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


# adjacent_2
def adjacent_2(h, w, H, W):
    ret = []
    for (dh, dw) in [(0, 1), (1, 0)]:
        h_ = h + dh
        w_ = w + dw
        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


def adjacent_2_(h, w, H, W):
    ret = []
    for (dh, dw) in [(0, -1), (-1, 0)]:
        h_ = h + dh
        w_ = w + dw
        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


H, W = map(int, readline().split())
M = [list(readline().decode().rstrip()) for _ in range(H)]

que = deque([(0, 0)])
while len(que) != 0:
    acc = que.popleft()

    ret = adjacent_2(*acc, H, W)
    cnt = adjacent_2_(*acc, H, W)
    ret = [pos for pos in ret if M[pos[0]][pos[1]] == '#']
    cnt = [pos for pos in cnt if M[pos[0]][pos[1]] == '#']

    if (len(cnt) > 1):
        print("Impossible")
        sys.exit()
    if acc == (H - 1, W - 1):
        break

    if (len(ret) != 1) or (len(cnt) > 1):
        print("Impossible")
        sys.exit()
    que.append(*ret)

print("Possible")

Submission status: Accepted

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

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:
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 k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
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)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0
inf = float("inf")

H,W = I()
boa = []
for i in range(H):
    x = X()
    count += x.count("#")

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[]
for i in range(h):
  at=list(str(input()))
  a.append(at)
i=0
j=0
t=0
while True:
  if j!=w-1:
    if a[i][j+1]=="#":
      for k in range(i+1,h):
        if a[k][j]=="#":
          t=1
          break
      else:
        j=j+1
  if i!=h-1:
    if a[i+1][j]=="#":
      for k in range(j+1,w):
        if a[i][k]=="#":
          t=1
          break
      else:
        i=i+1
  if t==1:
    print("Impossible")
    break
  elif i==h-1 and j==w-1:
    print("Possible")
    break

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = map(int, input().split())
a = [None]*h
for i in range(h):
    a[i] = input()
cx = 0
cy = 0
d = set()
while (cx,cy)!=(h-1, w-1):
    val = 0
#     print(cx,cy)
    for dx, dy in [(1,0), (0,1)]:
        ccx = cx+dx
        ccy = cy+dy
        if ccx>=h or ccy>=w or a[ccx][ccy]==".":
            continue
        nx, ny = ccx, ccy
        val += 1
    if val>=2 or val==0:
        ans = "Impossible"
        break
    cx, cy = nx, ny
else:
    vv = sum(sum(item=="#" for item in items) for items in a)
    if vv==h+w-1:
        ans = "Possible"
    else:
        ans = "Impossible"
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(h):
    area[i] = input()
num = 0

for i in range(h):
    for j in range(w):
        if area[i][j] == '#' and j < num:
            print('Impossible')
            exit()
        elif area[i][j] == '#':
            num = j

print('Possible')

Submission status: Accepted

Solution code:
h,w=map(int, input().split())
s=[list(input()) for _ in range(h)]
c=0
for i in range(h):
  for j in range(w):
    if s[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())
fld = ''.join([input()for _ in range(h)])
if fld.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)]
b = 0
check = True
for i in range(h):
  for j in range(w):
    if b == j:
      if a[i][j] == ".":
        check = False
    elif b+1 == j:
      if a[i][j] == "#":
        b = j
    else:
      if a[i][j] == "#":
        check = False
  if not check:
    break
if check:
  print("Possible")
else:
  print("Impossible")

Submission status: Accepted

Solution code:
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
a = [input()+'.' for i in range(h)]
a.append("."*(w+1))
i = j = 0
b = [['.']*(w+1) for i in range(h+1)]

if a[0][0] == '.':
        print("Impossible")
        exit()
else:
        while i < h or j < w:
                b[i][j] = '#'
 
                if a[i][j] == a[i+1][j] == a[i][j+1] == a[i+1][j+1] == '#':
                        print("Impossible")
                        exit()

                if i == h-1 and j == w-1:
                        break
                elif a[i+1][j] == '#':
                        i += 1
                elif a[i][j+1] == '#':
                        j += 1
                else: 
                        print("Impossible")
                        exit()

        for i in range(h):
                for j in range(w):
                        if a[i][j] != b[i][j]:
                                print("Impossible")
                                exit()
        print("Possible")

Submission status: Accepted

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

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

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

if __name__ == "__main__":
    main2()

Submission status: Accepted

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

    for i in range(H):
        board.append(list(input()))

    stat = [[False for i in range(W)] for j in range(H)]

    go = True
    i = j = 0
    stat[i][j] = True
    while go:

        if (i < H) and (j + 1 < W) and board[i][j + 1] == "#":
            j = j + 1
            stat[i][j] = True
        elif (i + 1 < H) and (j < W) and board[i + 1][j] == "#":
            i = i + 1
            stat[i][j] = True
        else:
            break

    ans = True
    for i in range(H):
        for j in range(W):
            if board[i][j] == "#" and stat[i][j] == False:
                ans = False

    if ans:
        print("Possible")
    else:
        print("Impossible")
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W=map(int, input().split())
cnt=0
for _ in range(H):
  a=list(input())
  cnt+=a.count("#")
if cnt==(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("#")

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[]
flg=True
for i in range(h):
    a.append(list(input()))
tmp=0
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            if j<tmp:
                flg=False
            else: tmp=j
if flg:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
count = 0
for _ in range(H):
    a = input()
    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 = [input() + '.' for _ in range(H)]
a.append('.' * W)

seen = [[False for i in range(W)] for j in range(H)]
h, w = 0, 0
while h < H and w < W:
    seen[h][w] = True

    if a[h][w + 1] == a[h + 1][w]:
        print('Impossible')
        exit()

    if a[h][w + 1] == '#':
        w += 1
    else:
        h += 1

    if a[h - 1][w] == '#' and a[h][w - 1] == '#':
        print('Impossible')
        exit()

    if h == H - 1 and w == W - 1:
        print('Possible')
        exit()
print('Impossible')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

A=["."*(W+2)]
T=0
for _ in range(H):
    G=input()
    A.append("."+G+".")
    T+=G.count("#")
    
A.append("."*(W+2))

x,y=1,1
U=1
while x<W or y<H:
    p=(A[y+1][x]=="#")
    q=(A[y][x+1]=="#")

    if p^q:
        if p:
            y=y+1
        else:
            x=x+1
        U+=1
    else:
        print("Impossible")
        sys.exit()

if T==U:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

Submission status: Accepted

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

A = []
for _ in range(H):
    A.append(list(input()))

cnt = 0
for aa in A:
    for aaa in aa:
        if aaa == '#':
            cnt += 1

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

Submission status: Accepted

Solution code:
x,y = list(map(int, input().split()))
l = []
for i in range (x):
   l.append(list(input()))
val = 0
for j in range (x):
   val += l[j].count('#')
print('Possible' if x + y - 1 == val else 'Impossible')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def dfs(grid, start, wall, h, w):
    stack = []
    push, pop = stack.append, stack.pop
    push(start)
    grid[start[0]][start[1]] = wall
    dxy = [(0,1), (1,0)]

    while stack:
        h, w = pop()
        cnt = 0
        for dx,dy in dxy:
            x, y = w+dx, h+dy
            if grid[y][x] == wall:
                continue
            push((y,x))
            grid[y][x] = wall
            cnt += 1
        if cnt > 1:
            return False
    for i in range(1, h+1):
        for j in range(1, w+1):
            if grid[i][j] != wall:
                return False
    return True


def resolve():
    h, w = map(int, input().split())
    grid = {}
    wall = '.'
    edges = [wall] * (w+2)
    grid = [edges]
    for i in range(h):
        s = input()
        grid.append([wall] + list(s) + [wall])
    grid.append(edges)
    print("Possible" if dfs(grid, (1, 1), wall, h, w) else "Impossible")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    H, W = map(int, input().split())
    A = [list(input().rstrip()) for i 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')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())

Map = []
Cnt = 0
for i in range(h):
    tmp = list(input())
    Cnt += tmp.count('#')
    Map.append(tmp)
q = deque()
q.append((0,0,0,True))
while q:
    y,x,cnt,flag= q.pop()
    if flag ==False:
        continue
    if y<0 or y>=h or x<0 or x>=w:
        continue
    if Map[y][x]!='#':
        continue
    cnt += 1
    if cnt==Cnt and y==h-1 and x == w-1:
        if flag:
            print('Possible')
        exit()
    q.append((y+1,x,cnt,flag))
    q.append((y,x+1,cnt,flag))
    flag = False
    q.append((y-1,x,cnt,flag))
    q.append((y,x-1,cnt,flag))

print('Impossible')

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np
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(map(int,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)
INF = 10**9
mod = 10**9+7

H,W = I()
maze = [list(s()) for _ in range(H)]
visited = [[0]*W for _ in range(H)]
def dfs(x,y):
    if x < 0 or y < 0 or x >= H or y >= W:
        return
    if maze[x][y] == '.':
        return
    visited[x][y] = 1
    dfs(x+1,y)
    dfs(x,y+1)
dfs(0,0)
if visited[H-1][W-1] == 1:
    cnt = 0
    for i in range(H):
        cnt += maze[i].count('#')
    if cnt == H+W-1:
        print('Possible')
    else:
        print('Impossible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[]
for _ in range(H):
    s=input()
    s=[a for a in s]
    S.append(s)
visited=[[-1 for _ in range(W)] for _ in range(H)]
visited[0][0]=1
stack=[[0,0]]
answer=0
S[0][0]='.'
while len(stack)>0:
    h,w=stack.pop()
    number=0
    for x,y in ([0,1],[0,-1],[1,0],[-1,0]):
        new_w=w+x
        new_h=h+y
        if new_w<0 or new_w>=W or new_h<0 or new_h>=H:
            continue
        elif visited[new_h][new_w]==-1 and S[new_h][new_w]=='#':
            number+=1
            visited[new_h][new_w]=1
            S[new_h][new_w]='.'
            stack.append([new_h,new_w])
            if x==-1 and y==0:
                answer=1
                break
            elif x==0 and y==-1:
                answer=1
                break
        if number>1:
            answer=1
            break
if answer==0:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["#","#"]:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
        for k in range(1,w):
            if a[i][k] == "#":
                if a[i+1][k-2:k] == ["#","#"]:
                    print("Impossible")
                    exit()
    if a[h-2][-1] == "#":
        if a[h-1][-2] == "#":
            print("Impossible")
            exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
def BFS(x,y):
  flag=False
  qu=deque([])
  qu.append([x,y])
  
  while len(qu)!=0:
    d=qu.popleft()
    now_x,now_y=d[0],d[1]
    #print(now_x,now_y)
    #print(now_x==w-1 and now_y==h-1)
    a[now_y][now_x]="."
    if now_x==w-1 and now_y==h-1:
      flag=True
      return flag
      
    if now_y<h-1 and a[now_y+1][now_x]=="#":
      qu.append([now_x,now_y+1])
    if now_x<w-1 and a[now_y][now_x+1]=="#":
      qu.append([now_x+1,now_y])
    if now_y<h-1 and a[now_y+1][now_x]=="#" and now_x<w-1 and a[now_y][now_x+1]=="#":
      return flag
  return flag
flag=BFS(0,0)
for i in a:
  for j in i:
    if j=="#":
      flag=False
if flag:
  print("Possible")
else:
  print("Impossible")