Problem:


Score : 200 points

Problem Statement

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

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

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

Constraints

2 \leq H, W \leq 8

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

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

Input

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

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

Output

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

Sample Input 1

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

Sample Output 1

Possible

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

Sample Input 2

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

Sample Output 2

Impossible

Sample Input 3

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

Sample Output 3

Impossible



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


Sample output:
Possible

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
v=[[1]*w for _ in range(h)]
q=[(0,0)]
dxy=((-1,0),(0,-1),(1,0),(0,1))
while q:
  x,y=q.pop()
  v[x][y]=0
  cnt=0
  for dx,dy in dxy:
    nx=x+dx
    ny=y+dy
    if not(0<=nx<h and 0<=ny<w) or s[nx][ny]=='.':continue
    elif v[nx][ny] and ((dx==-1 or dy==-1)or cnt):
      print('Impossible')
      exit()
    elif v[nx][ny] :
      q+=[(nx,ny)]
      cnt=1
print(['Possible','Impossible'][v[h-1][w-1]])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = []
flags = []
for _ in range(H):
    A.append(list(input()))
    flags.append([False] * W)
x, y = 0, 0
flags[0][0] = True
while True:
    nx1, ny1 = x + 0, y + 1
    nx2, ny2 = x + 1, y + 0
    if x == W - 1 and y == H - 1:
        break
    if x == W - 1:
        if A[ny1][nx1] == '#':
            x, y = nx1, ny1
        else:
            print('Impossible')
            exit()
    elif y == H - 1:
        if A[ny2][nx2] == '#':
            x, y = nx2, ny2
        else:
            print('Impossible')
            exit()
    else:
        if A[ny1][nx1] == '#' and A[ny2][nx2] == '.':
            x, y = nx1, ny1
        elif A[ny1][nx1] == '.' and A[ny2][nx2] == '#':
            x, y = nx2, ny2
        else:
            print('Impossible')
            exit()
    flags[y][x] = True
# print(*flags, sep='\n')
for x in range(W):
    for y in range(H):
        if A[y][x] == '#' and not flags[y][x]:
            print('Impossible')
            exit()
print('Possible')

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [list('.'+input()+'.') for _ in range(H)]
if sum(A[i].count('#') for i in range(H)) != H + W -1:
    print('Impossible')
    exit()
A.append('.'*(W+2))
A.insert(0, '.'*(W+2))
h, w = 1, 1
for i in range(H+W-2):
    n = []
    for j in [(0,-1), (0,1), (-1,0), (1,0)]:
        if A[h+j[0]][w+j[1]] == '#':
            n.append(j)
    if i == 0 and len(n) != 1 or i > 0 and len(n) != 2:
        print('Impossible')
        exit()
    if i == 0 or hp != h+n[0][0] or wp != w+n[0][1]:
        j = 0
    else:
        j = 1
    hp, wp = h, w
    h, w = h+n[j][0], w+n[j][1]
if h == H and w == W:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

g = []
cnt = 0
for _ in range(h):
    a = input() + "?"
    cnt += a.count("#")
    g.append(list(a))

if cnt != h+w-1:
    print("Impossible")
    exit()

g.append(["?"]*w)

y, x = 0, 0

for _ in range(h+w-2):
    if g[y+1][x] == "#" and g[y][x+1] != "#":
        y += 1
    elif g[y][x+1] == "#" and g[y+1][x] != "#":
        x += 1
    else:
        print("Impossible")
        exit()
print("Possible")

Submission status: Accepted

Solution code:
import sys
import queue
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = queue.Queue()
d.put([0, 0, 0])
vals = set()

while not d.empty():
    now = d.get()
    a[now[0]][now[1]] = '.'
    if now[2] in vals:
        print('Impossible')
        sys.exit()
    else:
        vals.add(now[2])
        
    if now[0] == h-1 and now[1] == w-1:
        a1 = [['.']*w for _ in range(h)]
        if a == a1:
            print('Possible')
        else:
            print('Impossible')
        sys.exit()
    else:
        if now[0]+1 < h:
            if a[now[0]+1][now[1]] == '#':
                d.put([now[0]+1, now[1], now[2]+1])
        if now[1]+1 < w:
            if a[now[0]][now[1]+1] == '#':
                d.put([now[0], now[1]+1, now[2]+1])        
print('Impossible')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 02
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


h, w = LI()
a = []
for _ in range(h):
    a.append(list(S()))

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())

count = 0
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == '#':
            a[j] = 1
        else:
            a[j] = 0
    count += sum(a)
    
if count == w + h - 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
table=[]
for _ in range(h):
  a=input()
  b=[]
  for i in range(w):
    if a[i]=='#':
      b.append(1)
    else:
      b.append(0)
  table.append(b)
ans=0
for i in range(h):
  ans+=sum(table[i])
if ans==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()) + ["."])
l[-1][w-1] = "g"
l.append(["."]*(w+1))

def dfs(x, y):
    if x == w or y == h or l[y][x] == ".":
        return
    elif l[y][x] == "g":
        print("Possible")
        exit()
    else:
        dfs(x+1, y)
        dfs(x, y+1)

cnt = 0
for i in l:
    for j in i:
        if j == "#":
            cnt += 1

if cnt == h + w - 2:
    dfs(0, 0)
print("Impossible")

Submission status: Accepted

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

Submission status: Accepted

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

cnt = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '#':
            cnt += 1

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

Submission status: Accepted

Solution code:
# def dfs(y, x):
#     if gridgraph[y+1][x] == "#" and y+1 != H:
#         visited[y+1][x] = True
#         dfs(y+1, x)
#     elif gridgraph[y][x+1] == "#" and x+1 != W:
#         visited[y][x+1] = True
#         dfs(y, x+1)
#     elif y == H-1 and x == W-1:
#         return

from collections import deque

H, W = map(int, input().split())
gridgraph = [input() for _ in range(H)]
# 移動経路を右or下のみに限定して，目的地に着いたかどうか判定する, 幅優先探索で右と下が同時に#なら終わりという制約でもいいかも
q = deque()
q.append([0, 0])
visited = [[False]*W for _ in range(H)]
adjacents = [[1, 0], [0, 1]]
while len(q):
    ny, nx = q.popleft()
    # print(ny, nx)
    visited[ny][nx] = True
    if (ny+1 != H and gridgraph[ny+1][nx] == "#") and (nx+1 != W and gridgraph[ny][nx+1] == "#"):
        break
    if (ny+1 != H and gridgraph[ny+1][nx] != "#") and (nx+1 != W and gridgraph[ny][nx+1] != "#"):
        break
    for dy, dx in adjacents:
        if ny+dy == H or nx+dx == W:
            continue
        if gridgraph[ny+dy][nx+dx] == "#":
            q.append([ny+dy, nx+dx])
ans = True
for i in range(H):
    for j in range(W):
        if visited[i][j] == False and gridgraph[i][j] == "#":
            ans = False

if ny == H-1 and nx == W-1 and ans:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
import sys

# A - Shik and Stone
def go(grid, i, j):
	global H
	global W
	global routes

	if i < H and j < W:
		import copy
		c = copy.deepcopy(grid)

		c[i][j] = '#'

		if i == H - 1 and j == W - 1:
			routes.append(c)
		else:
			go(c, i + 1, j)
			go(c, i, j + 1)


def merge_grid(grid):
	s = ''

	for line in grid:
		s += ''.join(line)

	return s


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

for _ in range(H):
	A.append(input())
	grid.append(['.'] * W)

routes = []
go(grid, 0, 0)

possibles = set()

for route in routes:
	possibles.add(merge_grid(route))

if merge_grid(A) in possibles:
	print('Possible')
else:
	print('Impossible')

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
c = [0]*(h+2)

r = 0

for i in range(1,h+1):
    c[i] = [0] + list(input()) + [0]
    r += c[i].count("#")
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

x,y = 1,1

q = 0
ans = 1
while 1:
    if x == h and y == w:
        break
    
    s = 0
    t = 0
    if c[x+1][y] == "#":
        s = 1
    if c[x][y+1] == "#":
        t = 1
            
    if s == 1 and t == 1:
        ans = 0
        break
    elif s == 0 and t == 0:
        ans = 0
        break
    elif s == 1:
        x += 1
        q += 1
    else:
        y += 1
        q += 1
if q + 1 != r:
    ans = 0

print(["Impossible","Possible"][ans])

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
grid = []
X = [['.']*W for _ in range(H)]
for i in range(H):
    grid.append(list(input()))
cur = 0
for i in range(H):
    if grid[i][cur] == '.':
        print('Impossible')
        exit()
    grid[i][cur] = '.'
    if cur != W-1:
        while grid[i][cur+1] == '#':
            grid[i][cur+1] = '.'
            cur += 1
            if cur == W-1:
                break

if grid != X:
    print('Impossible')
else:
    print('Possible')

Submission status: Accepted

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

x = 0
y = 0

while True:
    c = []
    neighbours = 0
    if x != w-1:
        c.append([x+1, y, 1])
    if y != h-1:
        c.append([x, y+1, 3])

    for coords in c:
        if grid[coords[1]][coords[0]] == "#":
            neighbours += 1
            x2 = coords[0]
            y2 = coords[1]

    if neighbours != 1 and not (x == w-1 and y == h-1):
        print("Impossible")
        break

    c = []
    neighbours = 0
    if x != 0:
        c.append([x-1, y, 0])
    if y != 0:
        c.append([x, y-1, 2])

    for coords in c:
        if grid[coords[1]][coords[0]] == "#":
            neighbours += 1

    if neighbours > 1:
        print("Impossible")
        break

    if x == w-1 and y == h-1:
        print("Possible")
        break

    x = x2
    y = y2

Submission status: Accepted

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

x = 0
y = 0
while True:
    if l[x][y] == "#":
        l[x][y] = "."
        if y < w-1 and l[x][y+1] == "#":
            y += 1
        elif x < h-1 and l[x+1][y] == "#":
            x += 1
        else:
            break
    else:
        break
for i in l:
    if "#" in i:
        print("Impossible")
        exit()
print("Possible")

Submission status: Accepted

Solution code:
from itertools import combinations
H,W = map(int,input().split())
grid = [0] * H
for i in range(H):
    grid[i] = list(input())
res = 'Impossible'
# 1は右、0は下
move_indexes = [i for i in range(H+W-2)]
# 移動回数W+Hの中からH回縦移動を選ぶ
for y_move in combinations(move_indexes,H-1):
    now_y, now_x = 0,0
    reached = [[0]*W for _ in range(H)]
    reached[0][0] = 1
    for i in range(H+W-2):
        # うまくやれば*1/8にはなる
        if i in y_move:
            now_y += 1
        else:
            now_x += 1
        reached[now_y][now_x] = 1
    can = True
    for i in range(H):
        for j in range(W):
            if (not reached[i][j] and grid[i][j]=='#') or (reached[i][j] and grid[i][j] == '.'):
                can = False
    if can:
        res = 'Possible'
        break

print(res)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
list1 =[]
count = 0
for i in range(H):
  a = list(input())
  list1.append(a)
for i in range(H):
  for j in range(W):
    if list1[i][j] == '#':
      count +=1
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):
    s = input()
    cnt += s.count('#')

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

Submission status: Accepted

Solution code:
import collections, sys

h, w = map(int, input().split())
count = 0
a = []
a.append("." * (w + 2))
for i in range(h):
    temp = input()
    a.append("." + temp + ".")
    count += temp.count("#")
a.append("." * (w + 2))
if count != h + w - 1:
    print("Impossible")
else:
    queue = collections.deque([[1, 1]])
    d = [[1, 0], [0, 1]]
    while queue:
        test = queue.popleft()
        for i in d:
            x = test[0] + i[0]
            y = test[1] + i[1]
            if (x, y) == (w, h):
                print("Possible")
                sys.exit()
            else:
                if a[y][x] == "#":
                    queue.append([x, y])
    else:
        print("Impossible")

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
# A = [['.']+list(input())+['.'] for i in range(H)]
A = [list(input()) for i in range(H)]
flag = True
endi = 0
for i in range(H):
    if A[i].index('#') == endi:
        for j in range(W):
            if A[i][j] == '#':
                endi = j
        continue
    flag = False
    break


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

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
ans='Impossible'
j=0

for i in range(H):
  A=[x for x in input()]
  count=A.count('#')
  if i==0 and A[0]=='.':
    break
  try:
    if i>0 and '#' in A[:j]:
      break
    else:
      if i==0:
        if count!=A[:count].count('#'):
        	break
      elif count!=A[j:j+count].count('#'):
        break
  except:
    j+=(count-1)
    pass
  j+=(count-1)
else:
  ans='Possible'
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque


def main():
    H, W = list(map(int, input().split()))
    A = [list(input()) for _ in range(H)]
    # 「右or下のみ移動可」で深さ優先探索
    # 移動時、該当マスを左上角とする長方形領域以外に未訪問の '#' があったらNG
    # ゴールに到達できなくてもNG
    que = deque()
    que.append((0, 0))
    ok = False
    while len(que) > 0:
        h, w = que.pop()
        A[h][w] = '.'
        if (h, w) == (H - 1, W - 1):
            ok = True
            break
        # 横方向
        next_h, next_w = h, w + 1
        if next_w < W and A[next_h][next_w] == '#':
            exist_unvisited = False
            for hh in range(next_h, H):
                if A[hh][w] == '#':
                    exist_unvisited = True
                    break
            if exist_unvisited:
                break
            que.append((next_h, next_w))
            continue
        # 縦方向
        next_h, next_w = h + 1, w
        if next_h < H and A[next_h][next_w] == '#':
            exist_unvisited = False
            for ww in range(next_w, W):
                if A[h][ww] == '#':
                    exist_unvisited = True
                    break
            if exist_unvisited:
                break
            que.append((next_h, next_w))
            continue
    if ok:
        print('Possible')
    else:
        print('Impossible')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

IsPossible=True
res=[]
for y in range(H):
    left=-1
    right=0
    for x in range(W):
        if A[y][x]=='#':
            if left<0:
                left=x
                right=x
            else:
                if x-right==1:
                    right=x
                else:
                    IsPossible=False
                    break
    res.append((left,right))

for y in range(1,H):
    if res[y-1][1]!=res[y][0]:
        IsPossible=False

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def IL(): return map(int,sys.stdin.readline().rstrip().split())

if __name__=='__main__':
    h,w = IL()
    m = [S() for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if i==h-1 or j==w-1:
                continue
            if m[i][j+1]=='#' and m[i+1][j]=='#':
                print('Impossible')
                exit()
    print('Possible')
    exit()

Submission status: Accepted

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

# from numba import njit

# input = stdin.readline

dxdy = [[1,0],[0,1]]

# @njit
def solve(h,w,board):
  sharp_count = sum(x.count("#") for x in board)
  def dfs(y,x,gy,gx,cnt=1):
    if y == gy and x == gx:
      return cnt

    if not 0 <= y < h or not 0 <= x < w:
      return 0
    if board[y][x] == ".":
      return 0
    return  dfs(y+1,x,gy,gx,cnt+1) + dfs(y,x+1,gy,gx,cnt+1)
  
  return dfs(0,0,h-1,w-1) == sharp_count



def main():
  H,W = map(int,input().split())
  board = [input() for _ in range(H)]
  print("Possible" if solve(H,W,board) else "Impossible")
  return

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[list(input()) for _ in range(H)]
h=0
w=0
ans="Possible"
for i in range(H):
  for j in range(W):
    if A[i][j]=="#":
      if (i==h and j-w<2) or (i-h<2 and j==w):
        h=i
        w=j
      else:
        ans="Impossible"
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]
now = 0
ng = 0
for i in range(h):
    # print(now)
    # 限界まで伸ばせる点を探し、それより先に#がないことを確認
    extended = 0
    if a[i][now] != "#" or "#" in a[i][:now]:
        ng = 1
        # print(i, now)
        break
    for j in range(now, w):
        if not extended:
            if a[i][j] == "#":
                now = j
            else:
                extended = 1
        else:
            if a[i][j] == "#":
                #print(i, j)
                ng = 1
                break
        if i == h - 1 and j == w - 1 and a[i][j] == ".":
            ng = 1
    if ng:
        break
if ng:
    print("Impossible")
else:
    print("Possible")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int, input().split())
lst1 = [list(input()) for i in range(H) ] #迷路データ。２次元リストで格納し、"."と"#"(壁)からなる


def dfs(maze, visited, sh, sw):
    stack = deque([[sh, sw, 0]])
    visited[sh][sw] = 1
    while stack:
        h, w, t = stack.pop()
        if h == H-1 and w == W-1: #ゴールにたどりつけるなら
            return
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #4近傍について探索
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W: #リスト外でないならelif条件へ
                continue
            elif maze[new_h][new_w] != "." and \
                visited[new_h][new_w] == 0: #行ったことがないかつ、壁でないなら
                visited[new_h][new_w] = 1
                stack.append([new_h, new_w, t+1])
    

visited = [[0]*W for _ in range(H)]
dfs(lst1, visited, 0, 0)

flag = 1
for i in range(H):
    for j in range(W):
        if not ((lst1[i][j] == "." and visited[i][j] == 0) \
        or (lst1[i][j] == "#" and visited[i][j] == 1)):
            flag = 0
            break
res = 0
for i in lst1:
    res += i.count("#")

if flag and res == H+W-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
dx=[0,1]
dy=[1,0]
def bfs(x,y):
    que=deque([(x,y)])
    while(que):
        nx,ny=que.popleft()
        seen[nx][ny]=True
        if (nx+1<H-1 and G[nx+1][ny]=='#') and (ny+1<W-1 and G[nx][ny+1]=='#'):
            return False
        elif nx+1<H and G[nx+1][ny]=='#':
            que.append((nx+1,ny))
            continue
        elif ny+1<W and G[nx][ny+1]=='#':
            que.append((nx,ny+1))
            continue
        else:
            if nx==H-1 and ny==W-1:
                return True
            else:
                return False
    return True


memo={}
H,W=map(int,input().split())
G=[list(input()) for i in range(H)]
seen=[[False]*W for i in range(H)]
isok=bfs(0,0)
for i in range(H):
    for j in range(W):
        if G[i][j]=='#' and seen[i][j]==False:
            isok=False
print("Possible" if isok else "Impossible")

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

h,w = readInts()
a = [list(input()) for i in range(h)]
check = [["."]*w for i in range(h)]
check[0][0]="#"

now = (0,0)
goal = (h-1,w-1)

while 1:
  if now==goal and check==a:
    print("Possible")
    break
  s = (now[0],now[1]+1)
  t = (now[0]+1,now[1])
  if s[1]<w and a[s[0]][s[1]]=="#":
    check[s[0]][s[1]]="#"
    now = s
  elif t[0]<h and a[t[0]][t[1]]=="#":
    check[t[0]][t[1]]="#"
    now = t
  else:
    print("Impossible")
    break

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
h, _ = map(int, input().split())
i = 0
for _ in range(h):
    a = input()
    c = a.count("#")
    if a.replace("#" * c, "").replace(".", "") != "" or a[i:i + c] != "#" * c:
        print("Impossible")
        exit()
    else:
        i += c - 1
print("Possible")

Submission status: Accepted

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

ans='Possible'
i=1
while i<H:
    j=1
    while j<W:
        if A[i][j-1]=='#' and A[i-1][j]=='#':
            ans='Impossible'
        j+=1
    i+=1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

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

def dfs(h, w):
    global cnt
    cnt += 1
    if h+1 < H and A[h+1][w] == '#':
        dfs(h+1, w)
    elif w+1 < W and A[h][w+1] == '#':
        dfs(h, w+1)

cnt = 0

if A[0][0] == '.':
    print('Impossible')
    exit()

dfs(0, 0)
if def_cnt == cnt:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
import sys
H, W = list(map(int, input().split()))
A = [input() for _ in range(H)]
for i in range(H - 1):
    for j in range(W - 1):
        if A[i + 1][j] == '#' and A[i][j + 1] == '#':
            print('Impossible')
            sys.exit()
print('Possible')

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# In[21]:


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


# In[ ]:


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 = sum(input().count('#') for _ in range(h))
print('Possible' if a == h + w - 1 else 'Impossible')

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
a = [sr() for i in range(h)]
c = 0

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            c+=1

def dfs():
    q = deque([[0,0]])
    dir = [[1,0],[0,1]]
    ret = 1
    while q:
        y,x = q.popleft()
        for dy,dx in dir:
            ny,nx = y+dy, x+dx
            if 0<=ny<h and 0<=nx<w and a[ny][nx] == '#':
                ret+=1
                if ny==h-1 and nx==w-1:
                    return ret
                q.append([ny,nx])
                break
    return ret

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

Submission status: Accepted

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

ans=0
cnt=0
 
for i in range(H-1):
    for j in range(W-1):
        if a[i][j] == '#' and a[i+1][j] == '#' and  a[i][j+1] == '#':
            cnt+=1
        elif a[i][j] == '#' and a[i+1][j] == '.' and  a[i][j+1] == '.':
            cnt+=1

            
for i in range(1,H):
    for j in range(1,W):
        if a[i][j] == '#' and a[i-1][j] == '.' and  a[i][j-1] == '.':
            cnt+=1

        
print('Impossible' if cnt>0 else 'Possible')

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
field = []
check = [[False for _ in range(w)] for _ in range(h)]
for i in range(h):
    s = list(input().strip())
    field.append(s)

sx, sy = 0, 0
d = deque()
dirx = [0, 1, 0, -1]
diry = [1, 0, -1, 0]
d.append([sx, sy])
# 離れ島がないかのチェック
while (d):
    nowx, nowy = d.popleft()
    check[nowx][nowy] = True
    for x, y in zip(dirx, diry):
        nx = nowx + x
        ny = nowy + y
        if nx in range(h) and ny in range(w) and (
                not check[nx][ny]) and field[nx][ny] == '#':
            d.append([nx, ny])
for i in range(h):
    for j in range(w):
        if not check[i][j] and field[i][j] == '#':
            print('Impossible')
            exit()

# 右or下のみの最短でいけるかチェック
d.append([sx, sy])
check = [[False for _ in range(w)] for _ in range(h)]
while (d):
    nowx, nowy = d.pop()
    check[nowx][nowy] = True

    for x, y in zip(dirx[0:2], diry[0:2]):
        nx = nowx + x
        ny = nowy + y
        if nx in range(h) and ny in range(w) and field[nx][ny] == '#':
            d.append([nx, ny])
    for x, y in zip(dirx[2:4], diry[2:4]):
        nx = nowx + x
        ny = nowy + y
        if nx in range(h) and ny in range(
                w) and field[nx][ny] == '#' and not check[nx][ny]:
            print('Impossible')
            exit()

    if len(d) == 2:
        print('Impossible')
        exit()
    if nowx == h - 1 and nowy == w - 1:
        print('Possible')
        exit()

print('Impossible')