Problem:


Score : 200 points

Problem Statement

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

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

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

Constraints

2 \leq H, W \leq 8

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

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

Input

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

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

Output

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

Sample Input 1

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

Sample Output 1

Possible

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

Sample Input 2

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

Sample Output 2

Impossible

Sample Input 3

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

Sample Output 3

Impossible



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


Sample output:
Possible

Submission status: Accepted

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

for i in range(H):
  inp = input()
  for j, square in enumerate(inp):
    if square == '#':
      matrix[i][j] = 1
      
hw = [0, 0]
matrix[0][0] = 0
while True:
  # 右に行ければ右に行く
  if hw[1] + 1 < W and matrix[hw[0]][hw[1] + 1] == 1:
    matrix[hw[0]][hw[1] + 1] = 0
    hw = [hw[0], hw[1] + 1]
    continue
  
  # 右に行けない時、下に行ければ下に行く
  if hw[0] + 1 < H and matrix[hw[0] + 1][hw[1]] == 1:
    matrix[hw[0] + 1][hw[1]] = 0
    hw = [hw[0] + 1, hw[1]]
    continue
  
  # 右にも下にも行けなくなったらbreak
  else:
    break
    
flag = sum([sum(row) for row in matrix])
print("Impossible" if flag else "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:
#coding:utf-8
H,W = map(int, input().split())
ans = 0
for h in range(H):
    S = str(input())
    for s in S:
        if s=="#":
            ans+=1
if (ans==H+W-1):
    print ("Possible")
else:
    print ("Impossible")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    H, W = LI()
    a = SR(H)
    for h in range(H):
        for w in range(W):
            if a[h][w] == "#":
                t = True
                for mh, mw in [[0, 1], [1, 0]]:
                    mh += h
                    mw += w
                    if 0 <= mh < H and 0 <= mw < W:
                        if a[mh][mw] == "#":
                            if t:
                                t &= False
                            else:
                                print("Impossible")
                                return
                if t and (h != H - 1 and w != W - 1):
                    print("Impossible")
                    return
                t = True
                for mh, mw in [[0, -1], [-1, 0]]:
                    mh += h
                    mw += w
                    if 0 <= mh < H and 0 <= mw < W:
                        if a[mh][mw] == "#":
                            if t:
                                t &= False
                            else:
                                print("Impossible")
                                return
                if t and (h != 0 and w != 0):
                    print("Impossible")
                    return
    print("Possible")
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    H,W = map(int,input().split())
    root = [list(str(input())) for _ in range(H)]
    _long = [[0 for _ in range(W)] for _ in range(H)]
    _long[0][0] = 1
    al = 0
    for i in range(H):
        for j in range(W):
            if root[i][j] == "#":
                al += 1
    
    if al != H+W-1:
        print("Impossible")
        exit()
    
    print("Possible")
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 右と下の両方に#があったら終了だしどちらにもなくても終了
# なんやこのクソみたいな実装は

h, w = map(int, input().split())
table = []
sharp = 0
for _ in range(h):
    get = input()
    table.append(get)
    sharp += get.count("#")

flag = False
pos = [0, 0]
path = 0
while True:
    if pos == [h - 1, w - 1]:
        path += 1
        flag = True
        break
    if h <= pos[0] or w <= pos[1]:
        break
    if (
        pos[0] < h - 1
        and pos[1] < w - 1
        and table[pos[0] + 1][pos[1]] == "#"
        and table[pos[0]][pos[1] + 1] == "#"
    ):
        break
    if pos[0] < h - 1 and pos[1] < w - 1 and table[pos[0] + 1][pos[1]] == "#":
        pos[0] += 1
        path += 1
        continue
    elif pos[0] < h - 1 and pos[1] < w - 1 and table[pos[0]][pos[1] + 1] == "#":
        pos[1] += 1
        path += 1
        continue
    if pos[0] == h - 1 and pos[1] < w - 1 and table[pos[0]][pos[1] + 1] == "#":
        pos[1] += 1
        path += 1
        continue
    elif pos[0] < h - 1 and pos[1] == w - 1 and table[pos[0] + 1][pos[1]] == "#":
        pos[0] += 1
        path += 1
        continue
    else:
        break

print("Possible" if flag and path == sharp else "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):
    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())
a = [list(input()) for _ in range(h)]


def dfs(x, y):
    if a[x][y] == '#':
        a[x][y] = '.'
    if 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)


dfs(0, 0)
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            print('Impossible')
            exit()
print('Possible')

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
d=[[1,0],[0,1]]
def dfs(x,y):
    a[x][y]="."
    for i in d:
        if 0<=x+i[0]<h and 0<=y+i[1]<w and a[x+i[0]][y+i[1]]=="#":
            dfs(x+i[0],y+i[1])
            break
dfs(0,0)
# for i in range(h):
#     print(a[i])
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            print("Impossible")
            exit()
print("Possible")

Submission status: Accepted

Solution code:
import sys
def routeSearch(x,y):
	a[y][x]='@'
	if(x<w-1 and a[y][x+1]=='#'):
		routeSearch(x+1,y)
	elif(y<h-1 and a[y+1][x]=='#'):
		routeSearch(x,y+1)
h,w=map(int,input().split())

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

routeSearch(0,0)
for i in range(h):
	if('#' in a[i]):
		print("Impossible")
		sys.exit()

print("Possible")

Submission status: Accepted

Solution code:
# coding: utf-8
import numpy as np
H, W = map(int, input().split())
board = []
tb = [[False] * W] * H
tb = np.array(tb)
cnt = 0
for i in range(H):
    tmp = list(input())
    for j in range(W):
        if tmp[j] == "#":
            cnt += 1
            if "s" not in globals():
                s = [i, j]
    board.append(tmp[:])
board = np.array(board)
tb[s[0], s[1]] = True
for i in range(H):
    for j in range(s[1], W):
        if board[i][j] == "#":
            s[1] = j
            tb[s[0], s[1]] = True
    if s[0] < H - 1:
        s[0] += 1
    if board[s[0], s[1]] == "#":
        tb[s[0], s[1]] = True
    else:
        break
print("Possible" if cnt == np.sum(tb) else "Impossible")

Submission status: Accepted

Solution code:
def examA():
    H, W = LI()
    A = [SI() for _ in range(H)]
    cur = 0
    for i in range(H):
        for j in range(W):
            if A[i][j]=="#":
                cur +=1
    if cur==H+W-1:
        ans = "Possible"
    else:
        ans = "Impossible"
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examA()

Submission status: Accepted

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

H, W = map(int, readline().split())
G = sum(sum(1 if s == '#' else 0 for s in readline().strip()) for _ in range(H))
if G == H+W-1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[]
for i in range(h):
  x=input()
  a.append(x)
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:
# coding: utf-8
# Your code here!
n,m=map(int,input().split())
s = [list(input()) for i in range(n)]
cnt=0
for i in range(n):
    for j in range(m):
        if s[i][j]=='#':
            cnt+=1
if cnt>n+m-1:
    print('Impossible')
else:
    print('Possible')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

A = '.' * (W+2)
for _ in range(H):
    A += '.' + readline().rstrip().decode('utf-8') + '.'
A += '.' * (W+2)

start = 1 * (W+2) + 1
goal = H * (W+2) + W

v = start
fail = False
for _ in range(H+W-2):
    if A[v+1] == '#':
        v += 1
        continue
    elif A[v+W+2] == '#':
        v += (W+2)
        continue
    fail = True
    break

cnt = A.count('#')
bl = (cnt == H + W - 1) and (not fail)
answer = 'Possible' if bl else 'Impossible'
print(answer)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = [input().strip() for _ in range(H)]
cnt_row = 0
for i in range(H):
    cnt_row += A[i].count("#")-1
cnt_col = 0
for j in range(W):
    cnt = 0
    for i in range(H):
        if A[i][j]==("#"):
            cnt += 1
    cnt_col += cnt-1
if cnt_row==W-1 and cnt_col==H-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,m=map(int,input().split())
s = [list(input()) for i in range(n)]
cnt=0
for i in range(n):
    for j in range(m):
        if s[i][j]=='#':
            cnt+=1
if cnt>n+m-1:
    print('Impossible')
else:
    print('Possible')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import copy
from collections import deque
H,W = map(int,input().split())
A = []
for i in range(H):
    A.append(list(input()))
now = [0,0]
goal = [H-1,W-1]
x1 = [0,1]
y1 = [1,0]
alr = copy.deepcopy(A)
alr[0][0] = 1
que = deque()
que.append(now)
while que:
    q = que.popleft()
    for i in range(2):
        if 0 <= q[0]+x1[i] <= H-1 and 0 <= q[1]+y1[i] <= W-1 and alr[q[0]+x1[i]][q[1]+y1[i]] == '#':
            alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] +1
            que.append([q[0]+x1[i],q[1]+y1[i]])
if alr[-1][-1] != '#':
    num = alr[-1][-1]
    count = {}
    flag = True
    for i in range(1,num+1):
        count[i] = 0
    for i in range(H):
        for j in range(1,num+1):
            count[j] += alr[i].count(j)
        if '#' in alr[i]:
            flag = False
    
    for i,v in count.items():
        if v != 1:
            flag = False
    if flag:
        print('Possible')
    else:
        print('Impossible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
bd = [list("."+input()+".") for i in range(h)]
bd.insert(0,["."]*(w+2))
bd.append(["."]*(w+2))
stack=[(1,1)]
while(stack):
  i,j=stack.pop()
  if i == h and j == w:
    bd[i][j]="."
    break
  if bd[i+1][j] == bd[i][j+1]:
    print("Impossible")
    exit()
  if bd[i-1][j] == "#" or bd[i][j-1] == "#":
    print("Impossible")
    exit()
  if bd[i+1][j] == "#":
    stack.append((i+1,j))
  if bd[i][j+1] == "#":
    stack.append((i,j+1))
  bd[i][j] = "."
if bd == [["." for i in range(w+2)] for j in range(h+2)]:
  print("Possible")
else:
  print("Impossible")

Submission status: Accepted

Solution code:
from sys import exit, stdin
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
S = [list(stdin.readline().rstrip()) for _ in range(H)]
cnt = 0
for l in S:
    cnt += l.count('#')
if cnt == 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:
from collections import deque

h,w=map(int,input().split())
l=[]
c=0
for i in range(h):
 t_l=list(input())
 c+=t_l.count('#')
 l.append(t_l)

sy,sx=0,0
gy,gx=h-1,w-1

dist=[[-1]*w for i in range(h)]
dist[0][0]=0

que=deque()
que.append((sy,sx))

while que:
 y,x=que.popleft()

 if y==gy and x==gx and dist[gy][gx]==c-1:
  print('Possible')
  exit()

 for dy,dx in [[1,0],[0,1]]:
  ny=y+dy
  nx=x+dx
  if ny<=h-1 and nx<=w-1 and l[ny][nx]=='#' and dist[ny][nx]==-1:
   que.append((ny,nx))
   l[ny][nx]=='.'
   dist[ny][nx]=dist[y][x]+1

print('Impossible')

Submission status: Accepted

Solution code:
import sys
import os
if sys.platform=="darwin":
   base = os.path.dirname(os.path.abspath(__file__))
   name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
   #print(name)
   sys.stdin = open(name)

h,w = map(int, input().split())
l = [str(input()) for _ in range(h)]

#print(l)
ans = 0
for i in range(h):
   ans = ans + l[i].count(".")

#print(ans)

if ans == (h-1)*(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)]
cnt=0
for i in range(h):
    cnt +=A[i].count("#")
print("Possible" if cnt==h+w-1 else "Impossible")

Submission status: Accepted

Solution code:
def flatten_2d(data):
    for block in data:
        for elem in block:
            yield elem
            
h,w = map(int,input().split())

List=[input() for i in range(h)]

#print(List)

a = list(flatten_2d(List))

#print(list(flatten_2d(List)))


if a.count("#")==(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)]

ans = "Possible"
now = 0
for i in range(H):
    nxt = now
    for j in range(W):
        if j < now and A[i][j] == '#':
            ans = "Impossible"
        elif j == now:
            if A[i][j] == '.':
                ans = "Impossible"
        else:
            if j == nxt+1 and A[i][j] == '#':
                nxt = j
            elif A[i][j] == '#':
                ans = "Impossible"
    now = nxt

print(ans)

Submission status: Accepted

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

#print(a)

x = 0
y = 0
a[x][y] = '.'

while  x < h and y < w:
    #print(x, y)
    if x < h-1:
        if a[x+1][y] == '#':
            x += 1
            a[x][y] = '.'
            continue
    if y < w-1:
        if a[x][y+1] == '#':
            y += 1
            a[x][y] = '.'
            continue
    if x == h - 1 and y == w - 1:
        break
    else:
        print('Impossible')
        exit()

#for x in a: print(x)

for b in a:
    if '#' in b:
        print('Impossible')
        exit()


print('Possible')

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A =[[0]*(W+2)] + [[0] + [0 if s=='.' else 1 for s in input()] + [0]  for _ in range(H)] + [[0]*(W+2)]
pos = [1,1]
A[1][1] = 0
while pos != [W,H]:
  if pos[1]<=H and A[pos[1]+1][pos[0]] == 1:
    A[pos[1]+1][pos[0]] = 0
    pos = [pos[0],pos[1]+1]
  elif pos[0]<=W and A[pos[1]][pos[0]+1] == 1:
    A[pos[1]][pos[0]+1] = 0
    pos = [pos[0]+1,pos[1]]
  else:
    print('Impossible')
    exit()
if sum([sum(row) for row in A]) == 0: print('Possible')
else:print('Impossible')

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np


def isPossible(grid):
    v = deque([[0, 0]])

    while v:
        x, y = v.popleft()
        grid[x][y] = 0
        if grid[x][y + 1]:
            v.append([x, y + 1])
            continue
        elif grid[x + 1][y]:
            v.append([x + 1, y])
            continue

    if grid.sum() == 0:
        return True
    else:
        return False


if __name__ == "__main__":
    h, w = map(int, input().split())
    grid = [[0 if i == "." else 1 for i in input()+"."] for _ in range(h)]
    grid.append([0]*(w+1))
    grid = np.array(grid)
    if isPossible(grid):
        ans = "Possible"
    else:
        ans = "Impossible"
    print(ans)

Submission status: Accepted

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

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

y, x = 0, 0
cnt -= 1
while not (y == H - 1 and x == W - 1) :
  if x + 1 < W and A[y][x + 1] == '#' :
    cnt -= 1
    x += 1
    continue
  
  if y + 1 < H and A[y + 1][x] == '#' :
    cnt -= 1
    y += 1
    continue

  break

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
cnt = 0
for i in range(a):
    s = input()
    cnt += s.count("#")

if cnt == a+b-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
cnt = 0
for i in range(a):
    s = input()
    cnt += s.count("#")

if cnt == a+b-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
from collections import deque

h,w=map(int,input().split())
a=[list(input()) for j in range(h)]
x=[0,0]#xが"#"を仮定

def next_point_is_ok1(i,j):
    global a,h
    if i < h-1:
        return a[i+1][j]=="#"
    else:
        return False

def next_point_is_ok2(i,j):
    global a,w
    if j < w-1:
        return a[i][j+1]=="#"
    else:
        return False


def next_points():
    global x,a
    #print(x)
    if x==[h-1,w-1]:
        #print(0)
        if a == [["." for i in range(w)] for j in range(h)]:
            print("Possible")
        else:
            print("Impossible")
    elif next_point_is_ok1(x[0],x[1]):
        #print(1)
        x[0]+=1
        a[x[0]][x[1]]="."
        next_points()
    elif next_point_is_ok2(x[0],x[1]):
        #print(2)
        x[1]+=1
        a[x[0]][x[1]]="."
        next_points()
    else:
        #print(3)
        print("Impossible")

#print(a)
if a[0][0]==".":
    print("Impossible")
else:
    a[0][0]="."
    next_points()

Submission status: Accepted

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

sharp = 0
for line in graph:
    sharp += line.count("#")
if sharp == H + W - 1:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
from sys import stdin

h,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [stdin.readline().rstrip() for _ in range(h)]

now = 0

for i in range(h):
    if "#" in li[i][:now]:
        print("Impossible")
        exit()
    for j in range(now,w-1):
        if li[i][j] == "#" and li[i][j+1] == ".":
            now = j
        if li[i][w-2] == "#" and li[i][w-1] == "#":
            now = w-1
    if now <= 3:
        if "#" in li[i][now+1:]:
            print("Impossible")
            exit()
print("Possible")

Submission status: Accepted

Solution code:
from sys import stdin

h,w = [int(x) for x in stdin.readline().rstrip().split()]
li = [stdin.readline().rstrip() for _ in range(h)]

now = 0

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

Submission status: Accepted

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

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

def dfs(i=0, j=0):
    if not (0 <= i < h and 0 <= j < w):
        return
    elif a[i][j] == ".":
        return
    elif b[i][j]:
        return
    else:
        b[i][j] = 1
        dfs(i+1, j)
        dfs(i, j+1)
        for i in range(h):
            for j in range(w):
                if a[i][j] == "#" and b[i][j] == 0:
                    print("Impossible")
                    exit()
        print("Possible")
        exit()

dfs()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0
for i in range(H):
    a = input()
    z = Counter(a)
    ans += z["#"]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())

l=[]
for _ in range(H):
    l.append(list(input()))

def dfs(h,w):
    l[h][w]="!"
    #print(l)
    #print(h,w,l[h][w])
    if h==H-1 and w==W-1:
        for item in l:
            if "#" in item:
                print("Impossible")
                exit()
        print("Possible")
        exit()
    elif (l[h-1][w]=="#" if h>0 else False) or (l[h][w-1]=="#" if w>0 else False):
        print("Impossible")
        exit()
    if h<H-1:
        if l[h+1][w]=="#":
            dfs(h+1,w)
    if w<W-1:
        if l[h][w+1]=="#":
            dfs(h,w+1)
    l[h][w]="#"
    
    return "Impossible"

print(dfs(0,0))

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
gy,gx=H-1,W-1
grid=["" for i in range(H)]
touched=0
for i in range(H):
  grid[i]=input()
  touched+=grid[i].count("#")

print(("Imp","P")[touched==H+W-1]+"ossible")

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
gy,gx=H-1,W-1
grid=["" for i in range(H)]
touched=0
for i in range(H):
  grid[i]=input()
  touched+=grid[i].count("#")

if touched!=(H+W-1):
  print("Impossible")
  exit(0)

stack=[]
stack.append([0,0])
goal=False
while stack:
  v=stack.pop()
  y=v[0]
  x=v[1]
  if y==gy and x==gx:
    goal=True
    break
  if grid[y][x]==".":
    continue
  if y+1<H:
    stack.append([y+1,x])
  if x+1<W:
    stack.append([y,x+1])
    
print(("Impossible","Possible")[goal])

Submission status: Accepted

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

visited = [[False for j in range(W)] for i in range(H)]
visited[0][0] = True

x,y = 0,0

while not (x==H-1 and y==W-1):
    if x<H-1 and A[x+1][y]=='#':
        x += 1
        visited[x][y] = True
    elif y<W-1 and A[x][y+1]=='#':
        y += 1
        visited[x][y] = True
    else:
        break
ans = True
for i in range(H):
    for j in range(W):
        if A[i][j] == '#' and not visited[i][j]:
            ans = False

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = rl()
A = [list(rs()) for _ in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            A[i][j] = 1
        else:
            A[i][j] = 0
    A[i].append(0)            
A.append([0] * (W + 1))
bool = True

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            if A[i+1][j] + A[i][j+1] != 1:
                bool = False
            continue
        if i == H - 1 and j == W - 1:
            if A[i-1][j] + A[i][j-1] != 1:
                bool = False
            continue
        if A[i][j] == 1:
            if A[i+1][j] + A[i][j+1] != 1:
                bool = False
            if A[i-1][j] + A[i][j-1] != 1:
                bool = False

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

Submission status: Accepted

Solution code:
# 2019-11-26 01:21:13(JST)
import sys
import numpy as np 

def main():
    H, W = map(int, sys.stdin.readline().split())
    visited = np.array([sys.stdin.readline().rstrip() for _ in range(H)], dtype='U')

    if np.char.count(visited, '#').sum() == H + W - 1:
        ans = 'Possible'
    else:
        ans = 'Impossible'

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 2019-11-26 01:21:13(JST)
import sys
import numpy as np 

def main():
    H, W = map(int, sys.stdin.readline().split())
    visited = np.array([sys.stdin.readline().rstrip() + '.' for _ in range(H)], dtype='U')
    visited = np.append(visited, '.' * (W + 1))

    if np.char.count(visited, '#').sum() != H + W - 1:
        print('Impossible')
        sys.exit()
    
    h, w = 0, 0
    for _ in range(H + W - 2):
        if visited[h+1][w] == '#' and visited[h][w+1] == '.':
            h += 1
        elif visited[h+1][w] == '.' and visited[h][w+1] == '#':
            w += 1
        else:
            print('Impossible')

    print('Possible')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

x = 0
y = 0
ans = 'Possible'
a[0][0] = '.'
while True:
    if y < W - 1 and a[x][y + 1] == '#':
        y += 1
        a[x][y] = '.'
        continue
    elif x < H - 1 and a[x + 1][y] == '#':
        x += 1
        a[x][y] = '.'
        continue
    break

for i in range(H):
    if a[i].count('#') != 0:
        ans = 'Impossible'
        break
print(ans)

Submission status: Accepted

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)]
if s[0][0] != '#':
    print('Impossible')
    quit()
s[0][0] = '.'
for i in itertools.combinations(range(h+w-2),h-1):
    # print(i)
    cnt = [1] * (h+w-2)
    for l in range(h+w-2):
        if l in i:
            cnt[l] = 0 
    # print(cnt)
    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 cnt:
        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: Accepted

Solution code:
import sys


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

    hash = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                hash.append((h, w))

    if hash == []:
        print('Impossible')
        sys.exit()

    s = hash[0]

    nd = ((1, 0), (0, 1))

    q = [s]
    cnt = 1
    while q:
        x0, y0 = q[0]
        del q[0]
        for dx, dy in nd:
            x = x0 + dx
            y = y0 + dy
            if x < H and y < W:
                if A[x][y] == "#":
                    cnt += 1
                    q.append((x, y))
                    break

    if cnt == len(hash):
        print('Possible')
    else:
        print('Impossible')

main()

Submission status: Accepted

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

the_number_of_stones = 0

for i in range(h):
    the_number_of_stones += a[i].count('#')

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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
max_x = 0
max_y = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            if max_x > j or max_y > i:
                print('Impossible')
                exit()
            else:
                max_x = j
                max_y = i
print('Possible')

Submission status: Accepted

Solution code:
N, M = input().split()
c=0
for i in range(int(N)):
	a=list(input())
	for j in a:
		if j=="#":
			c+=1

if c==int(N)+int(M)-1:
	print("Possible")
else:
	print("Impossible")

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
A = []
c = 0
O = "ossible"
P = "P" + O
I = "Imp" + O

for i in range(H):
    a = input()
    A.append(a)
    c += a.count("#")

if H+W-1==c:
    print(P)
else:
    print(I)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
table = []
for i in range(h):
    table.append(list(input()))
poss = True
for i in range(h-1):
    for j in range(w-1):
        if table[i][j] == "#":
            if (table[i+1][j]=="#" and table[i][j+1]=="#") or (table[i+1][j]=="." and table[i][j+1]=="."):
                poss = False
for i in range(1, h):
    if table[i][w-2]=="#" and table[i-1][w-1]=="#":
        poss = False
for i in range(1, w):
    if table[h-1][i-1]=="#" and table[h-2][i]=="#":
        poss = False

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