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:
# 2019/08/16

h,w=map(int,input().split())
w+=2
a=[['.']*w]
for i in range(h):
    a+=[['.']+list(input())+['.']]

a+=[['.']*w]

g=(h,w-2)
cnt=0

i,j=1,1
while i<h or j<w:
    a[i][j]='@'
    if a[i-1][j]=='#' or a[i][j-1]=='#':
        ans='Impossible'
        break

    if (i,j)==g:
        ans='Possible'
        break
        
    if (a[i+1][j]=='#')^(a[i][j+1]=='#'):
        if a[i+1][j]=='#':
            i+=1
        else:
            j+=1
    else:
        ans='Impossible'
        break

print(ans)

Submission status: Accepted

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

A = [list(input()) for _ in range(H)]

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

if count != H + W - 1:
    print ('Impossible')
    exit()

def move(i, j): #今、マス(i, j)にいる
    if A[i][j] == '.': #道ではない時
        return False
    if i == H - 1 and j == W - 1: #ゴール地点にいる時
        return True
    if i == H - 1: #一番下の段にいるとき
        return move(i, j + 1)
    if j == W - 1: #一番右の列にいるとき
        return move(i + 1, j)
    if A[i + 1][j] == A[i][j + 1]: #両方道 or 両方行き止まり
        return False 
    if A[i + 1][j] == '#': #下が道の時
        return move(i + 1, j)
    if A[i][j + 1] == '#': #右が道の
        return move(i, j + 1)

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

Submission status: Accepted

Solution code:
h,*a=open(0);print(("Imp"*(sum(x.count("#")for x in a)!=eval(h.replace(" ","+"))-1)or"P")+"ossible")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
m = [list(input()) for _ in range(h)]
cnt = 0
for i in range(h):
    for j in range(w):
        if m[i][j] == '#':
            cnt += 1
if cnt == h + w - 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
a = []
a.append("."*(w+2))
for i in range(h):
    a.append("." + input() + ".")
a.append("."*(w+2))
ans = "Possible"
for i in range(h+2):
    for j in range(w+2):
        if a[i][j] == "#":
            if i==1 and j==1:
                if [a[i+1][j],a[i][j+1]].count("#")!=1:
                    ans = "Impossible"
            elif i==h and j==w:
                if [a[i-1][j],a[i][j-1]].count("#")!=1:
                    ans = "Impossible"
            else:
                if [a[i-1][j],a[i][j-1]].count("#")!=1 or [a[i+1][j],a[i][j+1]].count("#")!=1:
                    ans = "Impossible"
print(ans)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
m = []
k = 0
for _ in range(H):
    a = list(input())
    k += a.count('#')
    m.append(a)
if k == H+W-1:
    sx = sy = 0
    for i in range(H+W-1):
        if   (sx+1<W) and (m[sy][sx+1] == '#'):sx += 1
        elif (sy+1<H) and (m[sy+1][sx] == '#'):sy += 1
        else:
            if (sx==W-1) and (sy==H-1):print('Possible')
            else:print('Impossible',sx,sy)
            exit(0)
else:
    print('Impossible')

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [[] for i in range(H+2)]
for i in range(H):
    A[i+1] = list(input())
    A[i+1].insert(0,'.')
    A[i+1].append('.')

A[0] = list('.' * (W+2))
A[H+1] = list('.' * (W+2))

for i in range(H+2):
    A[i] = ''.join(A[i])
    #print(A[i])



check = 0

for i in range(1,H+1):
    for j in range(1, W+1):
        if i == 1 and j ==1 :
            if A[i][j] == '#':
                if A[i+1][j] == '.' and A[i][j+1] == '#':
                    pass
                elif A[i+1][j] == '#' and A[i][j+1] == '.':
                    pass
                else:
                    check = 1
                pass
            else:
                check = 1

        elif i == H and j ==W :
            if A[i][j] == '#':
                if A[i-1][j] == '.' and A[i][j-1] == '#':
                    pass
                elif A[i-1][j] == '#' and A[i][j-1] == '.':
                    pass
                else:
                    check = 1
                pass
            else:
                check = 1

        else:
            if A[i][j] == '#':
                if A[i+1][j] == '.' and A[i][j+1] == '#' and A[i-1][j] == '.' and A[i][j-1] == '#':
                    pass
                elif A[i+1][j] == '#' and A[i][j+1] == '.' and A[i-1][j] == '.' and A[i][j-1] == '#':
                    pass
                elif A[i+1][j] == '.' and A[i][j+1] == '#' and A[i-1][j] == '#' and A[i][j-1] == '.':
                    pass
                elif A[i+1][j] == '#' and A[i][j+1] == '.' and A[i-1][j] == '#' and A[i][j-1] == '.':
                    pass
                else:
                    check = 1

if check == 0:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
# 右と下に移動する場合は絶対に最短経路になるので、最短経路を出してそれ以外に#があったらアウト、の方針で
def end_impossible():
    print("Impossible")
    exit()


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

if A[0][0] == ".":
    end_impossible()

seen.append([0, 0])
h, w = 0, 0

while h != H - 1 or w != W - 1:
    if h < H - 1 and A[h + 1][w] == "#":
        h += 1
    elif w < W - 1 and A[h][w + 1] == "#":
        w += 1
    else:
        end_impossible()
    seen.append([h, w])

for i in range(H):
    for j in range(W):
        if A[i][j] == "#" and [i, j] not in seen:
            end_impossible()

print("Possible")

Submission status: Accepted

Solution code:
#### import ####
import sys
sys.setrecursionlimit(10**7)
import math
from collections import defaultdict

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

H,W = II()
A = [list(map(str, input())) for _ in range(H)]
for i in range(H):
  A[i].append('?')
A.append(['?']*(W+1))

i=0;j=0
A[i][j]='.'
while 1:
  if i==H-1 and j==W-1:
    break
  if A[i+1][j]=='#':
    A[i+1][j]='.'
    i +=1
    continue
  if A[i][j+1]=='#':
    A[i][j+1]='.'
    j +=1
    continue
  print('Impossible')
  exit()

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W = [int(x) for x in input().split()]
A = [list(input()) for _ in range(H)]
#%%
def dfs(h,w):
    if(A[h][w]=='.'):
        return False
    else:
        A[h][w]='.'
        x = False
        if(w<W-1):
            x = dfs(h,w+1)
        if(not x and h<H-1):
            dfs(h+1,w)
        return True

dfs(0,0)
for a in A:
    if('#' in a):
        print('Impossible')
        break
else:
    print('Possible')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h, w = [ int(v) for v in input().split() ]

v = 0
for i in range(h):
  v += input().count("#")
  
if v == h + w - 1:
  print("Possible")
else:
  print("Impossible")

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
c = []
for i in range(a):
    c.append(list(input()))
x = y = 0
while True:
    c[x][y] = "."
    if x == a - 1 and y == b - 1:
        break
    d = False
    if x + 1 < a and not d:
        if c[x+1][y] == "#":
            d = not d
            x += 1
    if y + 1 < b and not d:
        if c[x][y + 1] == "#":
            d = not d
            y += 1
    if not d:
        print("Impossible")
        exit()
p = True
for i in range(a):
    if "#" in c[i]:
        print("Impossible")
        exit()
print("Possible")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# AGC007A - Shik and Stone
import sys
input = sys.stdin.readline

def main():
    h, w = tuple(map(int, input().rstrip().split()))
    B = tuple(input().rstrip() for _ in range(h))
    cnt = ("".join(B)).count("#")
    print("Possible" if cnt == h + w - 1 else "Impossible")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if maze[y+1][x]=="#" and maze[y][x+1]=="#":
            return("Impossible")
        for j, k in ([-1, 0], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "#" and visited[new_y][new_x] == -1:
                return("Impossible")
        for j, k in ([1, 0], [0, 1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "#" and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
        if x==gx and y==gy:
            return("Possible")
h,w=map(int,input().split())
sy,sx=1,1
gy,gx=h,w
maze =["$"*(w+2)]+["$"+input()+"$" for i in range(h)]+["$"*(w+2)]
visited = [[-1]*(w+2) for j in range(h+2)]
print(bfs(maze, visited, sy, sx, gy, gx))

Submission status: Accepted

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

t = 0
for i in range(N):
    for j in range(M):
        if a[i][j] == "#":
            if t <= j:
                t = j
            else:
                print("Impossible")
                exit()
print("Possible")

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
c = [list(input())for _ in range(a)]
x = y = 0
c[x][y] = "."
while True:
    moved = False
    if x < a-1:
        if c[x+1][y] =="#":
            c[x+1][y] = "."
            x += 1
            if not moved:
                moved = not moved
    if y < b-1:
        if c[x][y+1] == "#":
            c[x][y + 1] = "."
            y += 1
            if not moved:
                moved = not moved
    if x == a-1 and y == b-1:
        for i in range(a):
            for j in range(b):
                if c[i][j] == "#":
                    print("Impossible")
                    exit()
        print("Possible")
        exit()
    if not moved:
        print("Impossible")
        exit()

Submission status: Accepted

Solution code:
h,w=map(int,input().split());c=0
for i in range(h):
  a,b=input(),[]
  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:
import sys
h,w=map(int,input().split())
f=[[] for i in range(h)]
for i in range(h):
  inv=input()
  for j in range(w):
    if inv[j]=="#":
      f[i].append(j)
c=0
for i in f:
  if c!=i[0]:
    print("Impossible");sys.exit()
  if i[-1]-i[0]>=len(i):print("Impossible");sys.exit()
  c=i[-1]
print("Possible")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split()) # 横に2個

c = 0
for _ in range(H):
    for a in input():
        if a == '#':
            c += 1

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[list(input()+'.') for _ in range(h)]
d=['.']*(w+1)
a.append(d)
x=1
i=0;j=0
a[0][0]='.'
while i!=h-1 or j!=w-1:
  if a[i+1][j]=='#':
    if a[i][j+1]=='#':
      x=0
      break
    else:
      i=i+1
      a[i][j]='.'
  else:
    if a[i][j+1]=='.':
      x=0
      break
    else:
      j=j+1
      a[i][j]='.'
if x==1:
  for k in range(h):
    if '#' in a[k]:
      x=0
      break
print('Possible' if x==1 else 'Impossible')

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
pos = 0
for _ in range(H):
    line = input()
    for i, l in enumerate(line):
        if l == "#":
            if i < pos:
                print("Impossible")
                exit()
            if pos < i:
                pos = i
print("Possible")

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):
    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())
cnt = 0
for _ in range(H):
    cnt += input().count('#')

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h, w = [int(i) for i in input().split()]
cnt = 0
for i in range(h):
    cnt += input().count("#")

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
A=[list(input()) for _ 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:
def solve(h, w, a):
    a = list(map(list, a))
    total = 0
    for r in range(h):
        for c in range(w):
            if a[r][c] == "#":
                total += 1
    que = [(0,0)]
    a[0][0] = "."
    while que:
        cr, cc = que.pop(0)
        for dr, dc in [(1,0),(0,1)]:
            nr, nc = cr+dr, cc+dc
            if (0 <= nc < w) and (0 <= nr < h) and a[nr][nc] == "#":
                a[nr][nc] = "."
                que.append((nr, nc))
    return "Possible" if (a[h-1][w-1] == ".") and (total == h+w-1) else "Impossible"

h, w = map(int, input().split())
a = [input() for r in range(h)]
print(solve(h, w, a))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
c = 0
A = ['.' * (W + 2)]
for _ in range(H):
    a = input()
    c += a.count('#')
    A.append('.' + a + '.')
A.append('.' * (W + 2))

right = [0, 1]
under = [-1, 0]
goal = [H, W]
now = [1, 1]
ans = 1
while now != goal:
    if A[now[0] + 1][now[1]] == '#' and A[now[0]][now[1] + 1] == '#':
        break
    if A[now[0] + 1][now[1]] == '#':
        ans += 1
        now[0] += 1
    else:
        if A[now[0]][now[1] + 1] == '#':
            ans += 1
            now[1] += 1
        else:
            break

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
for x in range(h):
    a=input()
    for i in range(w):
        if a[i]=="#":
            l=i
            break
    for j in range(w):
        if a[w-1-j]=="#":
            r=w-1-j
            break
    if x>0:
        if br>l:
            print("Impossible")
            exit()
    bl=l
    br=r
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:
#!/usr/bin/env python3
import sys
INF = float("inf")


def yes():
    print("Possible")  # type: str


def no():
    print("Impossible")  # type: str


def main():
    H, W = map(int, input().split())
    A = [None]*H
    for i in range(H):
        A[i] = list(input())

    # 個数がH+W-1でなければ、条件を満たすさない。
    if H+W-1 != sum([A[i].count("#") for i in range(H)]):
        no()
        return

    # 連結しているか
    yes()

    pass


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for way in itertools.combinations([i for i in range(h + w - 2)], h - 1):
    k = 0
    l = 0
    ij_list =[[k, l]]
    #print(way)
    for i in range(h + w - 1):
        k += (i in way)
        l += (i not in way)
        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: Accepted

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

Submission status: Accepted

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

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

bl = True
x,y = 0,0
for _ in range(H+W-2):
  if x+1 < H and A[x+1][y] == '#':
    x += 1
    continue
  if y+1 < W and A[x][y+1] == '#':
    y += 1
    continue
  bl = False
  break

bl = bl and (sum(x.count('#') for x in A) == H+W-1)
answer = 'Possible' if bl else 'Impossible'
print(answer)

Submission status: Accepted

Solution code:
import itertools
from sys import stdin
H,W = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for _ in range(H):
    data.append(list(input()))

right = 0
down  = 0
for i in data:
    for j in range(0,W-1):
        if i[j] == "#" and i[j+1] == "#":
            right += 1

data_t = []
for i in range(W):
    row = []
    for vector in data:
        row.append(vector[i])
    data_t.append(row)

for i in data_t:
    for j in range(0,H-1):
        if i[j] == "#" and i[j+1] == "#":
            down += 1

if down == H-1 and right == W-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

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

f = 1
k = 0
p = 0
for _ in range(h):
  s = input()
  k += s.count("#")
  if s[p] == ".":
    f = 0
    break
  else:
    for i in range(p,w):
      if s[i] == ".":
        break
      else:
        p = i

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h, w = [int(item) for item in input().split()]
field = [input().rstrip() for _ in range(h)]
path = 0
for line in field:
    path += line.count("#")
if path != h + w - 1:
    print("Impossible")
else:
    print("Possible")

Submission status: Accepted

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

ds = ((0, 1), (1, 0))
cp = [(0, 0)]
sc = 1

while cp:
	np = []
	for p in cp:
		y, x = p
		for d in ds:
			dy, dx = y + d[0], x + d[1]
			if 0 <= dy < H and 0 <= dx < W:
				if "#" == STAGE[dy][dx]:
					sc += 1
					if not (dy, dx) in np:
						np += [(dy, dx)]
						break
			else:
				continue
	#print(np)
	cp = np

c = 0
for line in STAGE:
	c += line.count("#")

print(["Possible", "Impossible"][not(sc == c)])

Submission status: Accepted

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

A_lst = []
for i in range(H):
    tmp = list(input())
    A_lst.append(tmp)

#print(A_lst)

def judge(A_lst): 
    for i in range(1, H):
        for j in range(1, W):
            if A_lst[i][j-1] == "#" and A_lst[i-1][j] == "#":
                return False
    return True

if judge(A_lst):
    print("Possible")

else:
    print("Impossible")

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
As =[input() for _ in range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if As[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=[[i for i in input()] for i in range(h)]
i=0
j=0
a[0][0]="."
while not(i==h-1 and j==w-1):
    if(i==h-1):
        if(a[i][j+1]=="#"):
            a[i][j+1]="."
            j+=1
        else:
            print("Impossible")
            break
    elif(j==w-1):
        if(a[i+1][j]=="#"):
            a[i+1][j]="."
            i+=1
        else:
            print("Impossible")
            break
    else:
        if(a[i][j+1]=="#" and not a[i+1][j]=="#"):
            a[i][j+1]="."
            j+=1
        elif(not a[i][j+1]=="#" and a[i+1][j]=="#"):
            a[i+1][j]="."
            i+=1
        else:
            print("Impossible")
            break
else:
    if any("#" in i for i in a):
        print("Impossible")
    else:
        print("Possible")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
A - Shik and Stone
https://atcoder.jp/contests/agc007/tasks/agc007_a

"""
import sys


def solve(H, W, grid):
    x, y = 0, 0
    while True:
        grid[y][x] = '@'
        if x+1 < W and grid[y][x+1] == '#':
            x += 1
        elif y+1 < H and grid[y+1][x] == '#':
            y += 1
        else:
            break
    for row in grid:
        if '#' in row:
            return 'Impossible'
    return 'Possible'


def main(args):
    H, W = map(int, input().split())
    grid = [list(input()) for _ in range(H)]
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

Submission status: Accepted

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

A[-1] = ['.'] * (W+1)

x = 0
y = 0
p = 1

while x < W and y < H:
    right = A[y][x+1] == '#'
    down = A[y+1][x] == '#'
    if right:
        x += 1
        p += 1
    elif down:
        y += 1
        p += 1
    else:
        break

print(['Impossible','Possible'][o == p])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
As =[input() for _ in range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if As[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())
G=[input()+"." for _ in range(H)]+["."*(W+1)]
G_cnt=sum([g.count("#") for g in G])
p=[0,0]
i=1
while(p!=[H-1,W-1]):
    if G[p[0]+1][p[1]]==G[p[0]][p[1]+1]:
        print("Impossible")
        break
    elif G[p[0]+1][p[1]]=="#":
        p=[p[0]+1,p[1]]
        i+=1
    else:
        p=[p[0],p[1]+1]
        i+=1
else:
    if i==G_cnt:
        print("Possible")
    else:
        print("Impossible")

Submission status: Accepted

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

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

Submission status: Accepted

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

def dfs(h, w, count):
    if (h, w) == (H - 1, W - 1):
        return count

    ans = 0
    for nh, nw in [(h + 1, w), (h, w + 1)]:
        if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == "#":
            ans += dfs(nh, nw, count + 1)
    return ans

if dfs(0, 0, 1) == sum(a.count("#") for a in A):
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
L=[]
for i in range(H):
    a=[]
    b=list(input())
    for j in range(W):
        if b[j]=="#":
            a.append(j)
    if a==[]:
        print("Impossible")
        exit()
    L.append([min(a),max(a)])
#print(L)
for i in range(1,H):
    if L[i][0]==L[i-1][1]:
        pass
    else:
        print("Impossible")
        exit()
print("Possible")

Submission status: Accepted

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

Submission status: Accepted

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

x = ms = 0
for i in range(H):
    for j in range(x,W):
        if A[i][j] == '.':
            if i==H-1:
                print('Impossible')
            else:
                break
        else:
            x = j
            ms += 1

cs = sum(row.count('#') for row in A)

print('Possible' if cs==ms else 'Impossible')

Submission status: Accepted

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

numright = 0
numdown = 0
for i in range(H):
    now = A[i][0]
    for j in range(1,W):
        if now == "#" and A[i][j] == "#":
            numright += 1
        now = A[i][j]

for i in range(W):
    now = A[0][i]
    for j in range(1,H):
        if now == "#" and A[j][i] == "#":
            numdown += 1 
        now = A[j][i]

#print(numdown,numright)
if numdown == H - 1 and numright == W - 1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
from queue import Queue
h, w = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(input()))
x = [0, 1]
y = [1, 0]
a[0][0] = 0
q = Queue()
q.put([0, 0])
while (q.qsize() > 0):
    start_y, start_x = q.get()
    for i in range(2):
        xx = start_x + x[i]
        yy = start_y + y[i]
        if (xx >= 0) & (xx < w) & (yy >= 0) & (yy < h):
            if a[yy][xx] == "#":
                a[yy][xx] = a[start_y][start_x] + 1
                q.put([yy, xx])
ans_list = []
for i in range(h):
    ans_list.extend(a[i])
dot_num = ans_list.count(".")
last_num = ans_list[-1]
if last_num != "#":
    if h*w == dot_num + last_num+1:
        ans = "Possible"
    else:
        ans = "Impossible"
else:
    ans = "Impossible"
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
A=[input() for i in range(h)]
LR=[]
for i in range(h):
  l=A[i].find("#")
  r=A[i].rfind("#")
  LR.append([l,r])
ans=0
for i in range(1,h):
  if LR[i-1][1]==LR[i][0]:
    ans+=1
print("Possible" if ans==h-1 else "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())
cnt = 0
for i in range(h):
    A = list(input())
    cnt += A.count('#')
if cnt == h+w-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
r = 0
for i in range(h):
    s = input()
    a = 0
    for j in range(w):
        if s[j] == "#":
            if j < r:
                print("Impossible")
                exit()
            else:
                a = j
        else:
            continue
    r = a

print("Possible")

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr=[input() for _ in range(n)]
for i in range(n-1):
  if (m-1)-arr[i][::-1].index('#')>arr[i+1].index('#'):
    print('Impossible')
    break
else:
  print('Possible')