Problem:


Score : 200 points

Problem Statement

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

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

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

Constraints

2 \leq H, W \leq 8

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

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

Input

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

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

Output

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

Sample Input 1

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

Sample Output 1

Possible

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

Sample Input 2

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

Sample Output 2

Impossible

Sample Input 3

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

Sample Output 3

Impossible



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


Sample output:
Possible

Submission status: Accepted

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


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

x, y = 0, 0

while y != H - 1 or x != W - 1:
    A[y][x] = '.'
    dy, dx = min(y + 1, H - 1), x
    ry, rx = y, min(x + 1, W - 1)
    if A[dy][dx] == '#':
        y, x = dy, dx
    elif A[ry][rx] == '#':
        y, x = ry, rx
    else:
        # print(A)
        print('Impossible')
        break
else:
    A[H - 1][W - 1] = '.'
    if any('#' in a for a in A) is True:
        print('Impossible')
    else:
        print('Possible')

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[list(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:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
H,W=H-1,W-1
if not (A[0][0]==A[-1][-1]=="#"):
    print("Impossible")
    exit()

h=0
w=0
while H>h or W>w:
    if H>h and W>w:
        if A[h+1][w]=="#" and  [1 for w_ in range(w+1,W+1) if A[h][w_]=="#"] or A[h][w+1]=="#" and  [1 for h_ in range(h+1,H+1) if A[h_][w]=="#"]:
            print("Impossible")
            exit()
        elif A[h+1][w]=="#":
            h+=1
        elif A[h][w+1]=="#":
            w+=1
        else:
            print("Impossible")
            exit()
    elif H>h and A[h+1][w]=="#":
        h+=1
    elif W>w and A[h][w+1]=="#":
        w+=1
    else:
        print("Impossible")
        exit()

print("Possible")

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
prev=0
for i in range(H):
  s=input()
  id = s.index("#")
  if id >= prev:
    flag=False
    prev = W-1 - s[::-1].index("#")
    for j in range(id,W):
      if flag and s[j]=="#":
        print("Impossible")
        exit(0)
      if s[j]==".":
        flag=True
  else:
    print("Impossible")
    exit(0)
print("Possible")

Submission status: Accepted

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

A = [[0]*(W) for j in range(H+1)]

for i in range (H):
    A[i]=list(input()+".")

i=0
j=0
A[0][0]=0
while(True):
    if((i==(H-1))and(j==(W-1))):
        for k in range(H):
            if("#" in A[k]):
                print("Impossible")
                exit()
        print("Possible")
        exit()
    if(A[i+1][j]=="#"):
        A[i+1][j]=0
        i+=1
    elif(A[i][j+1]=="#"):
        A[i][j+1]=0
        j+=1
    else:
        print("Impossible")
        exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
C=[input() for i in range(H)]
F=[[0 for i in range(W)] for j in range(H)]
cc=0
for i in range(H):
    cc+=list(C[i]).count('#')
C[0]='s'+C[0][1:]
C[-1]=C[-1][:-1]+'g'
for i in range(H):
	if('s' in C[i]):
		home_y=i
		home_x=C[i].index('s')
	if('g' in C[i]):
		store_y=i
		store_x=C[i].index('g')

stack=[[home_x,home_y]]

def check(x,y):
	if(x<0 or x>=W or y<0 or y>=H):
		return 0
	if(C[y][x]=='.'):
		return 0
	if(F[y][x]==1):
		return 0
	return 1

while(len(stack)!=0):
    x,y=stack.pop()
    F[y][x]=1
    if(check(x+1,y)):
        stack.append([x+1,y])
    #if(check(x-1,y)):
        #stack.append([x-1,y])
    if(check(x,y+1)):
        stack.append([x,y+1])
    #if(check(x,y-1)):
        #stack.append([x,y-1])
    #print(stack)

if(F[store_y][store_x]==1) and cc==H+W-1:
	print('Possible')
else:
	print('Impossible')
#print(F)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*-coding: utf-8 -*-
def check(A, h, w):
    cnt = 0
    if A[h-1][w] == "#":
        cnt += 1
    if A[h][w-1] == "#":
        cnt += 1
    if A[h][w+1] == "#":
        cnt += 1
    if A[h+1][w] == "#":
        cnt += 1
    return cnt

def main():
    H, W = map(int, input().split())
    A = ["." * (W+2)]
    for i in range(H):
        A.append("." + input() + ".")
    A.append("." * (W + 2))
    #print(A)
    ans = "Possible"
    for w in range(1, W+1):
        for h in range(1, H+1):
            if A[h][w] == "#":
                if w == h == 1:
                    if check(A, h, w) != 1:
                        ans = "Impossible"
                elif h == H and w == W:
                    if check(A, h, w) != 1:
                        ans = "Impossible"
                elif check(A, h, w) == 2:
                    if A[h-1][w] == A[h+1][w] == "#" and A[h][w-1] == A[h][w+1] == ".":     # 直線(縦)
                        pass
                    elif A[h-1][w] == A[h+1][w] == "." and A[h][w-1] == A[h][w+1] == "#":   # 直線(横)
                        pass
                    elif A[h-1][w] == A[h][w+1] == "#" and A[h+1][w] == A[h][w-1] == ".":   # L字
                        pass
                    elif A[h+1][w] == A[h][w-1] == "#" and A[h-1][w] == A[h][w+1] == ".":   # L時
                        pass
                    else:
                        ans = "Impossible"
                else:
                    ans = "Impossible"
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

H, W = list(map(int, input().split()))
a_table = []

for _ in range(H):
    a_list = list(input())
    a_table.append(a_list)

if a_table[0][0] != "#" or a_table[H - 1][W - 1] != "#":
    is_ok = False
else:
    # 連結箇所のチェック
    section_list = []
    is_ok = True
    for j in range(H):
        exist_section = False
        end_section = False
        start_idx = None
        end_idx = None
        for i in range(W):
            if a_table[j][i] == "#":
                if end_section:
                    # 連結箇所が複数あるのでアウト
                    is_ok = False
                    break
                elif exist_section:
                    # 連続した'#'
                    continue
                else:
                    # 最初の'#'
                    exist_section = True
                    start_idx = i
            else:
                if exist_section and (not end_section):
                    end_section = True
                    end_idx = i - 1
                    section_list.append((start_idx, end_idx))
                else:
                    # 連結部分終了後の'.' または 連結部分開始前の'.'
                    continue

        if exist_section and (not end_section):
            end_idx = W - 1
            section_list.append((start_idx, end_idx))
        elif not exist_section:
            is_ok = False

        if is_ok:
            if j != 0:
                if section_list[-2][1] != section_list[-1][0]:
                    is_ok = False

        if not is_ok:
            break

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

Submission status: Accepted

Solution code:
def main():
    n,m = map(int,input().split())
    maze=[]
    for _ in range(n):
        maze.append(list(input()))
    cnt=0
    for i in range(n):
        for j in range(m):
            if maze[i][j]=="#":
                cnt+=1
    if cnt==n+m-1:print("Possible")
    else:print("Impossible")
    
main()

Submission status: Accepted

Solution code:
import sys
import os

H, W = map(int,input().split())
cntS = 0
for i in range(H):
    cntS += list(input()).count("#")

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

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

cnh = 0
cnb = 0
for i in range(h):
    s = input()
    for j in range(w):
        if(s[j]=='#'):
            cnh +=1
        else:
            cnb+=1
            
ch = 1
if( cnh == h+w-1):
    ch = 1
else:
    ch = 0

    
if(ch==1):
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
g = [['.'] * (w+2) for i in range(h+2)]
ss = set() #'#'のset
for i in range(h):
  g[i+1][1:-1] = list(input())
  for j in range(w):
    if g[i+1][j+1] == '#':
      ss.add((i+1,j+1))
if g[1][1] == '.':
  print('Impossible')
  exit()
cur = (1,1)
ts = set() #通った点のset
ts.add(cur)
while cur != (h,w):
  if g[cur[0]+1][cur[1]] == '#':
    cur = (cur[0]+1,cur[1])
    ts.add(cur)
  elif g[cur[0]][cur[1]+1] == '#':
    cur = (cur[0],cur[1]+1)
    ts.add(cur)
  else:
    print('Impossible')
    exit()
if ts == ss:
  print('Possible')
else:
  print('Impossible')

Submission status: Accepted

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


def dfs(x, y):
    A[x][y] = '.'

    if x == h-1 and y == w-1:
        return
    elif x+1 < h and A[x+1][y] == '#':
        dfs(x+1, y)
    elif y+1 < w and A[x][y+1] == '#':
        dfs(x, y+1)
    else:
        return


dfs(0, 0)
if A == [['.'] * w] * h:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
r=[]
for i in range(h):
    r.append(list(input()))
t=[]
for i in range(h):
    for j in range(w):
        if r[i][j]=='#':
            t.append([i,j])
op=[[[0,0]]]
for i in range(h+w-2):
    tmp=[]
    for j in op:
        tmp.append(j+[[j[-1][0]+1,j[-1][1]]])
        tmp.append(j+[[j[-1][0],j[-1][1]+1]])
    op=tmp
for i in op:
    if sorted(i)==sorted(t):
        print('Possible')
        exit()
print('Impossible')

Submission status: Accepted

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

here = 0
for i in A:
    if here != i.find('#'):
        print('Impossible')
        exit()
    else:
        here = i.rfind('#')
else:
    print('Possible')

Submission status: Accepted

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

def bfs(y,x):
    a[y][x]='.'
    
    if y+1<h and x+1<w:
        if a[y+1][x]=='#' :
            bfs(y+1,x)
        elif a[y][x+1]=='#':
            bfs(y,x+1)
    elif x+1<w:
        if a[y][x+1]=='#':
            bfs(y,x+1)
    elif y+1<h:
        if a[y+1][x]=='#':
            bfs(y+1,x)
    
bfs(0,0)

ans='Possible'
for i in a:
    if '#' in i:
        ans='Impossible'
        
print(ans)

Submission status: Accepted

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

grid = [[0] for h in range(H)]
#print(grid)
for h in range(H):
    line = list(input())
    grid[h] = line

last = 0
for h in range(H):
    if '#' not in grid[h]:
        print('Impossible')
        sys.exit()
    for w in range(last, W - 1):
        if grid[h][w] == '.' and grid[h][w + 1] == '#':
            print('Impossible')
            sys.exit()
    for w in range(W):
        if grid[h][w] == '#' and w < last:
            print('Impossible')
            sys.exit()
        elif grid[h][w] == '#' and w >= last:
            last = w
print('Possible')

Submission status: Accepted

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

Submission status: Accepted

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

# print(A)

def a():
    c = -1
    for i in range(len(A)):
        c += A[i].count("#")
    
    s = [0, 0]
    while s != [h-1, w-1]:
        # print(s)
        if s[1]+1 < w and A[s[0]][s[1]+1] == "#":
            s[1] += 1
            c -= 1
        elif s[0]+1 < h and A[s[0]+1][s[1]] == "#":
            s[0] += 1
            c -= 1
        else:
            return "Impossible"
    if c == 0:
        return "Possible"
    else:
        return "Impossible"

print(a())

Submission status: Accepted

Solution code:

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

num = 0

for i in range(H):

    A = input()

    for a in A:

        if a == "#":
            num += 1

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

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]
    cnt = 0
    for i in range(h):
        cnt += a[i].count("#")
    print("Possible" if cnt == (h + w - 1) else "Impossible")


if __name__ == '__main__':
    slove()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[]
point=0
for _ in range(h):
	x=input()
	a.append(x)
	point+=x.count("#")
cnt=[[10**10 for _ in range(w)] for _ in range(h)]
for i in range(h):
	for j in range(w):
		if a[i][j]==".":
			cnt[i][j]="."
cnt[0][0]=0
lis=[[0,0]]#tate yoko
p=1
while len(lis)!=0:
	x=list()
	for _ in range(len(lis)):
		k=lis.pop(0)
		if k[0]!=0:
			if cnt[k[0]-1][k[1]]==10**10:
				cnt[k[0]-1][k[1]]=p
				x.append([k[0]-1,k[1]])
		if k[1]!=0:
			if cnt[k[0]][k[1]-1]==10**10:
				cnt[k[0]][k[1]-1]=p
				x.append([k[0],k[1]-1])
		if k[0]!=h-1:
			if cnt[k[0]+1][k[1]]==10**10:
				cnt[k[0]+1][k[1]]=p
				x.append([k[0]+1,k[1]])
		if k[1]!=w-1:
			if cnt[k[0]][k[1]+1]==10**10:
				cnt[k[0]][k[1]+1]=p
				x.append([k[0],k[1]+1])
	lis=x
	p+=1
if cnt[-1][-1]==h+w-2==point-1:
	print("Possible")
else:
	print("Impossible")

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
S = [input() for _ in range(H)]
endSh = 0
for i in S:
  startSh = i.find("#")
  if startSh != endSh:
    print("Impossible")
    exit()
  endSh = i.rfind("#")
print("Possible")

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 = [input() for _ in range(H)]

confilm = [[False] * W for _ in range(H)]
confilm[0][0] = True

nH, nW = 0, 0
while True:
    isMoved = False
    while nW < W - 1 and A[nH][nW + 1] == '#':
        nW += 1
        confilm[nH][nW] = True
        isMoved = True
    while nH < H - 1 and A[nH + 1][nW] == '#':
        nH += 1
        confilm[nH][nW] = True
        isMoved = True

    if not isMoved:
        break

for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            if confilm[h][w]:
                continue
            else:
                print('Impossible')
                exit()
        else:
            if confilm[h][w]:
                print('Impossible')
                exit()
            else:
                continue

print('Possible')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = list(map(int, sys.stdin.readline().split()))
A = [list(sys.stdin.readline().rstrip()) for _ in range(H)]


def ok(h, w):
    return 0 <= h < H and 0 <= w < W


def dfs(h, w):
    A[h][w] = '.'
    dh = [0, 1, 0, -1]
    dw = [1, 0, -1, 0]
    cnt = 0
    for i, j in zip(dh, dw):
        cnt += ok(h + i, w + j) and A[h + i][w + j] == '#'
    if cnt == 1:
        for i, j in zip(dh, dw):
            if ok(h + i, w + j) and A[h + i][w + j] == '#' and i >= 0 and j >= 0:
                return dfs(h + i, w + j)
    return cnt == 0 and h == H - 1 and w == W - 1


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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
b=[["."]*w for _ in range(h)]
b[0][0]="#"
now=[0,0]
for i in range(h+w):
    if now[1]<w-1:
        if a[now[0]][now[1]+1]=="#":
            now[1]+=1
            b[now[0]][now[1]]="#"
    if now[0]<h-1:         
        if a[now[0]+1][now[1]]=="#":
            now[0]+=1
            b[now[0]][now[1]]="#"
            
print("Impossible" if a!=b else "Possible")

Submission status: Accepted

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

for h in range(H):
  for w in range(W):
    flag1 = 0
    flag2 = 0
    if grid[h][w] == "#":
      if 0 <= h-1 < H:
        if grid[h-1][w] == "#":
          flag1 += 1
      if 0 <= w-1 < W:
        if grid[h][w-1] == "#":
          flag1 += 1
      if 0 <= h+1 < H:
        if grid[h+1][w] == "#":
          flag2 += 1
      if 0 <= w+1 < W:
        if grid[h][w+1] == "#":
          flag2 += 1

      if (h == 0 and w == 0):
        if flag1 == 0 and flag2 == 1:
          continue
        else:
          print("Impossible")
          exit()
      if (h == H-1 and w == W-1):
        if flag1 == 1 and flag2 == 0:
          continue
        else:
          print("Impossible")
          exit()
      else:
        if flag1 == 1 and flag2 == 1:
          continue
        else:
          print("Impossible")
          exit()
else:
  print("Possible")

Submission status: Accepted

Solution code:
# AGC007A - Shik and Stone
def main():
    H, W, *A = open(0).read().split()
    H, W = int(H), int(W)
    flg = ("".join(A)).count("#") == H + W - 1
    print("Possible" if flg else "Impossible")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    a = [input().strip() for i in range(H)]
    check = [[False] * W for i in range(H)]
    
    x, y = 0, 0
    check[y][x] = True
    while True:
        fin = True
        for nx, ny in [(x+1, y), (x, y+1)]:
            if 0 <= nx and nx < W and 0 <= ny and ny < H:
                if a[ny][nx] == "#":
                    check[ny][nx] = True
                    fin = False
                    x, y = nx, ny
                    break
        if fin:
            break
    
    ok = False
    if x == W-1 and y == H-1:
        ok = True
        for i in range(H):
            for j in range(W):
                if a[i][j] == "#" and not check[i][j]:
                    ok = False
                    break
            if not ok:
                break

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

def main():
    H,_ = map(int, input().split())
    a = input().strip()
    for _ in range(H-1):
        b = input().strip()
        if a.rfind("#") > b.find("#"):
            print("Impossible")
            return
        a = b
    print("Possible")

if __name__ == '__main__':
    main()

Submission status: Accepted

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

prev_left = 0
prev_right = 0

for i in range(H):
    left = A[i].find('#')
    right = A[i].rfind('#')
    if prev_right == left:
        prev_left = left
        prev_right = right
    elif right == W-1:
        right = W
        break
    elif prev_left == left and prev_right == right:
        break

if right == 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):
  As = input()
  A.append(As)
  c += As.count("#")
if c != H+W-1:
  print("Impossible")
  exit()
ok = True
i, j = (0, 0)
for k in range(H+W-2):
  fR = j+1 < W and A[i][j+1] == "#"
  fD = i+1 < H and A[i+1][j] == "#"
  if not fR ^ fD:
    ok = False
    break
  if fR:
    j += 1
  if fD:
    i += 1
if ok:
  print("Possible")
else:
  print("Impossible")

Submission status: Accepted

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

count=0

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

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

Submission status: Accepted

Solution code:
H,W=map(int,input().split());print(["Imp","P"][H+W-1==sum(input().count("#")for _ in range(H))]+"ossible")

Submission status: Accepted

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

sw=0
for i in range(H):
  tmp=0
  for j in range(W-1):
    if A[i][j]=="#" and A[i][j+1]==".":
      tmp=1
    if tmp==1 and A[i][j]=="." and A[i][j+1]=="#":
      sw=1
#print(sw)

if sw==1:
  print("Impossible")
else:
  l=[]
  r=[]
  for i in range(H):
    ll=0
    for j in range(W-1):
      if A[i][j]=="." and A[i][j+1]=="#":
        ll=j+1
        break
    l.append(ll)
    
    rr=W-1
    for j in range(W-1):
      if A[i][j]=="#" and A[i][j+1]==".":
        rr=j
        break
    r.append(rr)
#  print(l)
#  print(r)

  sw2=0
  for i in range(len(r)-1):
    if r[i]!=l[i+1]:
      sw2=1
  print("Impossible" if sw2==1 else "Possible")

Submission status: Accepted

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
H, W = map(int,input().split())
A = [list(input()) for _ in range(H)]
first = 0
a = A[0]
a = list(reversed(a))
last = W - a.index('#') -1
if A[0][first:last+1] == ['#'] * len(A[0][first:last+1]):
    pass
else:
    print('Impossible')
    exit()

for i in range(1, H):
    a = A[i]
    if last == a.index('#'):
        first = last
    else:
        print('Impossible')
        exit()
    a = list(reversed(a))
    last = W - a.index('#') - 1
    if A[i][first:last+1] == ['#'] * len(A[i][first:last+1]):
        pass
    else:
        print('Impossible')
        exit()
print('Possible')

Submission status: Accepted

Solution code:
h, w = list(map(int, input().split()))
a = [list(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:
  print("Possible")
else:
  print("Impossible")

Submission status: Accepted

Solution code:
def slove():
    import sys
    input = sys.stdin.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    cnt = 0
    for i in range(h):
        cnt += str(input().rstrip('\n')).count("#")
    print("Possible" if cnt == (h + w - 1) else "Impossible")


if __name__ == '__main__':
    slove()

Submission status: Accepted

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

Submission status: Accepted

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

black = sum(s.count('#') for s in a)
if black == h + w - 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

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

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

Submission status: Accepted

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)
            break
    count += 1
    if (W + H - 2) < count:
        print("Impossible")
        exit()

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: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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 LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    h,w = LI()
    a = SR(h)
    d = [(1,0),(0,1)]
    bfs = [[1]*w for i in range(h)]
    for y in range(h):
        for x in range(w):
            if a[y][x] == "#":
                bfs[y][x] = 0
                q = deque([(y,x)])
                while q:
                    i,j = q.popleft()
                    k = 0
                    for dy,dx in d:
                        ni = i+dy
                        nj = j+dx
                        if 0 <= ni < h and 0 <= nj < w:
                            if a[ni][nj] == "#":
                                if k:
                                    print("Impossible")
                                    return
                                k = 1
                                bfs[ni][nj] = 0
                                q.append((ni,nj))
                for i in range(h):
                    for j in range(w):
                        if a[i][j] == "#" and bfs[i][j]:
                            print("Impossible")
                            return
                print("Possible")
                return
    return

#B
def B():

    return

#C
def C():

    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    A()

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    A = []
    for _ 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:
        return "Possible"
    return "Impossible"

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = h + w - 1
x = 0
for _ in range(h):
	x += input().count("#")

if s == x:
	print("Possible")
else:
	print("Impossible")

Submission status: Accepted

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

s = 0
for i in range(H):
    A = list(input())
    s += A.count("#")

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#AGC002A
import sys

#n= int(input())
tmp = input().split()
h,w = list(map(lambda a: int(a), tmp))


map = [[0 for i in range(w+2)] for j in range(h+2)]

for i in range(0,h):
	hoge = input()
	for j in range(0,w):
		map[i+1][j+1]=hoge[j]

for i in range(1,h+1):
#	print(i)
	for j in range(1,w+1):
		if(map[i][j]=="#"):
			if(((map[i+1][j]=="#")and(map[i][j+1]=="#")) or ((map[i+1][j]==".")and(map[i][j+1]=="."))):
#				print("hoge {} {}".format(i,j))
				if(i!=h or j!=w):
					print("Impossible")
					sys.exit()
			if(((map[i-1][j]=="#")and(map[i][j-1]=="#")) or ((map[i-1][j]==".")and(map[i][j-1]=="."))):
#				print("hoga {} {}".format(i,j))
				if(i!=1 or j!=1):
					print("Impossible")
					sys.exit()
print("Possible")

#print(map)

Submission status: Accepted

Solution code:
def main():
    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")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
now = 0
for _ in range(H):
    A = input()
    for i in range(W):
        a = A[i]
        if a == "#":
            if i < now:
                print("Impossible")
                exit()
            now = i
        else:
            if i == now:
                print("Impossible")
                exit()
print("Possible")

Submission status: Accepted

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

YES = "Possible"  # type: str
NO = "Impossible"  # type: str


def main():
    h, w = map(int, input().split())
    c = sum([input().count("#") for _ in range(h)])
    print("Possible" if h + w - 1 == c else "Impossible")

if __name__ == '__main__':
    main()

Submission status: Accepted

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