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:
def main():
    H, W = map(int, input().split())
    A = [
        list(input())
        for _ in range(H)
    ]

    # 2 <= H,W <= 8 より右下全列挙でもいけそう
    # H+W-2歩く(0,0からのため)、max:2 ** 14 = 16384
    # x:0, y:1
    p = [0] * (H + W - 2)

    def dfs(i):
        if i == H + W - 2:
            # 歩き方はあり得るか
            if p.count(1) != H-1 or p.count(0) != W-1:
                return False

            b = [
                ["."] * W
                for _ in range(H)
            ]
            x, y = (0, 0)
            b[0][0] = "#"
            for c in p:
                if c == 1:
                    y += 1
                else:
                    x += 1
                b[y][x] = "#"

            return A == b

        p[i] = 0
        if dfs(i + 1):
            return True
        p[i] = 1
        if dfs(i + 1):
            return True

        return False

    if dfs(0):
        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)]
count = 0
for i in range(H):
    for j in range(W):
        count += "#".count(A[i][j])
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)]


def enclose_field(field, outline="#"):
    """
    迷路等の外周をoutlineで埋めることで、IndexErrorを回避できます。
    [0, 0] → [1, 1]、[H-1, W-1] → [H, W]となります。
    """
    for i in range(len(field)):
        field[i] = [outline] + field[i] + [outline]
    field.append([outline] * (len(field[0])))
    field.insert(0, [outline] * (len(field[0])))
    return field


A = enclose_field(A, outline=".")
i = j = 1
while True:
    if A[i+1][j] == "#":
        A[i][j] = "."
        i += 1
        continue

    if A[i][j+1] == "#":
        A[i][j] = "."
        j += 1
        continue

    if i==H and j == W:
        A[i][j] = "."
        break

    print("Impossible")
    exit()

for a in A:
    if "#" in a:
        print("Impossible")
        break
else:
    print("Possible")

Submission status: Accepted

Solution code:
import sys


h,w=map(int,input().split())
c=0
for i in range(h):
    s=input()
    c+=s.count("#")
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 = [input() for i in range(h)]
num = 0
for i in a: num+=i.count("#")
if num==h+w-1: print("Possible")
else: print("Impossible")

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
meiros = [['' for x in range(w)] for y in range(h)]
for i in range(h):
  tmp = input().rstrip()
  for j in range(w):
    meiros[i][j] = tmp[j]
nowh,noww = 0,0
queue = [(0,0)]
flg = True
while 1:
  L = len(queue)
  if L == 0:
    break
  for z in range(L):
    nowh,noww = map(int,queue[0])
    queue.pop(0)
    if nowh + 1 < h:
      if meiros[nowh+1][noww] == '#':
        queue.append((nowh+1,noww))
    if noww + 1 < w:
      if meiros[nowh][noww+1] == '#':
        queue.append((nowh,noww+1))
    meiros[nowh][noww] = '.'
  if nowh != (h-1) and noww != (w-1) and len(queue) != L:
    flg = False
    break
for mairo in meiros:
  if '#' in mairo:
    flg = False
    break
if flg:
  print('Possible')
else:
  print('Impossible')

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
x = 0
y = 0
time = 0
cou = 0
lis = ""
for i in range(h):lis += str(input())
for i in range(h * w):
    if lis[i] == "#":
        cou += 1
for i in range(h):
    while lis[i * w + x] == "#" and y == 0:
        x += 1
        time += 1
        if x == w:
            x -= 1
            y = 1
    if i == h-1 and time == (h + w)-1 and time == cou:
        print("Possible")
        exit()
    time += 1
print("Impossible")

Submission status: Accepted

Solution code:
def isAble(a, r, c):
    lastC = 1
    for i in xrange(r):
        lowbit = a[i]&-a[i]
        if popcount(a[i]+lowbit)!=1:
            return False
        if lowbit!=lastC:
            return False
        lastC = (a[i]+lowbit)>>1
    if lastC!=(1<<(c-1)):
        return False
    return True

def popcount(x):
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f)
    x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff)
    x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff)
    return x

def main():
    r, c = [int(x) for x in raw_input().strip().split()]
    a = []
    for i in xrange(r):
        row = raw_input().strip()
        foo = 0
        for j in xrange(c):
            if row[j]=='#':
                foo |= 1<<j
        a.append(foo)
    if isAble(a, r, c):
        print 'Possible'
    else:
        print 'Impossible'

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
H,W = map(int,input().split())
src = [input() for i in range(H)]
ctr = Counter()
for row in src:
    ctr.update(row)
print('Possible' if ctr['#'] == H+W-1 else 'Impossible')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
H, W = map(int, input().split())
cnt = ''.join([input() for _ in range(H)]).count('#')
print(('Impossible', 'Possible')[cnt == H + W - 1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
H, W = map(int, input().split())
a = [''] * H
cnt = 0
for i in range(H):
    a[i] = list(input())
    cnt += len(list(filter(lambda x: x == '#', a[i])))

ans = False
if cnt == H + W - 1:
    y, x = 0, 0
    d = [1, 0, 1]
    for i in range(cnt):
        if y == H - 1 and x == W - 1:
            ans = True
            break
        for j in range(2):
            ny = y + d[j]
            nx = x + d[j + 1]
            if ny < H and nx < W and a[ny][nx] == '#':
                y, x = ny, nx
                break



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

Submission status: Accepted

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

A = [input() for _ in range(H)]
length = sum([a.count('#') for a in A])

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

Submission status: Accepted

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

A = [list(input()) for _ in range(H)]
length = 0
for a in A:
    for s in a:
        if s == '#':
            length += 1


def dfs(i, j, cnt):
    if i == H - 1 and j == W - 1:
        return cnt == length - 1
    else:
        if i < H - 1 and A[i + 1][j] == '#':
            return dfs(i + 1, j, cnt + 1)
        elif j < W - 1 and A[i][j + 1] == '#':
            return dfs(i, j + 1, cnt + 1)
        else:
            return False


print('Possible' if dfs(0, 0, 0) else 'Impossible')

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
h, w = map(int, input().split())
a = [ input() for _ in range(h) ]
result = ''.join(a).count('#') == h + w - 1
print(['Impossible', 'Possible'][result])

Submission status: Accepted

Solution code:
def shik_stone():
	h, w = map(int, raw_input().split(" "))
	m = []
	for i in range(h):
		m.append(str(raw_input()))
	current_most_right_index = 0
	for row in m:
		indices = [i for i, ltr in enumerate(row) if ltr == '#']
		if min(indices)==current_most_right_index:
			if len(indices)!=(max(indices)-min(indices)+1):
				print "Impossible"
				return
			else:
				current_most_right_index = max(indices)
		else:
			print "Impossible"
			return
	print "Possible"


if __name__ == "__main__":
	shik_stone()

Submission status: Accepted

Solution code:

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

cnt = 0
for h in range(H):
    for w in range(W):
        if m[h][w] == '#':
            cnt += 1

def rec(x, y):
    if x == W - 1 and y == H - 1:
        return True

    if m[y][x] != '#':
        return False
    dx = [0, 1]
    dy = [1, 0]

    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < W and \
           0 <= ny and ny < H:
            ret = rec(nx, ny)
            if ret:
                return ret
    return False


if rec(0, 0) and cnt == 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("#")
print("Possible") if ans == H+W-1 else print("Impossible")

Submission status: Accepted

Solution code:
h,w = map(int, raw_input().split())
m = [raw_input() for _ in range(h)]
possible = True
for y in range(h):
    for x in range(w):
        if m[y][x] == '#':
            p = 0
            if y > 0 and m[y-1][x] == '#':
                p += 1
            if x > 0 and m[y][x-1] == '#':
                p += 1
            if not(y == 0 and x == 0) and p != 1:
                possible = False
                break
            n = 0
            if y < h-1 and m[y+1][x] == '#':
                n += 1
            if x < w-1 and m[y][x+1] == '#':
                n += 1
            if not(y == h-1 and x == w-1) and n != 1:
                possible = False
                break
    if not possible:
        break
if possible:
    print 'Possible'
else:
    print 'Impossible'

Submission status: Accepted

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

    l = H + W - 1
    sharp = 0
    i = 0
    while i < H:
        A = str(input())
        sharp += A.count('#')
        i += 1

    if l == sharp:
        print('Possible')
    else:
        print('Impossible')

main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, Y = map(int, input().split())
P = 0
out = "Possible"
for i in range(H):
	inp = input()
	for j in range(Y):
		if inp[j] == "#" and j > P:
			P = j
		if inp[j] == "#" and j < P:
			out = "Impossible"
print(out)

Submission status: Accepted

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

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            a[i][j] = '.'
            break

for i in range(1,w):
    for j in range(h):
        if a[j][i] == '#':
            a[j][i] = '.'
            break

def check():
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                return 0;
    return 1;

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

Submission status: Accepted

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

def fun(aa,x,y):
    a=copy.deepcopy(aa)

    if h<=y or w<=x:
        return False

    if y==h-1 and x==w-1:
        count = 0
        for i in a:
            count += i.count('#')
        if count==1:
            return True
        else:
            return False

    if a[y][x]!="#":
        return False

    a[y][x]="."

    if fun(a,x+1,y) or fun(a,x,y+1):
        return True

    return False

a=[["" 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]



print("Possible" if fun(a,0,0) else "Impossible")

Submission status: Accepted

Solution code:
def feasible():
    n, m = map(int, raw_input().split())
    g = [ raw_input().strip() for r in range(n) ]
    start = 0
    for row in g:
        in_row = False
        found_row = False
        for c, ch in enumerate(row):
            if ch == '.':
                in_row = False
                continue
            if c < start:
                return False
            if not in_row and found_row:
                return False
            in_row = True
            found_row = True
            start = c
    return True
                
print('Possible' if feasible() else 'Impossible')

Submission status: Accepted

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

def dfs(i, j):
    if(i == h-1 and j == w-1):
        return 'Possible'
    if(i < h-1 and A[i+1][j] == '#'):
        return dfs(i+1, j)
    if(j < w-1 and A[i][j+1] == '#'):
        return dfs(i, j+1)
    return 'Impossible'

if sum([a.count('#') for a in A]) != (h+w-1):
    print('Impossible')
else:
    print(dfs(0, 0))

Submission status: Accepted

Solution code:
#agc007a

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

Submission status: Accepted

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

arr=[]
arr.append([".","#"]+["."]*w)
for _ in range(h):
    arr.append(["."]+list(input())+["."])
arr.append(["."]*w+["#","."])
#for row in arr:
#    print(row)

for i in range(h):
    for j in range(w):
        if arr[i+1][j+1]=='#':
            if arr[i][j+1]==arr[i+1][j] or arr[i+2][j+1]==arr[i+1][j+2]:
                print("Impossible")
                exit(0)

print("Possible")

Submission status: Accepted

Solution code:
list = input().split()
h = int(list[0])
w = int(list[1])

k = 0
for i in range (0,h):
   k += input().count("#")

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

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


def f():
    h,w = list(map(int, input().split()))
    a = [input() for _ in range(h)]
    c = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                c += 1
    if c == h + w -1:
        return 'Possible'
    return 'Impossible'


print(f())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
sharp=0
for i in range(h):
    row=str(input())
    sharp += row.count('#')

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

Submission status: Accepted

Solution code:
def dfs(l,x,y):
    
    if x+1 is w and y+1 is h:
        return l
    
    #right
    if w > x+1:
        if "#" is l[y][x+1]:

            l2 = list(l)
            l2[y][x+1] = "."

            return dfs(l2,x+1,y)

    #down
    if h > y+1:
        if "#" is l[y+1][x]:
            l3 = list(l)
            l3[y+1][x]= "."
            return  dfs(l3,x,y+1)



h,w = map(int,raw_input().split())


l = []
for i in range(h):
    l.append(list(raw_input()))

# print l
l[0][0] = "."
l2 = dfs(l,0,0)
# print l2
if l2:
    if "#" in [x for sublist in l2 for x in sublist]:
        print "Impossible"
    else:
        print "Possible"
else:
    print "Impossible"

Submission status: Accepted

Solution code:
import sys
h, w = map(int, input().split())
i = 0
pos = 0
while h > i:
    s = input()
    l = s.find('#')
    r = s.rfind('#')
    if (l == pos and r >= pos):
        pos = r
        i += 1
    else:
        print('Impossible')
        sys.exit()
print('Possible')

Submission status: Accepted

Solution code:
from sys import stdin

nbLig,nbCol=map(int,stdin.readline().split())
grille=[]
possible=[[-1]*nbCol for i in range(nbLig)]
possible[0][0]=0
for i in range(nbLig):
    ligne=stdin.readline()
    grille.append(ligne)
compteur=0
cases=0
for lig in range(nbLig):
    for col in range(nbCol):
        if grille[lig][col]=="#" and (lig!=0 or col!=0):
            cases+=1
            maximum=-1
            if lig>0:
                maximum=max(maximum,possible[lig-1][col])
            if col>0:
                maximum=max(maximum,possible[lig][col-1])
            possible[lig][col]=maximum+1

if cases==possible[nbLig-1][nbCol-1]:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
import sys
lines = sys.stdin.readlines()
sizes = lines[0].split(" ")
H = int(sizes[0])
W = int(sizes[1])
field = []
for line in lines[1:]:
    field.append(line.rstrip())

#print (field)
count=0
for f in field:
    for i in range(W):
        s = f[i:i+1]
        if s=="#":
            count+=1


posQ = [[0,0]]

now = [0,0]
before = [-1,0]

while(now[0]+1<H or now[1]+1<W):
    if (before==now):
        break
    #print (now)
    if now[1]+1<W:
        if field[now[0]][now[1]+1:now[1]+2] == "#":
            posQ.append([now[0],now[1]+1])
    if now[0]+1<H:
        if field[now[0]+1][now[1]:now[1]+1] == "#":
            posQ.append([now[0]+1,now[1]])
    before = now
    now = posQ[len(posQ)-1]

"""
now = [0,0]

if field[now[0]][now[1]+1:now[1]+2] == "#":
    posQ.append([now[0],now[1]+1])
if field[now[0]+1][now[1]:now[1]+1] == "#":
    posQ.append([now[0]+1,now[1]])

now = posQ[len(posQ)-1]

if field[now[0]][now[1]+1:now[1]+2] == "#":
    posQ.append([now[0],now[1]+1])
if field[now[0]+1][now[1]:now[1]+1] == "#":
    posQ.append([now[0]+1,now[1]])


"""

#print (posQ)
#print (len(posQ))
if (len(posQ)!=H+W-1):
    print("Impossible")
else:
    if (count>len(posQ)):
        print("Impossible")
    else:
        print("Possible")

Submission status: Accepted

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

sx, sy = 0, 0
gx, gy = h - 1, w - 1
nxt = deque()
nxt.appendleft([sx, sy])

for i in range(h - 1):
    count = 0
    check = 0
    count2 = 0
    for j in range(w):
        if a[i][j] == "#":
            if a[i][j] == a[i + 1][j]:
                count += 1
                if check == 0:
                    check = 1
                    if count2 > 0:
                        count = 2
                        break
        else:
            if a[i + 1][j] == "#":
              count2 += 1  

    if count > 1:
        nxt.clear()
        break

flag = 0
while len(nxt) > 0:
    tmp = nxt.pop()
    nwx, nwy = tmp[0], tmp[1]
    if nwx == gx and nwy == gy:
        flag = 1
        break
    count = 0
    for i in range(2):
        tmpx = mv[i][0] + nwx
        tmpy = mv[i][1] + nwy
        if tmpy < w and tmpx < h:
            if a[tmpx][tmpy] == '#':
                nxt.appendleft([tmpx, tmpy])
                count += 1
    if count > 1:
        break

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

Submission status: Accepted

Solution code:
# 次のダメパターンがあればImpossibleそれ以外はPossible
#  .#    ##
#  ## or #.

h, w = map(int, input().split())

table = []
for _ in range(h):
    a = input()
    temp = []
    for c in a:
        temp.append(c == '#')
    table.append(temp)

def check():
    for s in table:
        if True in s:
            return False
    return True
    
def solve(y, x):
    if table[y][x] == False:
        return False
    table[y][x] = False
    ret = False
    if y == h - 1 and x == w - 1:
        ret = check()
    else:
        if y < h - 1:
            ret = ret or solve(y + 1, x)
        if x < w - 1:
            ret = ret or solve(y, x + 1)
    table[y][x] = True
    return ret

ans = 'Possible' if solve(0, 0) else 'Impossible'

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, raw_input().split())
A = list()
for _ in range(H):
    A.append(list(raw_input()))

B = list()
for h in range(H):
    B.append(list())
    for w in range(W):
        B[h].append('.')

i = 0
j = 0
ret = "Impossible"
while True:
    B[i][j] = '#'
    # down and right
    if i+1 < H and j+1 < W:
        if A[i][j+1] == "#" and A[i+1][j] == ".":
            # right
            j += 1
        elif A[i][j+1] == "." and A[i+1][j] == "#":
            # down
            i += 1
        else:
            break
    # right only
    elif i+1 == H and j+1 < W:
        if A[i][j+1] == "#":
            # right
            j += 1
        else:
            break
    # down only
    elif i+1 < H and j+1 == W:
        if A[i+1][j] == "#":
            # down
            i += 1
        else:
            break
    elif i+1 == H and j+1 == W:
        if A == B:
            ret = "Possible"
        break
print ret

Submission status: Accepted

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

A = [input() for i in range(H)]

prevend=0
for i in range(H):
    for j in range(W):
        if A[i][j] == '#' and j < prevend:
            print ("Impossible")
            exit()
        elif j>0 and A[i][j-1] == '#' and A[i][j] == '.':
            prevend = j-1
            break
        elif j==W-1:
            prevend =W-1

prevend = 0
for j in range(W):
    for i in range(H):
        if A[i][j] == '#' and i < prevend:
            print ("Impossible")
            exit()
        elif i>0 and A[i-1][j] == '#' and A[i][j] == '.':
            prevend = i-1
            break
        elif i==H-1:
            prevend =H-1


print("Possible")

Submission status: Accepted

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

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

possible = True
prev_min_hash = W

for h in range(H-1, -1, -1):
    max_hash = 0
    for w in range(W):
        if array[h][w] == "#":
            max_hash = w

    if max_hash > prev_min_hash:
        possible = False
        break

    for w in range(W-1, -1, -1):
        if array[h][w] == "#":
            prev_min_hash = w

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

Submission status: Accepted

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

m = []
m.append('.'*(W+2))
for i in range(H):
    m.append('.'+input()+'.')

m.append('.'*(W+2))

x, y = 1, 1

while not(x==W and y==H):
    if(m[y][x+1]==m[y+1][x] or m[y][x-1]==m[y-1][x]=='#'):
        print('Impossible')
        exit()
    if(m[y][x+1]=='#'):
        x+=1
    elif(m[y+1][x]=='#'):
        y+=1


print('Impossible' if m[y-1][x]==m[y][x-1]=='#' else 'Possible')

Submission status: Accepted

Solution code:
import sys

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

board = [[-1 for i in range(w)] for j in range(h)]
board[0][0] = 0

movecol = [1, 0]
moverow = [0, 1]
count = 0

# #の数を数える
for i in range(w):
    for j in range(h):
        if(a[j][i] == "#"):
            count += 1

def dfs(x, y, n):
    #これ以上進めない
    if(x >= w or y >= h or a[y][x] == "."):
        flag = -1
        return
    #右下についた
    if(x == w-1 and y == h-1):
        if(n == count):
            print("Possible")
            sys.exit()
        else:
            flag = -1

    for i in range(2):
        nextx = x + movecol[i]
        nexty = y + moverow[i]
        dfs(nextx, nexty, n+1)

dfs(0, 0, 1)
print("Impossible")

Submission status: Accepted

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

H, W = map(int, input().split())
F = [list(input()) for x in range(H)]
ans = True
px = py = 0
while py < H-1 or px < W-1:
    if py<H-1 and F[py+1][px]=='#':
        if (px<W-1 and F[py][px+1]=='#') or (px>0 and F[py+1][px-1]=='#'):
            ans = False
            break
        py += 1
    elif px<W-1 and F[py][px+1]=='#':
        if py>0 and F[py-1][px+1]=='#':
            ans = False
            break
        px += 1
    else:
        ans = False
        break
print('Possible' if ans else 'Impossible')

Submission status: Accepted

Solution code:
import sys

IMPOSSIBLE = 'Impossible'
POSSIBLE = 'Possible'

def solve():
    H, W = map(int, sys.stdin.readline().split())
    lines = list(map(lambda s: s.rstrip(), sys.stdin.readlines()))
    maxs = []
    mins = []
    for line in lines:
        m = -1
        for i, w in enumerate(line):
            if w == '#':
                m = i
        maxs.append(m)
        m = len(line)
        for i, w in reversed(list(enumerate(line))):
            if w == '#':
                m = i
        mins.append(m)

    for i, (min, max) in enumerate(zip(mins, maxs)):
        if '.' in lines[i][min:max+1]:
            return IMPOSSIBLE

    for min, max in zip(mins[1:], maxs):
        if min != max:
            return IMPOSSIBLE

    return POSSIBLE

print(solve())

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

(H, W) = reads()
A = []

for _ in range(H):
  A.append(input()+".")
A.append("." * (W+1))

walk = [(0, 0)]

for i in range(H + W - 2):
  (y, x) = walk[-1]
  if A[y][x+1] == "#":
      walk.append((y, x+1))
  elif A[y+1][x] == "#":
      walk.append((y+1, x))
  else:
    print("Impossible"); exit()

if all(A[y][x] == "." for y in range(H) for x in range(W) if not (y, x) in walk):
  print("Possible")
else:
  print("Impossible")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        if g[y][x]=="#":
            return True
    return False

def dfs(y,x):
    dx=(0,1)
    dy=(1,0)
    if y==h-1 and x==w-1:
        return True
    for i in xrange(2):
        nxy=y+dy[i]
        nxx=x+dx[i]
        if check(nxy,nxx) and not visited[nxy][nxx]:
            visited[nxy][nxx]=True
            if dfs(nxy,nxx):
                return True
            visited[nxy][nxx]=False
    return False

h,w=map(int,raw_input().split())
g=[raw_input() for _ in xrange(h)]
visited=[[False]*w for _ in xrange(h)]
visited[0][0]=True
if not dfs(0,0):
    print("Impossible")
    exit()
for i in xrange(h):
    for j in xrange(w):
        if g[i][j]=="#" and not visited[i][j]:
            print("Impossible")
            exit()
print("Possible")

Submission status: Accepted

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

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        h, w = map(int, input().split())
        a = []
        for i in range(h):
            a.append(list(input()))
        # print(h)
        # print(w)
        # print(a)

        hash = []
        for i in range(h):
            for j in range(w):
                if a[i][j] == '#':
                    hash.append((i, j))
        # print(hash)
                
        queue = [(0, 0, [(0, 0)])]
        flag = False
        while queue:
            # print(queue)
            i, j, hist = queue.pop(0)
            if (i, j) == (h - 1, w - 1) and a[i][j] == '#' and hist == hash:
                flag = True
                break
            else:
                if i + 1 < h and a[i+1][j] == '#':
                    queue.append((i + 1, j, hist + [(i + 1, j)]))
                if j + 1 < w and a[i][j+1] == '#':
                    queue.append((i, j + 1, hist + [(i, j + 1)]))
        if flag:
            print('Possible')
        else:
            print('Impossible')
        
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Submission status: Accepted

Solution code:
import sys

if __name__ == '__main__':
    H, W = (int(i) for i in input().split())
    arr = input()
    index = arr.rfind("#")
    for i in range(H-1):
        arr = input()
        if arr.find("#") != index:
            print("Impossible")
            sys.exit()

        if arr.rfind("#") == (W - 1) and index == (W - 1) and arr.find("#") != (W - 1):
            print("Impossible")
            sys.exit()

        index = arr.rfind("#")

    print("Possible")