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:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

def io_generator():
	return input()

#+++++++++++++++++++

def ll2l(a_list):
	ret=[]
	for i, v in enumerate(a_list):
		if i == 0 or ret[-1][0] != v:
			ret.append([v,1])
		else: #if ret[-1][0] == v:
			ret[-1][1] += 1
	return ret
		

def main(io):
	a, b = map(int, io().split())
	end_pos=0
	ok='Possible'
	ng='Impossible'
	for i in range(a):
		l = list(io())[:b]
		rr=ll2l(l)
		#print(rr)
		if len(rr) == 0:
			return ng
		elif len(rr) >= 4:
			return ng
		elif len(rr)==1 and rr[0][0] == '.':
			return ng
		elif len(rr)==1:
			st=0
			end = rr[0][1]-1
		elif len(rr) == 2 and rr[0][0]=='.':
			st = rr[0][1]
			end = st + rr[1][1]-1
		elif len(rr) == 2 and rr[0][0]=='#':
			st = 0
			end = rr[0][1] - 1
		elif len(rr) == 3 and rr[0][0]=='#':
			return ng
		else:
			st=rr[0][1]
			end=st + rr[1][1]-1
		#print(st,end)
		if end_pos != st:
			return ng
		end_pos = end
		
	if end_pos==b-1:
		return ok
	return ng
	
#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

Submission status: Accepted

Solution code:
import re

pattern = re.compile('^(?:\.*)(#+)(?:\.*)$')

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

c = 0
for row in board:
    result = pattern.match(row)
    if result == None or result.start(1) != c:
        print("Impossible")
        exit()
    else:
        c = result.end(1) - 1

print("Possible")

Submission status: Accepted

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

currentNode = [0, 0]
visited = [["." for w in range(W)] for h in range(H)]
search = [(0, 1), (1, 0)]

while currentNode != [H-1, W-1]:
    visited[currentNode[0]][currentNode[1]] = "#"
    tovisit = []
    for s in search:
        nexth, nextw = currentNode[0] + s[0], currentNode[1] + s[1]
        if 0 <= nexth <= H-1 and 0 <= nextw <= W-1:
            if A[nexth][nextw] == "#" and visited[nexth][nextw] == ".":
                tovisit.append([nexth, nextw])
    if len(tovisit) == 1:
        currentNode = tovisit[0]
    else:
        print("Impossible")
        break
else:
    visited[currentNode[0]][currentNode[1]] = "#"
    flag = True
    for h in range(H):
        for w in range(W):
            if A[h][w] != visited[h][w]:
                flag = False
                break
        if not flag:
            print("Impossible")
            break
    else: print("Possible")

Submission status: Accepted

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

flag = 0
for i in range(H):
    tmp = []
    for j,k in enumerate(li[i]):
        if k == '#':
            tmp.append(j)
    if i != 0 and p != tmp[0]:
        flag = 1
        break
    p = tmp[-1]

print(['Possible', 'Impossible'][flag])

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
a = 0
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            a += 1
h = 0
w = 0
d = 0
fh = False
fw = False
while True:
    if h == H-1 and w == W-1:
        break
    
    if h == H-1:
        fh = True
    if w == W-1:
        fw = True
        
    if h < H-1:
        if A[h+1][w] == '#':
            h += 1
            d += 1
        elif fw:
            break
    if w < W-1:
        if A[h][w+1] == '#':
            w += 1
            d += 1
        elif fh:
            break
    
if a == d+1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

pos = [0, 0]
num = 1
while True:
    if pos == [H - 1, W - 1]:
        total = sum(map(lambda A: A.count("#"), A_s))
        ans = total == num
        break
    h, w = pos
    if h != H - 1 and A_s[h + 1][w] == "#":
        pos = [h + 1, w]
        num += 1
        continue
    if w != W - 1 and A_s[h][w + 1] == "#":
        pos = [h, w + 1]
        num += 1
        continue
    ans = False
    break

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a,b=0,0
ans="Possible"
for y in range(h):
  m=input()
  a=m.find("#")
  if a<b:
    ans="Impossible"
    break
  b=m.rfind("#")
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
amap = ['.' * (w + 2)]
for _ in range(h):
  amap.append('.' + input().strip() + '.')
amap.append('.' * (w + 2))

x, y = 1, 1
is_one = True
while x != w or y != h:
  if x == 1 and y == 1 and amap[y][x] != '#':
    break
  c = 0
  if amap[y][x+1] == '#':
    c += 1
  if amap[y][x-1] == '#':
    c += 1
  if amap[y+1][x] == '#':
    c += 1
  if amap[y-1][x] == '#':
    c += 1

  if c != 1:
    break
  else:
    amap[y] = amap[y][:x] + '.' + amap[y][x+1:]
    if amap[y][x+1] == '#':
      x += 1
    elif amap[y+1][x] == '#':
      y += 1
    elif amap[y][x-1] == '#':
      break
    elif amap[y-1][x] == '#':
      break

if x == w or y == h:
  c = 0
  for a in amap:
    c += a.count('#')
  if c == 1:
    print('Possible')
  else:
    print('Impossible')
else:
  print('Impossible')

Submission status: Accepted

Solution code:
from itertools import product

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
tmpH = -1
tmpW = -1
flag = True

for i, j in product(range(H), range(W)):
    if A[i][j] == "#":
        if i < tmpH or j < tmpW:
            flag = False
            break
        else:
            tmpH = i
            tmpW = j

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a,b,*c=open(0).read().split()
if int(a)+int(b)-1==sum(i.count("#") for i in c):
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
#AGC007 A
'''
問題
縦H行で横W列の盤面がある
コマははじめ左上隅のマスに置かれており，右下隅に移動した
駒は1マスずつ上下左右に動ける
駒が通ったことのあるマスが提示されるので，駒が常に右または下にしか動いていなかったどうか判定せよ
ただし通ったことのあるマスは'#',一度も通らなかったマスは'.'で与えられる

考察
各行0,1,...,i,...,H-1に対して'#'のマスが存在する範囲を[ai,bi]とする。ただし0<=ai<=bi<=W-1
このとき各0,1,...,j,...,H-2について b_j == a_(j+1) であればよい
'''

import re

H,W = map(int,input().split(' '))
A = []

ans = ''
answers = ('Possible','Impossible')

r = re.compile(r'\.*#+\.*')

for i in range(H):
	s = input()
	if len(r.findall(s)) == 1:
		A.append(s)
	else:
		#'#'が2箇所以上にわかれていたらその時点でアウト
		ans = answers[1]
		break

if ans == '':
	for i in range(H-1):
		if A[i].rfind('#') == A[i+1].find('#'):
			continue
		else:
			ans = answers[1]
			break

if ans == '':
	ans = answers[0]

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
num = []
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] =='#':
            num.append(j+1)
            
for i in range(len(num)-1):
    if num[i] == num[i+1] or num[i]+1 == num[i+1]:
        continue
    else:
        print('Impossible')
        exit()
print('Possible')

Submission status: Accepted

Solution code:
from collections import deque
h,w=[int(i) for i in input().split()]
a=[[i for i in input()] for _ in range(h)]
right_count=sum([sum([1 for j in range(w) if a[i][j]=="#"]) for i in range(h)])
pattern=[(1,0),(0,1)]
queue=deque([(0,0)])
def bfs():
    cnt=1
    while queue:
        (x,y)=queue.popleft()
        if (x,y)==(w-1,h-1):
            return cnt
        around=False
        for i,j in pattern:
            if y+i<h and x+j<w:
                if a[y+i][x+j]=="#":
                    queue.append((x+j,y+i))
                    around=True
                    cnt+=1
        if around==False:
            return False
print("Possible" if bfs()==right_count else "Impossible")

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def chk(r, c):
    cnt_in, cnt_out = 0, 0
    if (r, c) == (0, 0): cnt_in += 1
    if (r, c) == (H - 1, W - 1): cnt_out += 1
    if r - 1 >= 0:
        if a[r - 1][c] == '#': cnt_in += 1
    if r + 1 < H:
        if a[r + 1][c] == '#': cnt_out += 1
    if c - 1 >= 0:
        if a[r][c - 1] == '#': cnt_in += 1
    if c + 1 < W:
        if a[r][c + 1] == '#': cnt_out += 1
    return cnt_in == 1 and cnt_out == 1


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

bl = True
for r in range(H):
    for c in range(W):
        if a[r][c] == '#':
            if not chk(r, c):
                bl = False
                break
    else:
        continue
    break

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

Submission status: Accepted

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

count = 0

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

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

Submission status: Accepted

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

cnt = 0
for _ in range(H):
  cnt += input().count("#")
ans = "Impossible"
if(cnt == H+W-1):
  ans = "Possible"
print(ans)

Submission status: Accepted

Solution code:
t=open(0).read();print('I mPp'[t.count('#')<int(t[0])+int(t[2])::2]+'ossible')

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
A = [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 == w + h - 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

flag = 0
for a in A:
    X = a.split('.')
    cnt = 0
    for x in X:
        if '#' in x:
            cnt += 1
    if cnt > 1:
        flag = 1
        
if flag:
    ans = 'Impossible'
else:
    ans = 'Possible'
    posi = 0
    for i in range(h):
        B = []
        for j in range(w):
            if A[i][j] == '#':
                B.append(j)
        if B[0] > posi or B[0] < posi:
            ans = 'Impossible'
            break
        else:
            posi = B[-1]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import chain
h, w = map(int, input().split())
As = list(chain.from_iterable([list(input()) for i in range(h)]))
print("Possible" if As.count("#") == h + w - 1 else "Impossible")

Submission status: Accepted

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

x,y = 0,0

ans = "Possible"

while True:
    cnt = 0
    tmpX,tmpY = x,y
    # 上か左が"#" -> error
    if (x > 0 and As[y][x-1] == "#") or (y > 0 and As[y-1][x] == "#"):
        ans = "Impossible"
        break
    
    # 右も下も"#" -> error
    if x < w - 1 and As[y][x+1] == "#" and y < h - 1 and As[y+1][x] == "#":
        ans = "Impossible"
        break
    
    # 右に移動
    if x < w - 1 and As[y][x+1] == "#":
        As[y][x] = "."
        x += 1
    # 左に移動
    if y < h - 1 and As[y+1][x] == "#":
        As[y][x] = "."
        y += 1
        
    # 右下に到着
    if x == w - 1 and y == h - 1:
        As[y][x] = "."
        break

    # 移動していない
    if x == tmpX and y == tmpY:
        ans = "Impossible"
        break
        
for A in As:
    if "#" in A:
        ans = "Impossible"

print(ans)

Submission status: Accepted

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

count = 0
for i in range(H):
  for j in range(W):
    if L[i][j] == '#':
      count += 1
      
if count == W + H - 1:
  print('Possible')
else:
  print('Impossible')

Submission status: Accepted

Solution code:
input_nums = [int(c) for c in input().split(" ")]
h = input_nums[0]
w = input_nums[1]

count = 0

for i in range(h):
	for c in input():
		if c == "#":
			count += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    h, w = LI()
    B = [SI() + '.' for _ in range(h)]
    B.append('.' * w)

    for y in range(h):
        for x in range(w):
            if B[y][x] == '.':
                continue
                
            # |# . .
            # |# # #
            # |# . #
            if B[y][x + 1] == '#' and B[y + 1][x] == '#':
                return 'Impossible'
            
            # |. . .
            # |. # .
            # |# # .
            # |. # #
            if min(y, x) != 0:
                if B[y - 1][x] == '.' and B[y][x - 1] == '.':
                    return 'Impossible'

    return 'Possible'


print(main())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
aaa = [input().replace('#','1').replace('.','0') for _ in range(h)]

ans = 'Impossible'
for i in range(h-1):
    # check up-down
    updown = bin(int(aaa[i],2) & int(aaa[i+1],2))
    if updown.count('1') >1:
        # print('updown')
        break
    # check left move
    # print(aaa[i+1], aaa[i+1].index('1') , aaa[i], aaa[i].rindex('1'))
    if aaa[i+1].index('1') < aaa[i].rindex('1'):
    # int(aaa[i+1]) > int(aaa[i]):
        # print('left')
        break
else:
    ans = 'Possible'
print(ans)

# for a in aaa:
#     print(a)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = []
nS = 0
for i in range(H):
    A.append(list(input()))
for a in A: nS += a.count('#')

def dfs(i,j):
    if (i,j) == (H-1,W-1): return True
    if i >= H or j >= W or A[i][j] == '.': return
    return dfs(i+1,j) or dfs(i,j+1)

if dfs(0,0) and nS == (H+W-1): print('Possible')
else: print('Impossible')

Submission status: Accepted

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

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

Submission status: Accepted

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

l = 1
x = 0
for i in range(H):
    while x<W-1 and A[i][x+1] == '#':
        x += 1
        l += 1
    if i+1<H and A[i+1][x] == '.':
        print('Impossible')
        exit()
    elif i+1<H:
        l += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

memo = [[0] * w for _ in range(h)]

i = 0
j = 0
memo[i][j] = 1
while i < h-1 and j < w-1:
    if a[i+1][j] == "#" and a[i][j+1] == "#":
        print("Impossible")
        exit()
    elif a[i+1][j] == "#":
        i += 1
        memo[i][j] = 1
    elif a[i][j+1] == "#":
        j += 1
        memo[i][j] = 1
    else:
        print("Impossible")
        exit()

if i == h-1:
    while j < w-1:
        if a[i][j+1] == ".":
            print("Impossible")
            exit()
        j += 1
        memo[i][j] = 1
else:
    while i < h-1:
        if a[i+1][j] == ".":
            print("Impossible")
            exit()
        i += 1
        memo[i][j] = 1

for i in range(h):
    for j in range(w):
        if a[i][j] == "#" and memo[i][j] == 0:
            print("Impossible")
            exit()

print("Possible")

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

H, W = inpl()
A = []
for _ in range(H):
    A.append([x=="#" for x in input()] + [False])

A.append([False] * (W+1))

Q = [[0, 0]]
visited = [[False]*(W+1) for _ in range(H+1)]
visited[0][0] = True

while Q:
    h, w = Q.pop()
    for dh, dw in [[0, 1], [1, 0]]:
        nh, nw = h+dh, w+dw
        if A[nh][nw] and not visited[nh][nw]:
            visited[nh][nw] = True
            Q.append([nh, nw])

plength = sum([sum(a) for a in A])

if plength == (H+W-1) and visited[H-1][W-1]:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
c = []
for i in range(h):#h:高さ
    c.append([str(m) for m in list(input())])
pcnt = 0
qcnt = 0
for i in range(h):
    for j in range(w):
        if c[i][j] == "#":
            for p in range(i + 1, h):
                if c[p][j] == "#":
                    pcnt = 1
            for q in range(j + 1, w):
                if c[i][q] == "#":
                    qcnt = 1
            if pcnt == 1 and qcnt == 1:
                print("Impossible")
                exit()
            pcnt = 0
            qcnt = 0
print("Possible")

Submission status: Accepted

Solution code:
# 最短ルートでいける、左上開始、右上終了ゆえに#の数数えればいけるぞ
H, W = map(int, input().split(" "))
A = [input() for _ in range(H)]

print(["Impossible", "Possible"]["".join(A).count("#")==H+W-1])

Submission status: Accepted

Solution code:
h,w = (int(i) for i in input().split())
a = []
ct = 0
for i in range(h):
  s = input()
  a.append(s)
  ct += s.count('#')
queue = [(0,0)]
check = []
if a[0][0] == '.':
 print('Impossible')
 exit()
while queue != []:
 i,j = queue[0]
 queue.pop(0)
 if not (i,j) in check:
  if i+1 < h:
   if a[i+1][j] =='#':
    queue.append((i+1,j))
  if j+1 < w: 
   if a[i][j+1] =='#':
    queue.append((i,j+1))
  check.append((i,j))
  if i+1 < h and j+1 < w: 
    if a[i+1][j] =='#' and  a[i][j+1] =='#':
      break
  if queue != []:
   if queue[0] == (h-1,w-1) and a[h-1][w-1] == '#':
     if h+w-1 == ct:
      print('Possible')
      exit()
print('Impossible')

Submission status: Accepted

Solution code:

from collections import deque
H, W = map(int, input().split())
sy,sx = 1,1
gy,gx = H,W
sy-=1
sx-=1
gy-=1
gx-=1
con = [[1,0],[0,1],[-1,0],[0,-1]]
m=[]
d = [[0]*W for _ in range(H)]
for i in range(H):
    a= input()
    m.append(a)
q = deque()
q.append((sy,sx))
d[sy][sx] = 1
s = 0
while len(q)>0:
    y,x = q.popleft()
    if y == gy and x == gx:
        break
    for dx,dy in con:
        if  y+dy>=0 and x+dx >= 0 and y+dy < H and x+dx < W:
            if d[y+dy][x+dx] == 0 and m[y+dy][x+dx] =="#":
                q.append((y+dy,x+dx))
                d[y+dy][x+dx]+=d[y][x]+1
for i in range(H):
    for j in range(W):
        if m[i][j] == "#":s+=1
if H+W < d[gy][gx] or s > d[gy][gx]:
    print("Impossible")
else:print("Possible")

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

Submission status: Accepted

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

Submission status: Accepted

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W = MAP()

cnt = 0
for i in range(H):
    row = input()
    cnt += row.count('#')

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
tmp = 0
for _ in range(h):
    tmp += input().count('#')
if tmp == 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 = a + input()
if a.count("#") == h + w -1:
  print("Possible")
else:
  print("Impossible")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def dask(x,y):
  if(a[x][y]=="."):
    return [0,0,False]
  if(a[x+1][y]=="#"):
    for i in range(w):
      if(i>y and a[x][i]=="#"):
        return [0,0,False]
    return [x+1,y,True]
  if(a[x][y+1]=="#"):
    for i in range(h):
      if(i>x and a[i][y]=="#"):
        return [0,0,False]
    return [x,y+1,True]
  return [0,0,False]
h,w=map(int,input().split())
a=[input()+"." for _ in[0]*h]+["."*(w+1)]
x=0
y=0
fl=True
while(fl and (x<h-1 or y<w-1)):
  x,y,fl=dask(x,y)
print("Possible" if fl else "Impossible")

Submission status: Accepted

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

Submission status: Accepted

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

A = []

for i in range(H):
    tmp = input()
    A.append(tmp)
    
c = 0
    
for i in range(H):
    for j in range(W):
        if A[i][j]=='#':
            c = c+1
            
if not c==H+W-1:
    print('Impossible')
else:
    print('Possible')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

x = 0
y = 0

counts = 0
for item in inputs:
    counts += item.count('#')

if counts != (H + W - 1):
    ans = 'Impossible'
else:
    for _ in range(H + W - 2):
        if x + 1 < W and inputs[y][x + 1] == '#':
            x += 1
        elif y + 1 < H and inputs[y + 1][x] == '#':
            y += 1
    ans = 'Possible' if y == H - 1 and x == W - 1 else 'Impossible'

print(ans)

Submission status: Accepted

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

y = 0
x = 0

goal_y = H - 1
goal_x = W - 1

counts = 0
for item in inputs:
    counts += item.count('#')

if counts != (H + W - 1):
    print('Impossible')
else:
    for _ in range(H + W - 2):
        if x + 1 < W and inputs[y][x + 1] == '#':
            x += 1
        elif y + 1 < H and inputs[y + 1][x] == '#':
            y += 1
    print('Possible' if y == goal_y and x == goal_x else 'Impossible')

Submission status: Accepted

Solution code:
from itertools import combinations
H, W = map( int, input().split())
A = [ list( input()) for _ in range(H)]
for X in combinations([i for i in range(H+W-2)], H-1):
    I = [0]*(H+W-2)
    for i in range(H-1):
        I[X[i]] = 1
    B = [ ["."]*W for _ in range(H)]
    B[0][0] = "#"
    nowx = 0
    nowy = 0
    for i in range(H+W-2):
        if I[i] == 1:
            if A[nowx+1][nowy] == "#":
                nowx += 1
        else:
            if A[nowx][nowy+1] == "#":
                nowy += 1
        B[nowx][nowy] = "#"
    if nowx == H-1 and nowy == W-1:
        break
ans = "Possible"
for i in range(H):
    for j in range(W):
        if not A[i][j] == B[i][j]:
            ans = "Impossible"

print(ans)

Submission status: Accepted

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

x = y = p = 0
while x < W-1 or y < H-1:
    if x < W-1 and src[y][x+1] == '#':
        p += 1
        x += 1
    elif y < H-1 and src[y+1][x] == '#':
        p += 1
        y += 1
    else:
        print('Impossible')
        exit()

c = 0
for row in src:
    c += row.count('#')
print('Possible' if p+1==c else 'Impossible')

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h,w = li()
grid = [lc() for _ in range(h)]

black = 0
for row in grid:
    black += row.count("#")
                       
print("Possible") if black == h+w-1 else print("Impossible")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
route = ""
for _ in range(H):
    route += input()

print("Possible" if route.count("#")==(H+W-1) else "Impossible")

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W] = [int(input_raw[0]), int(input_raw[1])]
    field = []
    for i in range(H):
        input_raw = read_func().strip()
        field.append(input_raw)

    pre_last = -1
    for i in range(H):
        first = -1
        last = -1
        for j in range(W):
            if field[i][j] == '#':
                if first == -1:
                    first = j
                last = j
        if pre_last > first:
            print "Impossible"
            return
        pre_last = last

    pre_last = -1
    for j in range(W):
        first = -1
        last = -1
        for i in range(H):
            if field[i][j] == '#':
                if first == -1:
                    first = j
                last = j
        if pre_last > first:
            print "Impossible"
            return
        pre_last = last

    print "Possible"

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

cnt = 0
for i in range(H):
    s = input()

    cnt += s.count('#')

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

Submission status: Accepted

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


def main():
    """Function."""
    h, w = map(int, input().split())

    counter = 0
    for _ in range(h):
        s = str(input())
        counter += s.count("#")

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


if __name__ == "__main__":
    main()