Problem:


Score : 200 points

Problem Statement

   #nck {
      width: 30px;
      height: auto;
   }

We have a grid of H rows and W columns. Initially, there is a stone in the top left cell. Shik is trying to move the stone to the bottom right cell. In each step, he can move the stone one cell to its left, up, right, or down (if such cell exists). It is possible that the stone visits a cell multiple times (including the bottom right and the top left cell).

You are given a matrix of characters a_{ij} (1 \leq i \leq H, 1 \leq j \leq W). After Shik completes all moving actions, a_{ij} is # if the stone had ever located at the i-th row and the j-th column during the process of moving. Otherwise, a_{ij} is .. Please determine whether it is possible that Shik only uses right and down moves in all steps.

Constraints

2 \leq H, W \leq 8

a_{i,j} is either # or ..

There exists a valid sequence of moves for Shik to generate the map a.

Input

The input is given from Standard Input in the following format:

H W
a_{11}a_{12}...a_{1W}
:
a_{H1}a_{H2}...a_{HW}

Output

If it is possible that Shik only uses right and down moves, print Possible. Otherwise, print Impossible.

Sample Input 1

4 5
##...
.##..
..##.
...##

Sample Output 1

Possible

The matrix can be generated by a 7-move sequence: right, down, right, down, right, down, and right.

Sample Input 2

5 3
###
..#
###
#..
###

Sample Output 2

Impossible

Sample Input 3

4 5
##...
.###.
.###.
...##

Sample Output 3

Impossible



Sample input:
4 5
##...
.##..
..##.
...##


Sample output:
Possible

Submission status: Accepted

Solution code:
from collections import deque


def bfs(start):
    Q = deque()
    Q.append(start)
    dist[start[1]][start[0]] = 0

    while Q:
        x, y = Q.popleft()

        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]

            if not(0 <= nx < W and 0 <= ny < H):
                continue
            if G[ny][nx] == '.':
                continue
            if dist[ny][nx] != -1:
                continue

            Q.append((nx, ny))
            dist[ny][nx] = dist[y][x] + 1


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

n = 0
for i in range(H):
    G[i] = list(input())
    n += G[i].count('#')

dist = [[-1 for _ in range(W)] for _ in range(H)]
dx = [1, 0]  # 斜めも含むならその方向もプラス
dy = [0, 1]

bfs((0, 0))

if dist[H - 1][W - 1] + 1 == n:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
import sys
from itertools import product
import copy

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    grid_init = [["." for _ in range(W)] for _ in range(H)]
    grid_init[0][0] = "#"
    for pattern in product(["L", "D"], repeat=H + W - 2):
        grid = copy.deepcopy(grid_init)
        if pattern.count("L") == W - 1 or pattern.count("D") == H - 1:
            h, w = 0, 0
            for p in pattern:
                if p == "L":
                    w += 1
                else:
                    h += 1
                grid[h][w] = "#"

            flg = True
            for h in range(H):
                for w in range(W):
                    if A[h][w] != grid[h][w]:
                        flg = False
                        break

            if flg:
                print("Possible")
                break
    else:
        print("Impossible")


if __name__ == '__main__':
    resolve()

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 = []
B = ["."] * (w + 2)
A.append(B)
temp = 0
for i in range(h):
    T = ['.'] + list(input()) + ['.']
    A.append(T)
    temp += T.count('#')
A.append(B)

t = 1
x = 1
y = 1
ans = 0
while t:
    if A[x][y] == '#':
        C = []
        C.append(A[x][y + 1])
        C.append(A[x+1][y])
        if C.count('#') > 1:
            t = 0
        else:
            A[x][y] = '?'
            if A[x][y+1] == '#':
                y = y + 1
            else:
                x = x + 1
            ans += 1
    else:
        t = 0

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
a = [input() for i in range(h)]
ok = True
l = [False]*w
for i in range(h):
    d = False
    for j in range(w):
        if a[i][j]=='#':
            if i<h-1 and a[i+1][j]=='#':
                if d:ok=False
                d = True
            else:
                if l[j]: ok=False
                l[j] = True
print('Possible' if ok else 'Impossible')

Submission status: Accepted

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

a=[str(input()) for _ in range(h)]
ans=0
for i in range(h):
    ans+=a[i].count("#")
#print(ans)
if ans==h+w-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

count = 0

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]


def dfs(i, j):
    global flag, grid
    grid[i][j] = '.'
    if i == H and j == W:
        fgrid = flatten_2dim(grid)
        flag = ('#' in fgrid)
    if grid[i][j+1] == '#':
        dfs(i, j+1)
    if grid[i+1][j] == '#':
        dfs(i+1, j)
    grid[i][j] = '#'


def main():
    global H, W, grid, flag
    H, W = map(int, readline().split())
    grid = []
    grid.append(['.']*(W+2))
    for _ in range(H):
        grid.append(['.'] + list(readline()[:-1]) + ['.'])
    grid.append(['.']*(W+2))
    flag = True
    dfs(1, 1)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for hi in range(h-1):
    for wi in range(w-1):
        if al[hi][wi]==al[hi+1][wi]==al[hi][wi+1]=="#":
            print("Impossible")
            exit()
        if al[hi+1][wi]==al[hi+1][wi+1]==al[hi][wi+1]=="#":
            print("Impossible")
            exit()
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:
  ans = 'Possible'
else:
  ans = 'Impossible'
print(ans)

Submission status: Accepted

Solution code:
# AGC 007: A – Shik and Stone
H, W = [int(s) for s in input().split()]
A = [input() for _ in range(H)]

isExact = 'Possible'

i, j = 0, 0

while i < H - 1 or j < W - 1:
    if ((i + 1 < H and A[i + 1][j] != '#') and (j + 1 < W and A[i][j + 1] != '#')) \
            or (i + 1 == H and j + 1 < W and A[i][j + 1] != '#') \
            or (i + 1 < H and j + 1 == W and A[i + 1][j] != '#'):
        isExact = 'Impossible'
        break
    elif j + 1 < W and A[i][j + 1] == '#':
        A[i] = A[i][:j] + '.' + A[i][j + 1:]
        j += 1
    elif i + 1 < H and A[i + 1][j] == '#':
        A[i] = A[i][:j] + '.' + A[i][j + 1:]
        i += 1

if isExact == 'Possible':
    A[H - 1] = A[H - 1][:W - 1] + '.'

    for line in A:
        if '#' in line:
            isExact = 'Impossible'
            break

print(isExact)

Submission status: Accepted

Solution code:

h,w = map(int,input().split())
g = [input() for _ in range(h)]
num = 0

for i in range(h):
    num += g[i].count("#")

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

Submission status: Accepted

Solution code:
import collections
H, W = map(int, input().split())
A = [input() for _ in range(H)]
A = [a+'.' for a in A]
A.append('.'*(W+1))

cnt = -1
for a in A:
    cnt += a.count('#')

i=j=0
flg=False
while True:
    if (A[i][j+1]=='#' and A[i+1][j]=='.'):
        j += 1
        cnt -= 1
    elif (A[i][j+1]=='.' and A[i+1][j]=='#'):
        i += 1
        cnt -= 1
    else:
        break
    
    if i==H-1 and j==W-1 and cnt==0:
        flg=True
        break

ans = 'Possible' if flg else 'Impossible'
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

import copy

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

B = copy.deepcopy(A)
for h in range(H):
    for w in range(W):
        B[h][w] = A[h][w] == "."

def dfs(h, w, C):
    if h == H or w == W:
        return False
    if A[h][w] == ".":
        return False
    X = copy.deepcopy(C)
    X[h][w] = True
    if [h,w] == [H-1,W-1]:
        tmp = True
        for x in X:
            tmp = tmp and all(x)
        return tmp
    return dfs(h+1, w, X) or dfs(h, w+1, X)

print("Possible" if dfs(0,0,B) else "Impossible")

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [input() for _ in range(H)]
x = 0
for h in range(H):
    if '#' in A[h][:x]:
        print('Impossible')
        exit()
    if A[h][x] != '#':
        print('Impossible')
        exit()
    while x+1 < W and A[h][x+1] == '#':
        x += 1

    if '#' in A[h][x+1:]:
        print('Impossible')
        exit()

print('Possible')

Submission status: Accepted

Solution code:
h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'.'
    a=list(a)
    for i in a:
        if i == '#':
            count += 1
    ab.append(a)
ab.append(list('.'*w))

if count != h+w-1:
    print('Impossible')
    exit()
            
step = [[0, 0]]
 
while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print('Possible')
        exit()
    if ab[y+1][x] == '#' :
        step.append([y+1, x])
    elif ab[y][x+1] == '#' :
        step.append([y, x+1])

print('Impossible')

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
c = [input() for _ in range(H)]
dist = [[-1]*W for _ in range(H)]

now = 0
for h in range(H):
    now = min(now,W-1)
    if c[h][now]!="#":
        print("Impossible")
        exit()
    for w in range(now,W):
        if c[h][w]==".":
            now-=1
            break
        else:
            dist[h][w]=0
            now+=1

for h in range(H):
    for w in range(W):
        if c[h][w]=="#" and dist[h][w]==-1:
            print("Impossible")
            exit()

if c[H-1][W-1]=="#":
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
h,w = map(int,input().split())
A = [list(input()) for i in range(h)]
que = collections.deque()
que.append((0,0))
while que:
  i,j = que.popleft()
  A[i][j] = "."
  if 0 <= i+1 < h:
    if A[i+1][j] == "#":
      que.append((i+1,j))
      continue
  if 0 <= j + 1 < w:
    if A[i][j+1] == "#":
      que.append((i,j+1))
# print(*A,sep="\n")
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      print("Impossible")
      exit()
print("Possible")

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
a = [list(input()) for _ in range(h)]
dx,dy = [1,0],[0,1]
flag = True
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que = deque()
            que.append((i,j))
            a[i][j] = '.'
            while que:
                y,x = que.popleft()
                for k in range(2):
                    ny, nx = y + dy[k], x + dx[k]
                    if 0 <= ny < h and 0 <= nx < w:
                        if a[ny][nx] == '#':
                            que.append((ny,nx))
                            a[ny][nx] = '.'
                            break
            flag = False
            break
    if not flag:
        break


for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            print('Impossible')
            quit()
print('Possible')

Submission status: Accepted

Solution code:
import numpy as np
H,W=map(int, input().split())
A=[]
for i in range(H):
    a=list(input())
    A.append(a)

A=np.array(A)
ok=True
for h in range(H):
    for w in range(W):
        
        lu=0
        rd=0
        if A[h,w]=="#":
            if 0<=h-1 and h-1<H:
                if A[h-1,w]=="#":
                    lu+=1
            if 0<=w-1 and w-1<W:
                if A[h,w-1]=="#":
                    lu+=1
            if 0<=h+1 and h+1<H:
                if A[h+1,w]=="#":
                    rd+=1
            if 0<=w+1 and w+1<W:
                if A[h,w+1]=="#":
                    rd+=1
            if h==0 and w==0:
                lu=1
            if h==H-1 and w==W-1:
                rd=1
            if lu!=1 or rd!=1:
                ok=False
if ok:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
# Problem A - Shik and Stone

# input
H, W = map(int, input().split())
board = [['']*W for i in range(H)]
for i in range(H):
    s = list(input())
    for j in range(W):
        board[i][j] = s[j]

# initialization
max_pos = 0
is_ok = True

# check
for i in range(H):
    tmp_min_pos = W
    tmp_max_pos = 0
    for j in range(W):
        if board[i][j]=='#':
            tmp_min_pos = min(tmp_min_pos, j)
            tmp_max_pos = max(tmp_max_pos, j)
    if not tmp_min_pos==max_pos:
        is_ok = False
    max_pos = tmp_max_pos

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
a = [list(input()) for _ in range(h)]
count = 0
for y in range(h):
    for x in range(w):
        if a[y][x]=="#":
            count += 1
            
visited = [[0]*w for _ in range(h)]
q = [(0,0)]
visited[0][0] = 1
while q:
    cy,cx = q.pop()
    for dy,dx in ((1,0),(0,1)):
        ny,nx = cy+dy,cx+dx
        if (0<=ny<h and 0<=nx<w and a[ny][nx]=="#" and visited[ny][nx]==0):
            visited[ny][nx] = visited[cy][cx]+1
            q.append((ny,nx))
            
if visited[h-1][w-1]==count:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
        H, W = map(int, input().split())
        maze = [input() for _ in range(H)]
        cnt=0
        for i in maze:
            for j in i:
                if j=='#':
                    cnt+=1
        print('Possible' if cnt==(H-1)+(W-1)+1 else 'Impossible')

resolve()

Submission status: Accepted

Solution code:
def lake(x,y):
    l[x][y] = "."
    for i in range(2):
        xi = x + dx[i]
        yi = y + dy[i]
        if 0 <= xi < n and 0 <= yi < m and l[xi][yi] == "#":
            lake(xi,yi)
            break


n,m = map(int, input().split())
l = [list(input()) for _ in range(n)]
l[0][0]=="."
dx = [1,0]
dy = [0,1]
lake(0,0)
for i in range(n):
    for j in range(m):
        if l[i][j] == "#":
            print("Impossible")
            exit()

print("Possible")

Submission status: Accepted

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

i = j = 0

visited = [[None] * W for _ in range(H)]

def dp(i, j):
    global H, W
    visited[i][j] = True
    if i == H - 1 and j == W - 1: return True
    #
    if i + 1 >= H:
        d = False
    else:
        d = (A[i + 1][j] == '#')
    #
    if j + 1 >= W:
        r = False
    else:
        r = (A[i][j + 1] == '#')
    #
    if d and not r:
        return dp(i + 1, j)
    elif not d and r:
        return dp(i, j + 1)
    else:
        return False

if dp(0, 0):
    ans = 'Possible'
    for i in range(H):
        for j in range(W):
            if not visited[i][j] and A[i][j] == '#':
                ans = 'Impossible'
    #
    print(ans)
else:
    print('Impossible')

Submission status: Accepted

Solution code:
from collections import deque


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

q = deque([(0, 0)])
while q:
    i, j = q.pop()
    cnt = 0
    if i == h - 1 and j == w - 1:
        break
    for nxt_i, nxt_j in [(i + 1, j), (i, j + 1)]:
        if not(0 <= nxt_i < h and 0 <= nxt_j < w):
            continue
        if a[nxt_i][nxt_j] == "#":
            cnt += 1
            q.append((nxt_i, nxt_j))
    if cnt != 1:
        print("Impossible")
        exit()

cnt = 0
for i in range(h):
    cnt += a[i].count("#")
if cnt != h + w - 1:
    print("Impossible")
else:
    print("Possible")

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):
  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 = [input() for i in range(H)]

from collections import deque
dxy = [(0,1),(1,0)]
dist = [[0]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
visited[0][0] = 1
q = deque([(0,0)])
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if visited[ny][nx]: continue
        if A[ny][nx] == '.': continue
        visited[ny][nx] = 1
        dist[ny][nx] = dist[y][x] + 1
        q.append((nx,ny))

cnt = sum(row.count('#') for row in A)
print('Possible' if dist[-1][-1]+1 == cnt else 'Impossible')

Submission status: Accepted

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

p = -1
q = -1
for i in range(h):
    for j in range(w):
        if A[i][j] == '#':
            if q > j:
                print('Impossible')
                exit()
            else:
                p = j
    q = p
else:
    print('Possible')

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

d = [(1,0),(0,1)]
def solve():
    h,w = LI()
    a = [input() for i in range(h)]
    q = deque([(0,0)])
    bfs = [[0]*w for i in range(h)]
    bfs[0][0] = 1
    while q:
        y,x = q.popleft()
        if q:
            print("Impossible")
            return
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if a[ny][nx] != ".":
                    if not bfs[ny][nx]:
                        bfs[ny][nx] = 1
                        q.append((ny,nx))
    for y in range(h):
        for x in range(w):
            if a[y][x] != "." and not bfs[y][x]:
                print("Impossible")
                return
    print("Possible")
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
*t,=open(0)
print(["Imp", "P"][int(t[0][0])+int(t[0][2])-1==sum(s.count("#")for s in t[1:])]+"ossible")

Submission status: Accepted

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

Submission status: Accepted

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

ans = True
h = 0
w = 0
B = [[1 if a == '#' else 0 for a in a_list] for a_list in A]
while (ans) and not (h == H - 1 and w == W - 1):
    B[h][w] = 0
    if h == H - 1:
        if A[h][w + 1] == '.':
            ans = False
        else:
            w += 1
    elif w == W - 1:
        if A[h + 1][w] == '.':
            ans = False
        else:
            h += 1
    else:
        sh = A[h + 1][w]
        sw = A[h][w + 1]
        if sh == '#' and sw == '#':
            ans = False
        elif sh == '.' and sw == '.':
            ans = False
        elif sh == '#' and sw == '.':
            h += 1
        else:
            w += 1

s = sum([sum(b_list) for b_list in B])
if ans and s == 1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
import sys
from sys import stdin

h, w = map(int, stdin.readline().rstrip().split())
a = [stdin.readline().rstrip() for i in range(h)]
count = 0
for i in a:
    for j in i:
        if j == '#':
            count += 1
if h + w - 1 == count:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]


def solve():
    h, w = MI()
    cnt = 0
    for i in range(h):
        l = list(input())
        for j in range(w):
            if l[j] == '#':
                cnt = cnt + 1
    if h + w - 1 == cnt:
        print('Possible')
    else:
        print('Impossible')

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

# #の数が最低限必要な数より多いとImpossibleとなる
print ("Impossible") if c > H+W-1 else print ("Possible")

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

n=A.count("#")
if n==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 y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            cnt += 1

x, y = 0, 0
seen = 0
while 0 <= x < W and 0 <= y < H:
    #print(x, y)
    if 0 <= y < H - 1 and A[y + 1][x] == '#':
        y = y + 1
        seen += 1
    elif 0 <= x < W - 1 and A[y][x + 1] == '#':
        x = x + 1
        seen += 1
    elif x == W - 1 and y == H - 1:
        #print(cnt)
        if seen == cnt - 1:
            print('Possible')
            break
        else:
            print('Impossible')
            break
    else:
        print('Impossible')
        break

Submission status: Accepted

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

Submission status: Accepted

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

ans = "Possible"
for i in range(h-1):
    for y in range(w-1):
        if a[i][y+1] == a[i+1][y] == "#":
            ans = "Impossible"
            break
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def dfs(x, y): 
    if x == h-1 and y == w-1:
        a[x][y] = "."
        judge()

    if a[x][y] == "#":
        a[x][y] = "."

    if y+1 < w and a[x][y+1] != ".":
        dfs(x, y+1)#右
    
    if x+1 < h and a[x+1][y] != ".":
        dfs(x+1, y)#下
    
    judge()
    
def judge():
    for i in range(h):
        if "#" in a[i]:
            print("Impossible")
            exit()
    print("Possible")
    exit()

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

dfs(0, 0)

Submission status: Accepted

Solution code:

def dfs(x, y): 
    if x == h-1 and y == w-1:
        a[x][y] = "."
        # print(a)
        for i in range(h):
            if "#" in a[i]:
                print("Impossible")
                exit()
        print("Possible")
        exit()
    
    if a[x][y] == "#":
        a[x][y] = "."

    if y+1 < w and a[x][y+1] != ".":
        dfs(x, y+1)#右
    
    if x+1 < h and a[x+1][y] != ".":
        dfs(x+1, y)#下
    
    for i in range(h):
        if "#" in a[i]:
            print("Impossible")
            exit()
    print("Possible")
    exit()

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

dfs(0, 0)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

x,y = m()

co = 0

for i in range(x):
    po = input()
    co += po.count("#")
print("Possible" if x+y - 1 == co else "Impossible")

Submission status: Accepted

Solution code:
h,w = list(map(int, input().split()))
a = [input() for _ in range(h)]
ftpcount = 0
for i in a:
    ftpcount += i.count('#')

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

Submission status: Accepted

Solution code:
"""
def dfs(s):
    global ans
    for u in v:
        x = s[0] + u[0]
        y = s[1] + u[1]
        if x < h and y < w:
            b[x][y] = "#"
            dfs([x, y])
            b[x][y] = "."
    if a == b:
        ans = 1
    return

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
v = [[1, 0], [0, 1]]
b = [["."] * w for _ in range(h)]
b[0][0] = "#"
s = [0, 0]
ans = 0
dfs(s)
print("Possible" if ans == 1 else "Impossible")
"""

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
c = 1
for b in a:
    c += b.count("#")
print("Possible" if c == h + w else "Impossible")

Submission status: Accepted

Solution code:
def dfs(s):
    global ans
    for u in v:
        x = s[0] + u[0]
        y = s[1] + u[1]
        if x < h and y < w:
            b[x][y] = "#"
            dfs([x, y])
            b[x][y] = "."
    if a == b:
        ans = 1
    return

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
v = [[1, 0], [0, 1]]
b = [["."] * w for _ in range(h)]
b[0][0] = "#"
s = [0, 0]
ans = 0
dfs(s)
print("Possible" if ans == 1 else "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):
    for j in range(w):
        if a[i][j] == "#":
            cnt += 1
if cnt == h+w-1:
    print("Possible")
else:
    print("Impossible")