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)]
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:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

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

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

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

Submission status: Accepted

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

count = 0
for h in range(H):
    for w in range(W):
        if map[h][w] == "#":
            count += 1
if count == H + W - 1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

Submission status: Accepted

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

mvs = [(0,1),(1,0)]

from collections import deque
q = deque()
q.append((0,0))

cnt = 0
for f in fields:
    cnt += f.count("#")
if cnt != H + W - 1: 
    print("Impossible")
    exit()
# ゴールまで連結しているか
while len(q) > 0:
    h,w = q.popleft()
    if h == H-1 and w == W-1:
        print("Possible")
        exit()
    for dh, dw in mvs:
        h_nx = h + dh
        w_nx = w + dw
        if h_nx >= H or w_nx >= W:continue
        if fields[h_nx][w_nx] == ".":continue
        q.append((h_nx,w_nx))
print("Impossible")

Submission status: Accepted

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

def dfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[float("inf")] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(1, 0), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "#" and dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist[gy][gx]

count = dfs(0, 0, H-1, W-1)+1
count2 = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            count2 += 1
if count == count2:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

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

Submission status: Accepted

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


def judge(x, y, l: set):
    global a, f
    l.add("{},{}".format(x, y))
    if (x != h - 1):
        if (a[x + 1][y] == "#") and not ("{},{}".format(x+1, y) in l):
            judge(x + 1, y, l.copy())
    if (y != w - 1):
        if (a[x][y + 1] == "#") and not ("{},{}".format(x, y+1) in l):
            judge(x, y + 1, l.copy())

    if (x == h - 1) and (y == w - 1):
        if (l.__len__() == c):
            f = True


judge(0, 0, set())

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

Submission status: Accepted

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

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

Submission status: Accepted

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

h, w = map(int, input().split())
a = [input().rstrip('\n') 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')

Submission status: Accepted

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

y, x = 0, 0
c = 0
while True:
    c += 1
    if y == H - 1 and x == W - 1:
        break
    if y < H - 1 and A[y + 1][x] == '#':
        y += 1
    elif x < W - 1 and A[y][x + 1] == '#':
        x += 1
    else:
        break

if c == sum(a.count('#') for a in A):
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

h, w = MAP()
a = [[1 if i == '#' else 0 for i in STR()] for _ in range(h)]
s = 0
for i in range(h):
    s += sum(a[i])
if s != h + w - 1:
    print('Impossible')
    exit()
y = 0
x = 0
dx = [1, 0]
dy = [0, 1]
while y < h - 1 or x < w - 1:
    flag = [False, False]
    for i in range(2):
        if x + dx[i] < w and y + dy[i] < h and a[y + dy[i]][x + dx[i]] == 1:
            flag[i] = True
    if (flag[0] and flag[1]) or (not flag[0] and not flag[1]):
        print('Impossible')
        exit()
    if flag[0]:
        x += 1
    else:
        y += 1
print('Possible')

Submission status: Accepted

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

h, w = MAP()
a = [input() for _ in range(h)]
y = 0
x = 0
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
while y < h and x < w:
    flag = [False for _ in range(4)]
    for i in range(4):
        if 0 <= y + dy[i] < h and 0 <= x + dx[i] < w and a[y + dy[i]][x + dx[i]] == '#':
            flag[i] = True
    if x == y == 0:
        flag[2] = True
    if x == w - 1 and y == h - 1:
        flag[0] = True
    if flag[0]:
        y += 1
    else:
        x += 1
    if not len(set(flag[0:2])) == len(set(flag[2:4])) == 2:
        print('Impossible')
        exit()
print('Possible')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h, w = map(int,input().split())
a = [list(input()) for _ in range(h)]

#print(a)
i = 0
j = 0
ans = "Possible"
while i < h - 1 or j < w - 1:
    flag1 = [False for _ in range(2)]
    flag2 = [False for _ in range(2)]
    #print(i, j+1)
    #print(a)
    #print(a[i][j+1])
    if i == 0 and j == 0:
        flag2[0] = True
    if i + 1 < h and a[i + 1][j] == '#':
        flag1[0] = True
    if j + 1 < w and a[i][j + 1] == '#':
        flag1[1] = True
    if i - 1 >= 0 and a[i - 1][j] == '#':
        flag2[0] = True
    if j - 1 >= 0 and a[i][j - 1] == '#':
        flag2[1] = True
    #print(flag1, flag2)
    if len(set(flag1)) == 2 and len(set(flag2)) == 2:
        if flag1[0]:
            i += 1
        if flag1[1]:
            j += 1
    else :
        ans = "Impossible"
        break
if a[h - 2][w - 1] == '#' and a[h - 1][w - 2] == '#':
    ans = "Impossible"
print(ans)

Submission status: Accepted

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

h, w = MAP()
a = [[1 if i == '#' else 0 for i in STR()] for _ in range(h)]
s = 0
for i in range(h):
    s += sum(a[i])
if s != h + w - 1:
    print('Impossible')
    exit()
y = 0
x = 0
d = [[1, 0], [0, 1]]
while y < h - 1 or x < w - 1:
    flag = [False, False]
    for i in range(2):
        if x + d[i][0] < w and y + d[i][1] < h and a[y + d[i][1]][x + d[i][0]] == 1:
            flag[i] = True
    if (flag[0] and flag[1]) or (not flag[0] and not flag[1]):
        print('Impossible')
        exit()
    if flag[0]:
        x += 1
    else:
        y += 1
print('Possible')

Submission status: Accepted

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

h, w = MAP()
a = [[1 if i == '#' else 0 for i in STR()] for _ in range(h)]
s = 0
for i in range(h):
    s += sum(a[i])
if s != h + w - 1:
    print('Impossible')
    exit()
y = 0
x = 0
while y < h - 1 or x < w - 1:
    flag1 = False
    flag2 = False
    if y + 1 < h and a[y + 1][x] == 1:
        flag1 = True
    if x + 1 < w and a[y][x + 1] == 1:
        flag2 = True
    if (flag1 and flag2) or (not flag1 and not flag2):
        print('Impossible')
        exit()
    if flag1:
        y += 1
    if flag2:
        x += 1
print('Possible')

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque
def bfs(sy,sx,gy,gx):
    q=deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x=q.popleft()
        if [y,x]==[gy,gx]:
            return visited[y][x]
        for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx=y+i,x+j
            if ny<0 or ny>h-1 or nx<0 or nx>w-1:continue
            if path[ny][nx]=="#" and visited[ny][nx]==-1:
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])
h,w=map(int,input().split())
path=[input() for i in range(h)]
visited=[[-1]*w for _ in range(h)]
c=0
for p in path:
    for pp in p:
        if pp=='#':
            c+=1

sy,sx=0,0
gy,gx=h-1,w-1
bfs(sy,sx,gy,gx)
if visited[gy][gx]==h+w-2 and c==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)]
x=0
y=0
flag=1
cnt=0
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            cnt=cnt+1

if cnt==W+H-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)]
max_h=0
max_w=0
flag=True
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            if i>max_h:
                max_h=i
            elif i<max_h:
                flag=False
            if j>max_w:
                max_w=j
            elif j<max_w:
                flag=False
print("Possible" if flag==True else 'Impossible')

Submission status: Accepted

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

total = sum([1 for a in A for s in a  if s=='#'])   
print('Possible' if total == W+H-1 else 'Impossible')

Submission status: Accepted

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

right = 0
for A in AA:
    left = A.index('#')
    if left < right:
        print('Impossible')
        break
    right = W - 1 - A[::-1].index('#')
else:
    print('Possible')

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

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

h,w = na()
b = 0
for i in range(h):
    a = list(ns())
    b += a.count('#')

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

Submission status: Accepted

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

check = [['.'] * w for _ in range(h)]
check[0][0] = '#'

def dfs(x,y):
  global flag,check
  if x == h-1 and y == w-1:
    flag = True
    return
  if x != h-1 and maze[x+1][y] == '#':
    check[x+1][y] = '#'
    dfs(x+1,y)
    return
  if y != w-1 and maze[x][y+1] == '#':
    check[x][y+1]= '#'
    dfs(x,y+1)
    return
  return
dfs(0,0)
if maze == check:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
# input
H, W = map(int, input().split())
board = [['.']*W for i in range(H)]
v_board = [[True]*W for i in range(H)]
sign_count = 0
for i in range(H):
    s = input()
    for j in range(W):
        if s[j]=='#':
            sign_count += 1
        board[i][j] = s[j]

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

Submission status: Accepted

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

c = 0
for i in L:
    c += i.count('#')
    
if c == H + W - 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

L = [list(input()) for i in range(H)]

cnt = 0
for i in L:
    c = i.count("#")
    cnt += c

if 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 = list(input())
    A.append(a)

r = 0
for i in range(H):
    for j in range(r):
        if A[i][j] == '#':
            print('Impossible')
            exit(0)

    flag = False
    for j in range(r+1, W):
        if not(flag):
            if A[i][j] == '#':
                r += 1
            else:
                flag = True
                r = j-1
        else:
            if A[i][j] == '#':
                print('Impossible')
                exit(0)

print('Possible')

Submission status: Accepted

Solution code:
import sys

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
    if count + 1 == H + W: print("Possible")
    else: print("Impossible")


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

def func(y, x, cnt):
    if y == h - 1 and x == w - 1:
        cnt += 1
        return y, x, cnt
    if y < h - 1 and a[y + 1][x] == 1:
        cnt += 1
        return func(y + 1, x, cnt)
    if x < w - 1 and a[y][x + 1] == 1:
        cnt += 1
        return func(y, x + 1, cnt)
    if y < h - 1 and a[y + 1][x] == 0:
        return y, x, cnt
    if x < w - 1 and a[y][x + 1] == 0:
        return y, x, cnt

h, w = MAP()
a = [[1 if i == '#' else 0 for i in STR()] for _ in range(h)]
s = 0
for i in range(h):
    s += sum(a[i])
y, x, cnt = func(0, 0, 0)
if y == h - 1 and x == w - 1 and cnt == s:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

q_ = 0
for i in range(h):
    flag = 0
    for j in range(w):
        if A[i][j] == '#' and flag == 0:
            p = j
            q = j
            flag = 1
        elif A[i][j] == '#' and flag == 1:
            q = j
        else:
            pass
    if p < q_:
        print('Impossible')
        exit()
    else:
        q_ = q
else:
    print('Possible')

Submission status: Accepted

Solution code:
from collections import deque

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

que = deque([(0, 0)])
while que:
    h, w = que.popleft()

    A[h][w] = '?'

    if h == H - 1 and w == W - 1:
        break

    if h + 1 < H and A[h + 1][w] == '#':
        que.append((h + 1, w))
        continue

    if w + 1 < W and A[h][w + 1] == '#':
        que.append((h, w + 1))
        continue

cnt = sum([a.count('#') for a in A])
print('Possible' if cnt == 0 else 'Impossible')

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    height, width = map(int, input().split())
    grid = [list(input()) for _ in range(height)]
    count = 0
    for g in grid:
        count += g.count("#")
    print("Possible" if count == height + width - 1 else "Impossible")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

def pad(mxy, wall="#"):
	w = len(mxy[0])
	gp = wall*(w+2)
	re = [gp,]
	re_app = re.append
	for vx in mxy:
		re_app(wall+vx+wall)
	re_app(gp)
	return re

def main():
	H,W = linput()
	mM = [input().rstrip() for _ in [0,]*H]
	mM = pad(mM,".")
	mV = [[0,]*(W+2) for _ in [0,]*(H+2)]
	
	vD = [(0,1),(1,0)]
	
	res = False
	cnt = 0
	
	vQ = []
	vQ_app, vQ_pop = vQ.append, vQ.pop
	if mM[1][1]=="#":
		vQ_app((1,1))
	while vQ:
		x,y = vQ_pop()
		#print(x,y)
		if (x,y)==(W,H):
			res = True; mV[H][W] = 1; break
		
		
		t = 0
		for dx,dy in vD:
			nx,ny = x+dx, y+dy
			if mM[ny][nx]=="#" and \
			not mV[ny][nx]:
				t += 1
				vQ_app((nx,ny))
		
		if t>0:
			mV[y][x] = 1

		cnt += 1
		#print(res,cnt,X,Y,H)
		if cnt>999999: break
	
	if res:
		for vm,vv in zip(mM,mV):
			#print(vm,vv)#
			if not all(v for m,v in 
			  zip(vm,vv) if m=="#"):
				res = False; break
	
	print(("Impossible","Possible")[res])
	#print(res)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

H, W = map(int, input().split())
G = [[] for i in range(H*W)]
S = [list(input()) for i in range(H)]
rs = 0
for i in range(H*W) :
    h = i//W
    w = i%W
    if S[h][w] == "#" :
        rs += 1
        if h < H-1 and S[h+1][w] == "#" :
            j = (h+1)*W + w
            G[i].append(j)
        if w < W-1 and S[h][w+1] == "#" :
            j = h*W + w+1
            G[i].append(j)

def bfs(s, g) :
    dist = [-1 for _ in range(H*W)]
    q = deque([s])
    dist[s] = 0
    while q :
        now = q.popleft()
        for next in G[now] :
            if dist[next] != -1 :
                continue
            else :
                dist[next] = dist[now] + 1
                q.append(next)
    return dist[g]

if bfs(0,H*W-1) == rs-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 i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            cnt += 1
if cnt == h + w - 1:
    ans = 'Possible'
else:
    ans = 'Impossible'
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import copy
# input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    H,W = MAP()
    S = [input() for _ in range(H)]
    answerLabel = [[S[i][j]=="#" for j in range(W)] for i in range(H)]

    def dfs(cur,isVisited):
        i,j = cur
        isVisited[i][j] = True
        v = copy.deepcopy(isVisited)
        v2 = copy.deepcopy(isVisited)
        
        if i == H-1 and j == W-1:
            if isVisited == answerLabel:
                print("Possible")
                sys.exit()
            return
        if i+1<H:
            dfs((i+1,j),v)
        
        if j+1<W:
            dfs((i,j+1),v2)
    
    dfs((0,0),[[False]*W for _ in range(H)])

    print("Impossible")
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
pos = [0, 0]
S = [input() for i in range(H)]
p = 1
def whiteout(Map, h, w):
  y = 0
  for i in range(h):
    for j in range(w):
      if Map[i][j] == '#':
        y += 1
  return y == 0

while pos != [H-1, W-1]:
  cnt = 0
  x, y = pos[0], pos[1]
  S[x] = S[x][:y] + '.' + S[x][y+1:]
  if x < H-1:
    if S[x+1][y] == '#':
      cnt += 1
      pos = [x+1, y]
  if y < W-1:
    if S[x][y+1] == '#':
      cnt += 1
      pos = [x, y+1]
  if cnt != 1:
    p = 0
    break
S[H-1] = S[H-1][:W-1] + '.'
if p == 1 and whiteout(S, H, W):
  print("Possible")
else:
  print("Impossible")

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
A = []
for i in range(h):
    A.append(list(input()))
c = 0
for i in range(h):
    for j in range(w):
        if A[i][j] == "#":
            c += 1
if c > h+w-1:
    print("Impossible")
else:
    i = 0
    j = 0
    f = False
    for _ in range(h+w-1):
        if i + 1 < h  and A[i+1][j] == "#":
            i += 1
        elif j + 1 < w and A[i][j+1] == "#":
            j += 1
        if i == h-1 and j == w-1 and A[i][j] == "#":
            f = True
    print("Possible")

Submission status: Accepted

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


i = 0
j = 0

while True:
    if a[i+1][j] == "#":
        a[i][j] = "."
        i += 1
    elif a[i][j+1] == "#":
        a[i][j] = "."
        j += 1
    else:
        break
a[i][j] = "."
bl = True
for row in a:
    if "#" in row:
        bl = False

ans = "Possible" if bl else "Impossible"
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split(' '))
A = [input() for _ in range(H)]

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

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

Submission status: Accepted

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

for i in range(H):
    s = input()
    A.append(list(s))

# for i in range(H):
#     print(A[i])

di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

ans = True
for i in range(H):
    for j in range(W):
        # if (i == 0 and j == 0) or (i == H-1 and j == W-1):
        #     continue
        if A[i][j] == '#':
            ul = 0  # 上 or 左
            rd = 0  # 右 or 下
            for k in range(4):
                ni = i + di[k]
                nj = j + dj[k]
                if 0 <= ni < H and 0 <= nj < W:
                    if A[ni][nj] == '#':
                        if k == 0 or k == 1:
                            ul += 1
                        else:
                            rd += 1
            # print(i, j, ':', ul, rd)
            if i == 0 and j == 0:
                if not (ul == 0 and rd == 1):
                    ans = False
            elif i == H-1 and j == W-1:
                if not (ul == 1 and rd == 0):
                    ans = False
            else:
                if not (ul == 1 and rd == 1):
                    ans = False

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

Submission status: Accepted

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

ans = "Impossible"

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

if cnt == H + W - 1:
    ans = "Possible"

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

fie = [list(input())for i in range(h)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]


cant = 0
que = Queue()
que.put([0,0])

while not que.empty():
        px, py = que.get()
        fie[px][py] = "."
        under = right = 0
        for i in range(4):
                if 0<=px+dx[i]<h and 0<=py+dy[i]<w and fie[px+dx[i]][py+dy[i]]=="#":
                        if i==2 or i==3: cant = 1
                        else:
                                if i==0: under = 1
                                elif i==1: right = 1
                                que.put([px+dx[i],py+dy[i]])
        if under and right: cant = 1

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#n = int(input())
#n,k = map(int,input().split())
#x = list(map(int,input().split()))


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

h = 0
w = 0
A[0][0]="."

while not(h==H-1 and w==W-1):
    # print(h,w)
    if h<H-1 and w<W-1 and A[h+1][w]=="#" and A[h][w+1]=="#":
        print("Impossible")
        break

    elif h<H-1 and A[h+1][w]=="#":
        h += 1
        A[h][w] = "."

    elif w<W-1 and A[h][w+1]=="#":
        w += 1
        A[h][w] = "."
    else:
        print("Impossible")
        break

else:
    flg = 0
    for h in range(H):
        for w in range(W):
            if A[h][w]=="#":
                flg = 1
                break
    else:
        if flg:
            print("Impossible")
        else:    
            print("Possible")