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: Time Limit Exceeded

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

isExact = 'Possible'

i, j = 0, 0

while i < H - 1 or j < W - 1:
    A[i] = A[i][:j] + '.' + A[i][j + 1:]

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

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

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

print(isExact)

Submission status: Time Limit Exceeded

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

isExact = 'Possible'

i, j = 0, 0

while i < H - 1 or j < W - 1:
    A[i] = A[i][:j] + '.' + A[i][j + 1:]
    
    if j + 1 < W and A[i][j + 1] == '#':
        j += 1
    elif i + 1 < H and A[i + 1][j] == '#':
        i += 1

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

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

print(isExact)

Submission status: Time Limit Exceeded

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

from itertools import permutations

li = ['R' for w in range(W-1)] + ['D' for h in range(H-1)]

for v in permutations(li, H+W-2):
    i,j = 0,0
    B = [['.' for w in range(W)] for h in range(H)]
    B[i][j] = '#'
    for k in range(H+W-2):
        if v[k] == 'R':
            j += 1
        else:
            i += 1
        B[i][j] = '#'

    ans_ = 1
    for i in range(H):
        for j in range(W):
            if A[i][j] != B[i][j]:
                ans_ = 0
    if ans_:
        ans = 'Possible'
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

h,w = inpl()
s = [list(input()) for i in range(h)]
seq = [0]*(h-1) + [1]*(w-1)
d = set()
if s[0][0] != '#':
    print('Impossible')
    quit()
s[0][0] = '.'
for i in itertools.permutations(seq,h+w-2):
    if i in d:
        continue
    d.add(i)
    t = [['' for k in range(w)] for j in range(h)] 
    for k in range(h):
        for j in range(w):
            tmp = s[k][j]
            t[k][j] = tmp
    nx = ny = 0
    # print('t')
    # print(t)
    # print('s')
    # print(s)
    # print(i)
    for j in i:
        if j:
            nx += 1
        else:
            ny += 1
        if t[ny][nx] == '#':
            t[ny][nx] = '.'
    for j in t:
        if '#' in j:
            break
    else:
        print('Possible')
        # print(i)
        # print(t)
        break
else:
    print('Impossible')

Submission status: Time Limit Exceeded

Solution code:
import pprint

H, W = list(map(int, input().split()))
A = []
for h in range(H):
    A.append([s for s in input()])
x, y = 0, 0
goal_x, goal_y = W - 1, H - 1
count = 0
while not (x == goal_x and y == goal_y):
    for diff_x, diff_y in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        tmp_x = x + diff_x
        tmp_y = y + diff_y
        if tmp_x < 0 or tmp_x >= W or tmp_y < 0 or tmp_y >= H:
            continue
        if A[tmp_y][tmp_x] == "#":
            if diff_x == -1 or diff_y == -1:
                print("Impossible")
                exit()
            A[y][x] = "."
            x += diff_x
            y += diff_y
            # print(y, x)
            # pprint.pprint(A)
            count += 1
            if (W + H - 2) < count:
                print("Impossible")
                exit()
            break

A[goal_y][goal_x] = "."
# pprint.pprint(A)

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

Submission status: Time Limit Exceeded

Solution code:
import pprint

H, W = list(map(int, input().split()))
A = []
for h in range(H):
    A.append([s for s in input()])
x, y = 0, 0
goal_x, goal_y = W - 1, H - 1
while not (x == goal_x and y == goal_y):
    for diff_x, diff_y in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        tmp_x = x + diff_x
        tmp_y = y + diff_y
        if tmp_x < 0 or tmp_x >= W or tmp_y < 0 or tmp_y >= H:
            continue
        if A[tmp_y][tmp_x] == "#":
            if diff_x == -1 or diff_y == -1:
                print("Impossible")
                exit()
            A[y][x] = "."
            x += diff_x
            y += diff_y
            # print(y, x)
            # pprint.pprint(A)
            break

A[goal_y][goal_x] = "."
# pprint.pprint(A)

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

Submission status: Time Limit Exceeded

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

for way in itertools.permutations([1 for i in range(h - 1)] + [-1 for i in range(w - 1)]):
    k = 0
    l = 0
    ij_list =[[k, l]]
    for way_route in way:
        k += (way_route == 1)
        l += (way_route == -1)
        ij_list.append([k, l])

    for i, j in itertools.product(range(h), range(w)):
            if [i, j] not in ij_list:
                if a[i][j] != ".":
                    break
            else:
                if a[i][j] != "#":
                    break
    else:
        print("Possible")
        break

else:
    print("Impossible")

Submission status: Time Limit Exceeded

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
    
    # 上か左が"#" -> 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

for A in As:
    if "#" in A:
        ans = "Impossible"

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
tiles = [list(input()) for _ in range(H)]
moves_cnt = 0
for h in range(H):
  for w in range(W):
    if tiles[h][w] == '#':
      moves_cnt += 1

dhw = [(0, 1), (1, 0)]

moves = deque([(0, 0, 1)])
checked = [[False for _ in range(W)] for _ in range(H)]
checked[0][0] = True
ans = 0
while len(moves) > 0:
  h, w, m = moves.pop()
  if h == H-1 and w == W-1:
    ans = m
    break
  for dh, dw in dhw:
    if h+dh < H and w+dw < W and tiles[h+dh][w+dw] == '#' and not checked[h+dh][w+dw]:
      moves.appendleft((h+dh, w+dw, m+1))
      checked[h+dh][w+dw] = True
if ans == moves_cnt:
  print('Possible')
else:
  print('Impossible')

Submission status: Accepted

Solution code:
h, w = map(int, input().split()); a = [input() for _ in range(h)]; z = 0
for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            if a[i+1][j] == "#" and a[i][j+1] == "#": print("Impossible"); z = 1; break
        elif i == h-1 and j == w-1:
            if a[i-1][j] == "#" and a[i][j-1] == "#": print("Impossible"); z = 1; break
        else:
            if a[i][j] == "#":
                x = y = 0
                if i != 0:
                    if a[i-1][j] == "#": x += 1
                if j != 0:
                    if a[i][j-1] == "#": x += 1
                if i != h-1:
                    if a[i+1][j] == "#": y += 1
                if j != w-1:
                    if a[i][j+1] == "#": y += 1
                if x != 1 or y != 1: print("Impossible"); z = 1; break
    if z == 1: break
else: print("Possible")

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	A_fix
# CreatedDate:  2020-09-27 15:12:42 +0900
# LastModified: 2020-09-27 15:23:26 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def Possible_or_Impossible(visited, H, W):
    for v in visited:
        if -1 in v:
            return 0
    return 1



def DFS(visited, maze, H, W, u):
    visited[u[0]][u[1]] = 1
    if visited[u[0]+1][u[1]] == -1 and maze[u[0]+1][u[1]] == 1:
        if DFS(visited, maze, H, W, [u[0]+1, u[1]]) == 1:
            return 1
        visited[u[0]+1][u[1]] = -1

    if visited[u[0]][u[1]+1] == -1 and maze[u[0]][u[1]+1] == 1:
        if DFS(visited, maze, H, W, [u[0], u[1]+1]) == 1:
            return 1
        visited[u[0]][u[1]+1] = -1

    if Possible_or_Impossible(visited, H, W) == 1:
        return 1


def main():
    H, W = map(int, input().split())
    maze = [[0]*(W+2)]
    visited = [[0]*(W+2)]
    for _ in range(H):
        S = input()
        S = [0 if s == "." else 1 for s in S]
        V = [0 if s == 0 else -1 for s in S]
        S.insert(0, 0)
        V.insert(0, 0)
        S.append(0)
        V.append(0)
        maze.append(S)
        visited.append(V)
    maze.append([0]*(W+2))
    visited.append([0]*(W+2))
    if DFS(visited, maze, H, W, [1, 1]) == 1:
        print("Possible")
    else:
        print("Impossible")



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
H, W = list(map(int, input().split()))
A = [input() + '.' for _ in range(H)]
A.append('.' * (W + 1))

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

# cur = (0, 0)
# while True:
#     x, y = cur
#     if x == W - 1 and y == H - 1:
#         print("Possible")
#         break
#     nx1, ny1 = x + 1, y
#     nx2, ny2 = x, y + 1
#     if A[ny1][nx1] == '#' and A[ny2][nx2] == '#':
#         print("Impossible")
#         break
#     if A[ny1][nx1] == '#':
#         cur = (nx1, ny1)
#     elif A[ny2][nx2] == '#':
#         cur = (nx2, ny2)
#     else:
#         print("Impossible")
#         break

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(input())
num = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      num += 1
A = [[0 for j in range(W)] for i in range(H)]
d = deque([[0, 0]])
while len(d) > 0:
  x = d.pop()
  A[x[0]][x[1]] = 1
  if x[0] + 1 < H and S[x[0]+1][x[1]] == "#":
    d.append([x[0]+1, x[1]])
  if x[1] + 1 < W and S[x[0]][x[1]+1] == "#":
    d.append([x[0], x[1]+1])
if num == H + W - 1 and A[H-1][W-1] == 1:
  print("Possible")
else:
  print("Impossible")

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [''] * H
for i in range(H):
    A[i] = input()
x, y = 0, 0
while True:
    if (x < H-1 and A[x+1][y] == '#') and (y < W-1 and A[x][y+1] == '#'):
        print('Impossible')
        exit()
    elif (x > 0 and A[x-1][y] == '#') and (y > 0 and A[x][y-1] == '#'):
        print('Impossible')
        exit()
    elif x == H-1 and y == W-1:
            print('Possible')
            exit()
    elif (x == H-1 or A[x+1][y] == '.') and (y == W-1 or A[x][y+1] == '.'):
        print('Impossible')
        exit()
    elif x < H-1 and A[x+1][y] == '#':
        x += 1
        continue
    elif y < W-1 and A[x][y+1] == '#':
        y += 1
        continue

Submission status: Accepted

Solution code:
import sys
h,w = map(int,input().split())
ls = [list(input()) for _ in range(h)]
i = 0
j = 0
while True:
    flag = False
    if i > 0:
        if ls[i-1][j] == "#":
            print("Impossible")
            sys.exit()
    if i < h-1:
        if ls[i+1][j] == "#":
            if flag == False:
                flag = True
                ls[i][j] = "."
                nx = [0,1,0,0]
            else:
                print("Impossible")
                sys.exit()
    if j > 0:
        if ls[i][j-1] == "#":
            print("Impossible")
            sys.exit()
    if j < w-1:
        if ls[i][j+1] == "#":
            if flag == False:
                flag = True
                ls[i][j] = "."
                nx = [0,0,0,1]
            else:
                print("Impossible")
                sys.exit()
    if i == h-1 and j == w-1:
        break
    if nx[1] == 1:
        i += 1
    else:
        j += 1
print("Possible")

Submission status: Accepted

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

#import
#import math
#import numpy as np
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

for i in range(H):
    for j in range(W):

        if A[i][j] != "#":
            continue

        ul = 0
        dr = 0

        if i != 0:
            if A[i - 1][j] == "#":
                ul += 1
        if i != H - 1:
            if A[i + 1][j] == "#":
                dr += 1
        if j != 0:
            if A[i][j - 1] == "#":
                ul += 1
        if j != W - 1:
            if A[i][j + 1] == "#":
                dr += 1

        if dr > 1 or ul > 1:
            print("Impossible")
            exit()

print("Possible")

Submission status: Accepted

Solution code:
import sys
def input():
  return sys.stdin.readline().rstrip()

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

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

Submission status: Accepted

Solution code:
H,W=list(map(int, input().split()))
A=[list(input()) for _ in range(H)]
for i in range(2**(H+W)):
  L=[['.']*W for _ in range(H)]
  L[0][0]='#'
  c,d=0,0
  for j in range(H+W):
    if (i>>j)&1:
      c+=1
    else:
      d+=1
    if 0<=c<H and 0<=d<W:
      L[c][d]='#'
    else:
      break
  for k in range(H):
    if A[k]!=L[k]:
      break
  else:
    print('Possible')
    exit()
else:
  print('Impossible')

Submission status: Accepted

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

Submission status: Accepted

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

def dfs(x,y):
    field[x][y]='.'
    dx=[0,1]
    dy=[1,0]
    for i in range(2):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<=nx and nx<H and 0<=ny and ny<W and field[nx][ny]=="#":
            dfs(nx,ny)
            break
    return

dfs(0,0)

for i in range(H):
    for j in range(W):
        if field[i][j]=='#':
            print('Impossible')
            exit()
print('Possible')

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]
right_limit = [0]*h
for j in range(w):
    if a[0][j] == "#":
        right_limit[0] = j

for i in range(1, h):
    for j in range(w):
        if right_limit[i-1] > j and a[i][j] == "#":
            print("Impossible")
            exit()
        if a[i][j] == "#":
            right_limit[i] = j
print("Possible")

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

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

s = sum(1 for i in range(H) for j in range(W) if A[i][j] == '#')
if s == H+W-1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

    a = []
    for i in range(h):
        a.append(input())

    count = 0

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

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


'''
    for i in range(h):
        a.append(input()+'.')

    a.append('.' * (w-1))

    print(a)
    i = 0
    j = 0
    while True:
        if last == 'up':
            if a[i+1][j] == '#' and a[i][j+1] == '.':
                last = 'up'
                i += 1
            elif a[i+1][j] == '.' and a[i][j+1] == '#':
                last = 'left'
                j += 1
            else:
                print('Impossible')
                return 0
        if i == h-1 and j == w-1:
            break
        print(i, j)

    print('Possible')
    return 0
'''

if __name__ == "__main__":
    main()


'''

possible判定条件

前のコマの位置（左or上）以外は右or下のみに#がある
コマの移動はすべて連続である
コマの移動数はH+W-1である

'''

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:
H,W = map(int,input().split())
road = [input()for i in range(H)]
rightest = 0
bottomest = 0
for i in range(H):
    for j in range(W):
        if road[i][j] == '#':
            if j < rightest:
                print('Impossible')
                exit()
            rightest = j
print('Possible')

Submission status: Accepted

Solution code:
def dfs(cnt=0, y=0, x=0):
    if y == H-1 and x == W-1:
        if S == cnt+1:
            global naraba
            naraba = True
        return
    for dy, dx in [(1, 0), (0, 1)]:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == "#" and not V[ny][nx]:
            V[ny][nx] = True
            dfs(cnt+1, ny, nx)
            V[ny][nx] = False


if __name__ == "__main__":
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    V = [[False]*W for _ in range(H)]
    S = 0
    for a in A:
        S += a.count("#")
    V[0][0] = True
    naraba = False
    dfs()
    if naraba:
        print("Possible")
    else:
        print("Impossible")

Submission status: Accepted

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

for i in range(h):
  for j in range(w):
    if c[i][j]=="#":
      s+=1
      
a = 1
x = 0
y = 0

while a<s:
  flg = True
  while x+1<w and c[y][x+1]=="#":
    x+=1
    a+=1
    flg = False
  while y+1<h and c[y+1][x]=="#":
    y+=1
    a+=1
    flg = False
  if flg:
    break
if a==s:
  print("Possible")
else:
  print("Impossible")

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[input()for i in range(H)]
for i in range(H):
    A[i]=A[i]+"."
A.append("."*(W+1))
p,q=1,1
c=1
t=0
for i in A:
    t+=i.count("#")
if t!=H+W-1:
    c=0
for i in range(H+W-2):
    if A[p-1][q-1]==".":
        c=0
        break
    if A[p][q-1]=="." and A[p-1][q]=="#":
        q+=1
    elif A[p][q-1]=="#" and A[p-1][q]==".":
        p+=1
    else:
        c=0
        break
print("Possible" if c else "Impossible")

Submission status: Accepted

Solution code:
h,w=map(int,input().split());A=[list(input())for _ in "_"*h]
def f(x,y):
  A[x][y]="."
  if x<h-1 and A[x+1][y]<".":return f(x+1,y)
  if y<w-1 and A[x][y+1]<".":return f(x,y+1)
f(0,0);print(['P','Imp']['#' in [x for a in A for x in a]]+'ossible')

Submission status: Accepted

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

maze = [[0] for _ in range(h)]
for i in range(h):
    maze[i] = list(input())

flag = True
prev = 0
for row in maze:
    if "#" not in row:
        flag = False
        break
    left = row.index("#")
    if prev != left:
        flag = False
        break
    for r in range(left,w):
        if row[r] == "#":
            right = r
        else:
            break
    check_r = w-1-row[::-1].index("#")
    if check_r != right:
        flag = False
        break
    prev = right
if flag:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = []
sh = 0
for i in range(h):
  t = input()
  sh += t.count('#')
  s.append(t)

visited = [[False for j in range(w)] for i in range(h)]

dx = [0,1]
dy = [1,0]
def dfs(x,y,cnt):
  visited[x][y] = True
  cnt += 1
  if x == h-1 and y == w-1:
    if cnt == sh:
      print ('Possible')
      exit()
    return
  for i in range(2):
    a = x+dx[i]
    b = y+dy[i]
    if a < 0 or b < 0 or a >= h or b >= w or visited[a][b] or s[a][b] == '.':
      continue
    dfs(a,b,cnt)

dfs(0,0,0)

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):
    cnt += a[i].count('#')
if cnt == h + w - 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# A - Shik and Stone
import sys
sys.setrecursionlimit(10**7)
H,W = map(int,input().split())
mp = [list(input()) for _ in range(H)]

dw = [1,0]
dh = [0,1]

seen = [[False]*W for _ in range(H)]
def dfs(h,w):
    seen[h][w] = True
    # まず右に進もうとする
    nxt_h = h 
    nxt_w = w + 1   
    # 右が壁か範囲外なら下に進む
    if  not(-1<nxt_w<W) or mp[nxt_h][nxt_w] == '.':
        nxt_h = h + 1
        nxt_w = w 
    # 下も行き止まりならスルー
    if not(-1<nxt_h<H):
        return
    if (seen[nxt_h][nxt_w] == True) or (mp[nxt_h][nxt_w] == '.'):
        return
    dfs(nxt_h,nxt_w)
        
dfs(0,0)

result = 'Possible'
for h in range(H):
    for w in range(W):
        if mp[h][w] == '#':
            if seen[h][w] == False:
                result = 'Impossible'
                break
print(result)

Submission status: Accepted

Solution code:
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

h, w = inintm()
grid = []
now = [0,0]
fw = 0
fh = 0

for i in range(h):
    grid.append(input())

while now != [h-1,w-1]:
    if now[0] == h-1:
        if fh == 0 and now[1] != 0:
            if grid[h-1][now[1]+1] == "#" and grid[h-1][now[1]-1] == ".":
                now = [h-1, now[1]+1]
                fh = 1
        else:
            if grid[h-1][now[1]+1] == "#":
                now = [h-1, now[1]+1]
                fh = 1
            else:
                print("Impossible")
                exit()
    elif now[1] == w-1:
        if fw == 0 and now[0] != 0:
            if grid[now[0]+1][w-1] == "#" and grid[now[0]-1][w-1] == ".":
                now = [now[0]+1, w-1]
                fw = 1
            else:
                print("Impossible")
                exit()
        else:
            if grid[now[0]+1][w-1] == "#":
                now = [now[0]+1, w-1]
                fw = 1
            else:
                print("Impossible")
                exit()
    else:
        if grid[now[0]+1][now[1]] == "#" and grid[now[0]][now[1]+1] == ".":
            now = [now[0]+1, now[1]]
        elif grid[now[0]+1][now[1]] == "." and grid[now[0]][now[1]+1] == "#":
            now = [now[0], now[1]+1]
        else:
            print("Impossible")
            exit()

if fh == 0 and grid[h-1][w-2] == "#" and (h >= 2 and w >= 2):
    print("Impossible")
    exit()

print("Possible")

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 "Impossible")

Submission status: Accepted

Solution code:
def search(y,x,oy,ox,r):
    if y == h-1 and x == w-1:
        return r
    l = []
    for i,j in t:
        ny,nx = y+i,x+j
        if (0 <= ny < h and 0 <= nx < w) and not (ny == oy and nx == ox):
            if a[ny][nx] == "#":
                l.append((ny,nx))

    if 1 < len(l) or len(l) == 0:
        return r
    else:
        r.add((l[0][0],l[0][1]))
        return search(l[0][0],l[0][1],y,x,r)

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

s = search(0,0,0,0,set([(0,0),(h-1,w-1)]))
f = True
for i in range(h):
    for j in range(w):
        if a[i][j] == "#" and not (i,j) in s:
            print("Impossible")
            exit(0)
print("Possible")

Submission status: Accepted

Solution code:
def check(h, w):
  if A[h][w] != r:
    return True
  if h == H - 1 and w == W - 1:
    return True
  cnt = 0
  if h + 1 < H:
    cnt += A[h + 1][w] == r
  if w + 1 < W:
    cnt += A[h][w + 1] == r
  if cnt != 1:
    return False
  if h == 0 and w == 0:
    return True
  cnt = 0
  if h - 1 >= 0:
    cnt += A[h - 1][w] == r
  if w - 1 >= 0:
    cnt += A[h][w - 1] == r
  if cnt == 0:
    return False
  return True

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

for i in range(H):
  for j in range(W):
    if not check(i, j):
      print("Impossible")
      exit()

print("Possible")

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    h,w = LI()
    shortest = h+w-1
    cnt = 0
    for i in range(h):
        line = S()
        cnt += line.count("#")
    ans = shortest==cnt 
    print("Possible" if ans else "Impossible")
main()

Submission status: Accepted

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

tmp = 0

for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            if j < tmp:
                print("Impossible")
                exit()
            else:
                tmp = j


print("Possible")

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s = 0
for _ in range(H):
    S = input().rstrip() + "."
    a0 = "."
    A = []
    for i, a in enumerate(S):
        if a==a0:
            continue
        else:
            A.append(i)
        a0 = a
    if len(A) > 2:
        print("Impossible")
        exit()
    if s != A[0]:
        print("Impossible")
        exit()
    s = A[1]-1
print("Possible")

Submission status: Accepted

Solution code:

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

A = [[c=='#' for c in input()] for _ in range(H)]

dp = [[False]*W for _ in range(H)]

dp[0][0] = True
def solve():

    s = sum(sum(l) for l in A)
    if s != H+W-1:
        return False

    for d in range(1,H+W):
        if d < W:
            dp[0][d] = dp[0][d-1] and A[0][d]
        if d < H:
            dp[d][0] = dp[d-1][0] and A[d][0]
        for i in range(1,d):
            j = d-i
            if i >= H or j >= W:
                continue
            dp[i][j] = A[i][j] and (dp[i-1][j] or dp[i][j-1])

    return dp[-1][-1]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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!=h+w-1 or a[0][0]!="#" or a[-1][-1]!="#":
    print("Impossible")
    exit()

now=[0,0]
for i in range(h+w-2):
    if now[0]+1<h and a[now[0]+1][now[1]]=="#":
        now[0]+=1
    elif now[1]+1<w and a[now[0]][now[1]+1]=="#":
        now[1]+=1
    else:
        print("Impossible")
        exit()
print("Possible")

Submission status: Accepted

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

Submission status: Accepted

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

x = 0
y = 0
while x < h or y < w:
    if x < h - 1 and grid[x + 1][y] == "#":
        grid[x][y] = "."
        x += 1
    elif y < w - 1 and grid[x][y + 1] == "#":
        grid[x][y] = "."
        y += 1
    else:
        break

if x != h - 1 or y != w - 1:
    print("Impossible")
else:
    grid[x][y] = "."
    for line in grid:
        if "#" in line:
            print("Impossible")
            quit()
    print("Possible")