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 dfs(maze, cnt, x, y):
    global H, W, count, can
    if x == H-1 and y == W-1:
        if cnt == count:
            can = "Possible"
    for dx, dy in ([1, 0], [0, 1]):
        new_x , new_y = x + dx, y + dy
        if new_x < 0 or new_x >= H or new_y < 0 or new_y >= W:
            continue
        elif maze[new_x][new_y] == '#':
            cnt += 1
            dfs(maze, cnt, new_x, new_y)
            cnt -= 1

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = []
    for _ in range(H):
        a = [c for c in input()]
        maze.append(a)
    count = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '#':
                count += 1
    cnt = 1 
    can = "Impossible"
    dfs(maze, cnt, 0, 0)
    print(can)

Submission status: Accepted

Solution code:
import sys
H,W = map(int, input().split())
x_pos = 0
for _ in range(H):
    a = input()
    for i in range(W):
        if i<x_pos and a[i]=="#":
            print("Impossible")
            sys.exit()
        if a[i]=="#":
            x_pos = max(x_pos, i)
print("Possible")

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
Ass = ['.#' + '.' * W] + ['.' + input() + '.' for _ in range(H)] + ['.' * W + '#.']

def solve():
    for x in range(1, H + 1):
        for y in range(1, W + 1):
            if Ass[x][y] == '.': continue
            isOK_pX = Ass[x - 1][y] == '#'
            isOK_pY = Ass[x][y - 1] == '#'
            isOK_nX = Ass[x + 1][y] == '#'
            isOK_nY = Ass[x][y + 1] == '#'
            if isOK_pX == isOK_pY or isOK_nX == isOK_nY:
                print('Impossible')
                return
    print('Possible')

solve()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [[] for i in range(H)]
check1 = 0
check2 = 1
now = [0, 0]
flag = True

for i in range(H):
    A[i] = input()
    check1 += A[i].count('#')
    
for iii in range(30000):
    lim = 0
    for dy, dx in [1, 0], [0, 1]:
        lim += 1
        if now[0] + dy <= H-1 and now[1] + dx <= W-1:
            if A[now[0] + dy][now[1] + dx] == '#':
                check2 += 1
                now[0] += dy
                now[1] += dx
                break
                
        if lim == 2:
            break
                
if check2 == check1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
h, w = [int(i) for i in input().split()]
adj = [["" for _ in range(w)] for j in range(h)]
for i in range(h):
    _tmp = input()
    for j in range(w):
        adj[i][j] = _tmp[j]
# for i in range(h):
    # print(adj[i])
for i in range(h):
    for j in range(w):
        if (i > 0 or j > 0) and adj[i][j] == "#":
            okFlag = False
            if i > 0 and adj[i - 1][j] == "#":
                okFlag = True
                adj[i - 1][j] = "."
            elif j > 0 and adj[i][j - 1] == "#":
                okFlag = True
                adj[i][j - 1] = "."
            if not okFlag:
                print("Impossible")
                # print("[{},{}]".format(i, j))
                exit()
print("Possible")
# for i in range(len(adj)):
    # print(adj[i])

Submission status: Accepted

Solution code:
H, W, A = open(0).read().split(maxsplit=2)
if A.count('#') == int(H) + int(W) - 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
pos = 0
for _ in range(H):
    row = input()
    for c in row[:pos]:
        if c == '#':
            print('Impossible')
            exit()
    for i in range(pos, W):
        if row[i] == '#':
            pos = i
        else:
            break
    for c in row[pos + 1:]:
        if c == '#':
            print('Impossible')
            exit()
if pos + 1 == W:
    print('Possible')
else:
    print('Impossible')

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

queue = [(0, 0, 1)]
depth = 0
while queue:
    q = queue.pop(0)
    depth = max(depth, q[2])
    if A[q[0]][q[1]] == ".":
        continue
    if (q[0], q[1]) == (H-1, W-1):
        break
    if(q[0]+1 < H):
        queue.append((q[0]+1, q[1], q[2]+1))
    if(q[1]+1 < W):
        queue.append((q[0], q[1]+1, q[2]+1))

print("Possible" if depth==count else "Impossible")

Submission status: Accepted

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


def parse(x, y):
    A[x][y] = '.'
    cand_OK = []
    cand_NG = []
    if x < H - 1:
        cand_OK += [[x + 1, y]]
    if y < W - 1:
        cand_OK += [[x, y + 1]]
    if x > 0:
        cand_NG += [[x - 1, y]]
    if y > 0:
        cand_NG += [[x, y - 1]]
    if any([A[i][j] == '#' for i, j in cand_NG]):
        return False
    if sum([A[i][j] == '#' for i, j in cand_OK]) == 2:
        return False
    if sum([A[i][j] == '.' for i, j in cand_OK]) == 2:
        return False
    if x == H - 1 and y == W - 1:
        return True
    for i, j in cand_OK:
        if A[i][j] == '#':
            return parse(i, j)


if parse(0, 0):
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

x = 0
y = 0

c = 0
a[0][0] = '.'
while x != w-1 or y != h-1:
    r = 0
    if x <= w-2:
        if a[y][x+1] == '#':
            r = 1
            a[y][x+1] = '.'
    if y <= h-2:
        if a[y+1][x] == '#':
            r += 2
            a[y+1][x] = '.'
    if x >= 1:
        if a[y][x-1] == '#':
            r = 0
    if y >= 1:
        if a[y-1][x] == '#':
            r = 0
    if r == 2:
        y += 1
    if r == 1:
        x += 1
    if x == w-1 and y == h-1:
        if a[y-1][x] == '.' and a[y][x-1] == '.':
            c = 1
    if r == 0 or r == 3:
        c = -1
        x = w-1
        y = h-1

    

    
if c == 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
x = 0
for i in range(h):
    cells = input()
    if cells.find('#') == x:
        x = cells.rfind('#')
    else:
        print('Impossible')
        exit()
print('Possible')

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
x,y=0,0
while(x<h and y<w):
    a[x][y]='.'
    if y+1<w and a[x][y+1]=="#":
        y+=1
    elif x+1<h and a[x+1][y]=="#":
        x+=1
    else:
        break
j=True
for b in a:
    for t in b:
        if t=="#":
            j=False
            break
print("Possible" if j else "Impossible")

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
h = 0
w = 0
flag = 0
ans = 0
counter = 0
L = []
for i in range(H) :
    l = input()
    counter += l.count("#")
    L.append(l)

while flag == 0 :
    if h == (H-1) and w == (W-1) :
        ans = 1
        flag = 1
    else :
        if w == (W-1) :
            if L[h+1][w] == "#" :
                h += 1
            else :
                flag = 1
        elif h == (H-1) :
            if L[h][w+1] == "#" :
                w += 1
            else :
                flag = 1
        else :
            if L[h+1][w] == "#" and L[h][w+1] == "#" :
                flag = 1
            else :
                if L[h+1][w] == "#" :
                    h += 1
                elif L[h][w+1] == "#" :
                    w += 1
                else :
                    flag = 1
                
if ans == 1 and ((H+W-1) == counter) :
    print("Possible")
else :
    print("Impossible")

Submission status: Accepted

Solution code:
height, width = map(int, input().split())

arr = []

for i in range(height):
    s = input()
    a = []
    for j in range(width):
        if s[j] == '#':
            a.append(1)
        else:
            a.append(0)
    arr.append(a)
    
h = 0
w = 0
f = 1

if arr[0][0] == 0:
    h = height-1
    w = width-1
    f = 0

while h < height-1 or w < width-1:
    if h == height-1:
        if arr[h][w+1] == 0:
            f = 0
            break
        else:
            arr[h][w+1] = 0
            w += 1
    elif w == width-1:
        if arr[h+1][w] == 0:
            f = 0
            break
        else:
            arr[h+1][w] = 0
            h += 1
    else:
        if arr[h][w+1] == 0:
            if arr[h+1][w] == 0:
                f = 0
                break
            else:
                arr[h+1][w] = 0
                h += 1
        else:
            if arr[h+1][w] == 1:
                f = 0
                break
            else:
                arr[h][w+1] = 0
                w += 1


if f == 0:
    print('Impossible')
else:
    extra = 0
    for i in range(height):
        for j in range(width):
            extra += arr[i][j]
    if extra > 1:
        print('Impossible')
    else:
        print('Possible')

Submission status: Accepted

Solution code:
import sys


def main() -> None:
    h, w = [int(next_str()) for _ in range(2)]
    cnt = 0
    for i in range(h):
        cnt += input().count("#")
    print(["Impossible", "Possible"][cnt == h + w - 1])


def next_str() -> str:
    result = ""
    while True:
        tmp = sys.stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


if __name__ == '__main__':
    main()

Submission status: Accepted

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

result = []

for i in range(H):
    a = input()
    result.append(a)

possibility = True

for i in range(H):
    for j in range(W):
        if j != W - 1 and i != H - 1:
            if result[i][j] == "#" and result[i + 1][j] == result[i][j] and result[i][j + 1] == result[i][j]:
                possibility = False
        if i != 0 and j !=0:
            if result[i][j] == "#" and result[i-1][j] == "." and result[i][j-1] == ".":
                possibility = False
if possibility:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

Submission status: Accepted

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

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

judge = "Possible"
x = 0
y = 0
for i in range(H + W - 2):
	if x == W - 1:
		if A[y + 1][x] == "#":
			y += 1
		else:
			judge = "Impossible"
			break
	elif y == H - 1:
		if A[y][x + 1] == "#":
			x += 1
		else:
			judge = "Impossible"
			break

	else:
		if A[y + 1][x] == "#":
			if A[y][x + 1] == "#":
				judge = "Impossible"
				break
			else:
				y += 1
		else:
			if A[y][x + 1] == "#":
				x += 1
			else:
				judge = "Impossible"
				break

s = 0
for i in range(H):
	s += A[i].count("#")

if s != H + W - 1:
	judge = "Impossible"

if A[0][0] != "#":
	judge = "Impossible"

if A[H - 1][W - 1] != "#":
	judge = "Impossible"

print(judge)

Submission status: Accepted

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

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=[list(input()) for i in range(h)]
count=0
for i in a:
    count+=i.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 i in range(h)]
c=0
for j in range(h):
  for k in range(w):
    if a[j][k]=='#':c+=1
if c==h+w-1:print('Possible')
else:print('Impossible')

Submission status: Accepted

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

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

Submission status: Accepted

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

a = []
count = 0

for i in range(h):
    a.append(list(input()))
    count += a[i].count("#")

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

Submission status: Accepted

Solution code:
t=open(0).read();print(('P'*(t.count('#')<sum(map(int,t.split()[:2])))or'Imp')+'ossible')

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[input()for _ in[0]*h]
a=[['..','..'],['.#','..'],['..','#.'],['##','..'],['..','##'],['#.','#.'],['.#','.#'],['##','.#'],['#.','##']]
for i in range(h-1):
  for j in range(w-1):
    t=s[i][j:j+2]
    u=s[i+1][j:j+2]
    for b in a:
      if t==b[0]and u==b[1]:
        break
    else:
      print('Impossible')
      exit()
print('Possible')

Submission status: Accepted

Solution code:
import copy

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

list_check = copy.deepcopy(list_a)
for i in range(0,h):
    for j in range(0,w):
        list_a[i][j] = "."

i = 0
j = 0
while True:
    if i == h-1 and j == w-1:
        list_a[i][j] = "#"
        break
    if list_check[i][j] == "#":
        list_a[i][j] = "#"
        if i != h-1:
            i += 1
        else:
            j += 1
    else:
        i -= 1
        j += 1
        if j > w-1:
            ans = "Impossible"
            break
        if list_check[i][j] == ".":
            ans = "Impossible"
            break
if list_a == list_check:
    ans = "Possible"
else:
    ans = "Impossible"
print(ans)

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("#")
if(cnt==h+w-1):
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
H,W = (int(i) for i in input().split())

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

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

Submission status: Accepted

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

print('Impossible' if h + w - 1 != sum(A) else 'Possible')

Submission status: Accepted

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

migi = 0
ans = 1
for s in a:
    for cnt, i in enumerate(s):
        if cnt < migi and i == "#":
            ans = 0
        if i == "#":
            migi = cnt
print("Possible" if ans else "Impossible")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W = inpl()
MAP = [['.']*(W+2)]
for i in range(H):
	MAP.append(['.'] + list(input()) + ['.'])
MAP.append(['.']*(W+2))

x = y = 1
while x < W or y < H:
	ri = MAP[y][x+1]
	do = MAP[y+1][x]
	le = MAP[y][x-1]
	up = MAP[y-1][x]
	if ri == do or [ri,do,le,up].count('#')>2:
		print('Impossible')
		sys.exit()
	else:
		if ri == '#':
			x += 1
		else:
			y += 1


ri = MAP[y][x+1]
do = MAP[y+1][x]
le = MAP[y][x-1]
up = MAP[y-1][x]

if [ri,do,le,up].count('#')>=2:
	print('Impossible')
else:
	print('Possible')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W = [int(x) for x in input().split()]
A = [input() for i in range(0, H)]
i, j = 0, 0
H, W = H-1, W-1
moveX = [1, 0, -1, 0]
moveY = [0, 1, 0, -1]
while True:
    count = 0
    for k in range(0, 4):
        ii = i+moveX[k]
        jj = j+moveY[k]
        if 0 <= ii and ii <= H and 0 <= jj and jj <= W:
            if A[ii][jj] == '#':
                count += 1
    invalid = 2 if (not (i==0 and j==0)) and (not(i==H and j==W)) else 1  
    if count > invalid:
        print("Impossible")
        break
    if i < H and A[i+1][j] == '#':
        i = i+1
        continue
    if j < W and A[i][j+1] == '#':
        j = j+1
        continue
    if i == H and j == W:
        print("Possible")
        break
    else:
        print("Impossible")
        break

Submission status: Accepted

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

def solve(H, W, A):
    ssum = sum(row.count("#") for row in A)
    if ssum != H + W - 1:
        return False
    x, y = 0, 0
    if A[y][x] != "#":
        return False
    while 1:
        if y == H - 1 and x == W - 1:
            return True
        if (x + 1) < W and A[y][x + 1] == "#":
            x += 1
        elif (y + 1) < H and A[y + 1][x] == "#":
            y += 1
        else:
            return False

result = solve(H, W, A)

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

Submission status: Accepted

Solution code:
def chk_ent(r, c, arr):   
    chk_up = (arr[r-1][c] == '#') if ((r - 1) >= 0) else False
    chk_left = (arr[r][c-1] == '#') if ((c - 1) >= 0) else False
    
    return (chk_up, chk_left)

def chk_exit(r, c, arr):
    my_h = len(arr)
    my_w = len(arr[0])
    
    chk_down = (arr[r+1][c] == '#') if ((r + 1) < my_h) else False
    chk_right = (arr[r][c+1] == '#') if ((c + 1) < my_w) else False
    
    return (chk_down, chk_right)


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

r = 0
c = 0
while True:
    up, left = chk_ent(r, c, a)
    if (not(up or left) and not((r == 0) and (c == 0))) or (up and left):
        flg = False
        break
    down, right = chk_exit(r, c, a)
    if not(down or right):
        if((r == (h - 1)) and (c == (w - 1))):
            flg = True
            break
        else:
            flg = False
            break
    elif (down and right):
        flg = False
        break
    elif right:
        c += 1
    elif down:
        r += 1
print('Possible' if flg else 'Impossible')

Submission status: Accepted

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

if a.count("#") == h + w - 1:
	print("Possible")
else:
	print("Impossible")

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[list(input()).count('#')for i in range(h)]
print(["Imp","P"][sum(a)==h+w-1]+"ossible")

Submission status: Accepted

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

# 最小の道順でない場合、どこかで寄り道をしている→右、下以外の場所へ移動している

Submission status: Accepted

Solution code:
H, W = map(int, input().split(' '))
maps = [input().count('#') for _ in range(H)]
if sum(maps) == 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:
def main():
    h, w = map(int, input().split())
    a = [[j for j in input()] for i in range(h)]

    x, flg = (0, -1), False
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                if i == x[0] and j == x[1] + 1 or i == x[0] + 1 and j == x[1]:
                    x = i, j
                else:
                    break

        else:
            continue
        break

    else:
        flg = True

    if flg:
        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)]
cnt = 0
for i in range(H):
  cnt += A[i].count('#')

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

Submission status: Accepted

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

H, W = map(int, input().split())
A = []
for i in range(H):
    temp = list(input())
    A.append(temp)

def is_sharp(i, j):
    # print(i,j)
    if i<0 or j<0 or i>=H or j>=W:
        return False
    if A[i][j] == "#":
        return True
    else:
        return False

def ok(i,j):
    if is_sharp(i-1, j) and is_sharp(i,j-1):
        return False
    if is_sharp(i+1, j) and is_sharp(i,j+1):
        return False
    return True

for i in range(H):
    for j in range(W):
        if is_sharp(i,j) and (not ok(i,j)):
            print("Impossible")
            sys.exit(0)
print("Possible")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def read():
    return [int(x) for x in str.split(raw_input())]

n, m = read()
st = []
cnt = 0

for i in range(n):
    st.append(raw_input())
    for j in range(m):
        if (st[i][j] == '#'):
            cnt = cnt+1
            
def can_down(st, x, y):
    return x+1 < n and st[x+1][y] == '#'

def can_right(st, x, y):
    return y+1 < m and st[x][y+1] == '#'

def dfs(st, x, y, c):
    if (x == n-1 and y == m-1):
        return c == cnt
    down, right = can_down(st, x, y), can_right(st, x, y)
    if (down and right):
        return 0
    if ((not down) and (not right)):
        return 0
    if (down):
        return dfs(st, x+1, y, c+1)
    if (right):
        return dfs(st, x, y+1, c+1)

if (dfs(st, 0, 0, 1) == 1):
    print("Possible")
else:
    print("Impossible");

Submission status: Accepted

Solution code:
import sys
H,W = [int(i) for i in input().split()]
A = [list(input().strip()) for j in range(H)]

q = [(0,0)]
while q:
  h,w = q.pop()
  if (h,w) == (H-1,W-1):
    A[h][w] = '.'
    break
  for dh,dw in [(1,0),(0,1)]:
    nh,nw = h+dh,w+dw
    if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '#':
      q.append((nh,nw))
      A[h][w] = '.'
      break
  else:
    print('Impossible')
    sys.exit()

for h in range(H):
  for w in range(W):
    if A[h][w] == '#':
      print('Impossible')
      sys.exit()
print('Possible')

Submission status: Accepted

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

# AtCoder Grand Contest
# Problem A


if __name__ == '__main__':
    h, w = list(map(int, input().split()))
    board = [input() for i in range(h)]
    count = sum([board[i].count('#') for i in range(h)])

    # See:
    # https://www.youtube.com/watch?v=6ZP8JyGsQBs
    if count == (h + w - 1):
        print('Possible')
    else:
        print('Impossible')

Submission status: Accepted

Solution code:
def sarch(s):
    key = 0
    for i in range(len(s)):
        if s[i] == "#":
            key = i
    return key

def judge(s):
    key = 0
    for i in s:
        if i == "#":
            key = 1
            break
    return key

H, W = map(int, input().split())
A = [["0" for i in range(W)] for j in range(H)]
for i in range(H):
    S = input()
    for j in range(W):
        A[i][j] = S[j]
key = "Possible"
for i in range(1, H):
    if judge(A[i][0:sarch(A[i - 1])]) != 0:
        key = "Impossible"
        break
print(key)

Submission status: Accepted

Solution code:
h,w=[int(i) for i in input().split()]
s=0
l=0
for i in range(h):
  sf=True
  lf=False
  a=list(input().strip())
  for j in range(w):
    if a[j]=="#" and sf==True:
      s=j
      sf=False
      if s!=l and i!=0:
        print("Impossible")
        exit()
    if a[j]=="#" and lf==True:
      print("Impossible")
      exit()
    if a[j]=="." and sf==False and lf==False:
      l=j-1
      lf=True
  if sf==True:
    print("Impossible")
    exit()
  if lf==False:
    l=w-1
else:
  print("Possible")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
a = ['.'*(W+2)]
for i in range(H):
    a.append('.'+input()+'.')
a.append('.'*(W+2))
x, y = 1, 1
d = [0, 1], [1, 0]

#右と下だけで行けるところまで行く
while True:
    #現在地を探索済みにする
    a[x] = a[x][:y] + '*' + a[x][y+1:]
    
    if [x, y] == [H, W]:
        break
    
    #右か下に進む
    for d_i in d:
        if a[x+d_i[0]][y+d_i[1]]=='#':
            x, y = x+d_i[0], y+d_i[1]
            break
    #行き止まりなら終了
    else:
        break
    
    
#探索結果を確認
end = 0
for r_i in a:
    for j in r_i:
        if j == '#':
            print('Impossible')
            end = 1
            break
    if end == 1:
        break
else:
    print('Possible')

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
t=[list(input())for i in range(h)]
cnt=0
for i in range(h):
    for j in range(w):
        if t[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())
grid = [list(input()) for _ in range(h)]

for i in range(h-1):
    for j in range(1, w):
        if grid[i][j] == "#":
            if grid[i+1][j-1] == "#":
                print("Impossible")
                exit()

print("Possible")

Submission status: Accepted

Solution code:
from queue import Queue
import numpy as np

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

B = []
for i in range(H):
    B_sub = []
    for j in input():
        if j == "#":B_sub.append(5)
        else: B_sub.append(-1)
    B.append(B_sub)
    
qy,qx = Queue(),Queue()
qy.put(0)
qx.put(0)

isok = True
while(isok):
    if qy.empty() and qx.empty(): break
    else:
        y,x = qy.get(),qx.get()
        if y==0 and x==0: B[y][x] = 0

        if y<H-1 and B[y+1][x]==5:
            B[y+1][x] = 0
            qy.put(y+1)
            qx.put(x)
            if 5 in B[y]: isok = False
        elif x<W-1 and B[y][x+1]==5:
            B[y][x+1] = 0
            qy.put(y)
            qx.put(x+1)
            if 5 in np.array(B).T[x]: isok = False
            
            
if isok:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

count = h+m

for i in range(h):
    b =(list(input()))
    count -= b.count('#')
if count == 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

import sys, math, copy
# import fractions, itertools
# import numpy as np
# import scipy

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def main():
    h, w = map(int, input().split())
    su = 0
    for i in range(h):
        line = input()
        su += line.count("#")
    print("Possible" if su == h + w - 1 else "Impossible")

main()

Submission status: Accepted

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

# 数値の読み込み

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

x=0
for i in range(h):
    for j in range(x,w):
        #print(i,j,m[i][j])
        if m[i][j] == '#':
            #print("find")
            m[i][j]='.'
            x=j
        else:
            break
result="Possible"
for i in range(h):
    for j in range(w):
        if m[i][j] == '#':
            result="Impossible"

print(result)

Submission status: Accepted

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

shortest = (H-1) + (W-1)
tmp = -1
for i in range(H):
    tmp += input().count("#")

print("Possible" if tmp == shortest else "Impossible")