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: Runtime Error

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

isExact = 'Possible'

i, j = 0, 0

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

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

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

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

print(isExact)

Submission status: Runtime Error

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

i = j = 0

passed = [[None] * W for _ in range(H)]

def dp(i, j):
    global H, W
    passed[i][j] = True
    if i == H - 1 and j == W - 1: return True
    #
    if i + 1 >= H:
        d = False
    else:
        d = (A[i + 1][j] == '#')
    #
    if j + 1 >= W:
        r = False
    else:
        r = (A[i][j + 1] == '#')
    #
    if d and not r:
        return dp(i + 1, j)
    elif not d and r:
        return dp(i, j + 1)
    else:
        return False

if dp(0, 0):
    ans = 'Possible'
    for i in range(H):
        for j in range(W):
            if not visited[i][j] and A[i][j] == '#':
                ans = 'Impossible'
    #
    print(ans)
else:
    print('Impossible')

Submission status: Runtime Error

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

for f in fields:
    cnt += f.count("#")
if cnt == H + W - 1: 
    print("Possible")
else:
    print("Impossible")

Submission status: Runtime Error

Solution code:
from collections import deque

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

total = sum([1 for a in A for s in a  if s=='#'])

que = deque([[0,0,1]])
while que:
    for x,y in [(1,0), (0,1)]:
        x_,y_,cnt = que.popleft()
        next_x, next_y = x_+x, y_+y
        if A[next_y][next_x] == '#':
            que.append([next_x,next_y,cnt+1])

print('Possible' if total == cnt else 'Impossible')

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
pos = [[0, 0]]
S = [input() for i in range(H)]
p = 1
def whiteout(Map, h, w):
  y = 0
  for i in range(h):
    for j in range(w):
      if Map[i][j] == '#':
        y += 1
  return y == 0

while pos != [H-1, W-1]:
  cnt = 0
  x, y = pos[0], pos[1]
  S[x] = S[x][:y] + '.' + S[x][y+1:]
  if x < H-1:
    if S[x+1][y] == '#':
      cnt += 1
      pos = [x+1, y]
  if y < W-1:
    if S[x][y+1] == '#':
      cnt += 1
      pos = [x, y+1]
  if cnt != 1:
    p = 0
    break
S[H-1] = S[H-1][:W-1] + '.'
if p == 1 and whiteout(S, H, W):
  print("Possible")
else:
  print("Impossible")

Submission status: Runtime Error

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

ans = "Impossible"
d = [(1, 0), (0, 1)]


def f(y, x):
    if y == H-1 and x == W-1:
        global ans
        ans = "Possible"
        return
    elif not (0 <= y < H and 0 <= x < W):
        return
    elif A[y][x] == ".":
        return
    
    f(y+1, x)
    f(y, x+1)


f(0, 0)
print(ans)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
num=0
s=[str(input()) for i in range(h):]
for i in range(h):
  num+=s[i].count("#")
if num>h+w-1:
  print("Impossible")
  exit()
print("Possible")

Submission status: Runtime Error

Solution code:
    maze = []
    h, w = map(int,input().split())
    for _ in range(h):
        maze.append(list(input()))
    #print(maze)
    x,y = 0,0
    while True:
        maze[y][x] = "."
        if x == w-1 and  y == h-1:
            break
        if x != w-1 and maze[y][x+1]== "#":
            x += 1
            continue
        if y != h-1 and maze[y+1][x]=="#":
            y += 1
            continue
        break
    from pprint import pprint
    #pprint(maze)
    f= True
    for i in range(h):
        if maze[i].count("#") != 0:
            f = False
    print("Impossible" if not f else "Possible")

Submission status: Runtime Error

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

al = []

for _ in range(h):
   a = list(input())
   al.append(a)

i,j = 0,0
while True:
    al[i][j] = "."
    if j + 1 < w and al[i][j+1] == "#":
        al[i][j+1] = "."
        j += 1
    elif i + 1 < h and al[i+1][j] == "#":
        al[i+1][j] = "."
        i += 1
    else:
        print("Impossible")
        exit()
    if j == w-1 and i == h-1:
        break

for i in range(h):
    for j in range(h):
        if al[i][j] == '#':
            print("Impossible")
            exit()
print("Possible")

Submission status: Runtime Error

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

dy = [0, 1]
dx = [1, 0]

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

def dfs(y, x):
    stack[y][x] = 1
    if x == w-1 and y == h-1:
        return
    for i in range(2):
        ny = y + dy[i]
        nx = x + dx[i] 
        if ny < 0 or ny >= h or nx < 0 or nx >= w:
            continue
        if a[ny][nx] == "#":
            dfs(ny, nx)
            break
    return

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

Submission status: Runtime Error

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

h, w = map(int, input().split())
table = []
for _ in range(h):
    table.append(input())

flag = False
pos = [0, 0]
while True:
    if pos == [h - 1, w - 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
        continue
    elif pos[0] < h - 1 and pos[1] < w - 1 and table[pos[0]][pos[1] + 1] == "#":
        pos[1] += 1
        continue
    if pos[0] == h - 1 and pos[1] < w - 1 and table[pos[0]][pos[1] + 1] == "#":
        pos[1] += 1
        continue
    elif pos[0] < h - 1 and pos[1] == w - 1 and table[pos[0] + 1][pos[0]] == "#":
        pos[0] += 1
        continue
    else:
        break

print("Possible" if flag else "Impossible")

Submission status: Runtime Error

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

h, w = map(int, input().split())
table = []
for _ in range(h):
    table.append(input())

flag = False
pos = [0, 0]
while True:
    if pos == [h - 1, w - 1]:
        flag = True
        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
        continue
    elif pos[0] < h - 1 and pos[1] < w - 1 and table[pos[0]][pos[1] + 1] == "#":
        pos[1] += 1
        continue
    if pos[0] == h - 1 and pos[1] < w - 1 and table[pos[0]][pos[1] + 1] == "#":
        pos[1] += 1
        continue
    elif pos[0] < h - 1 and pos[1] == w - 1 and table[pos[0] + 1][pos[0]] == "#":
        pos[0] += 1
        continue
    else:
        break

print("Possible" if flag else "Impossible")

Submission status: Runtime Error

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

for i in range(H):
    for j in range(W-1):
        if A[i][j] == "#":
            if A[i-1][j] != "#" and A[i+1][j+1] != "#":
                print("Impossible")
                exit()

print("Possible")

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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-1]=="#" and table[i-1][w]=="#":
        poss = False
for i in range(1, w):
    if table[h][i-1]=="#" and table[h-1][i]=="#":
        poss = False

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

Submission status: Runtime Error

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 = id
    for j in range(prev,W):
      if flag ans s[j]=="#":
        print("Impossible")
        exit(0)
      if s[j]==".":
        flag=True
print("Possible")

Submission status: Runtime Error

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
    for j in range(id,W):
      if flag ans s[j]=="#":
        print("Impossible")
        exit(0)
      if s[j]==".":
        flag=True
print("Possible")

Submission status: Runtime Error

Solution code:
h,w=map(int,input())
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: Runtime Error

Solution code:
n=int(input())
a=[i*30000+1 for i in range(n)]
b=[30000**2-i for i in a]
p=list(map(int,input().split()))
for i in range(n):
  a[p[i]-1]+=i
  b[p[i]-1]+=i
print(*a)
print(*b)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[i*40000 for i in range(n)]
b=[40000**2-i for i in a]
p=list(map(int,input().split()))
for i in range(n):
  a[p[i]]+=i
  b[p[i]]+=i
print(*a)
print(*b)

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

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
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:
  if '#' in a:
    x=0
print('Possible' if x==1 else 'Impossible')

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
d='.'*(w+2)
a=[d]
for _ in range(h):
  s='.'+input()+'.'
  a.append(s)
a.append(d)
x='Possible'
a[h][w+1]='#'
for i in range(1,w+1):
  for j in range(1,h+1):
    if a[j][i]=='#':
      if a[j][i+1]==a[j+1][i]:
        x='Impossible'
        break
print(x)

Submission status: Runtime Error

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

flag = False
for j in (itertools.product([0,1],repeat=int((H+W-2)/2))):
    route_flag = True
    right = 0
    down  = 0
    for k in j:
        if k == 1:
            right += 1
        else:
            down += 1
        if data[down][right] == ".":
            route_flag = False
    if route_flag:
        flag = True
    
if data[0][0] == ".":
    flag = False

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

Submission status: Runtime Error

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

flag = False
for j in (itertools.product([0,1],repeat=(H+W-2))):
    route_flag = True
    right = 0
    down  = 0
    for k in j:
        if k == 1:
            right += 1
        else:
            down += 1
        if data[down][right] == ".":
            route_flag = False
    if foute_flag:
        flag = True
    
if data[0][0] == ".":
    flag = False

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

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
G=[input()+"." for _ in range(4)]+["."*(W+1)]
p=[0,0]
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]]
    else:
        p=[p[0],p[1]+1]
else:
    print("Possible")

Submission status: Runtime Error

Solution code:
from operator import itemgetter
H,W=map(int,input().split())
A=[list([i for i in input()]) for i in range(H)]
B=[0]*H
C=[0]*W
for i in range(H):
    num=0
    for j in range(W):
        if A[i][j]=='#':
            num+=1
    B[i]=num
for j in range(W):
    num=0
    for i in range(H):
        if A[i][j]=='#':
            num+=1
    C[j]=num
L=[]
for i in range(H):
    for j in range(W):
        if B[i]>=2 and C[j]>=2 and A[i][j]=='#':
            L.append((i,j))
L=sorted(L,key=itemgetter(1))
L=sorted(L,key=itemgetter(0))
for i in range(len(L)-1):
    flag=True
    if i%2==0:
        if L[i][0]==L[i+1][0] and L[i][1]<L[i+1][1]:
            continue
        flag=False
    elif i%2==1:
        if L[i][1]==L[i+1][1] and L[i][0]<L[i+1][0]:
            continue
        flag=False
#print(L)
if flag:
    print('Possible')
if not flag:
    print('Imossible')

Submission status: Runtime Error

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

def dfs(x, y):
    d = [[0,1], [1,0]]
    num = 0
    for dx, dy in d:
        x += dx
        y += dy
        if A[y][x] == '#':
            num += 1
    if num != 1:
        return 'Impossible'
    else:
        for dx, dy in d:
            x += dx
            y += dy
            if A[y][x] == '#':
                dfs(x, y)

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

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
A = [input() +'.' for i in range(H)] + ['.' * (H+2)]
idxs = [[0, 0]]
route = 0
while len(idxs):
    y, x = idxs.pop(0)

    if y == H-1 and x == W-1 and A[y][x] == '#':
        route += 1
    if A[y+1][x] == '#':
        idxs.append([y+1, x])
    if A[y][x+1] == '#':
        idxs.append([y, x+1])
    if route > 1:
        break

if route == 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
A = [input() +'.' for i in range(H)] + ['.' * (H+2)]
idxs = [[0, 0]]
route = 0
while len(idxs):
    y, x = idxs.pop(0)

    if y == H-1 and x == W-1 and A[y][x] == '#':
        route += 1
    if A[y+1][x] == '#':
        idxs.append([y+1, x])
    if A[y][x+1] == '#':
        idxs.append([y, x+1])

if route == 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N=int(input())

p = list(map(int,input().split()))
q = [0 for i in range(N)]
for i in range(N):
    q[p[i]-1]=i
    
A = 0
B = 10**9+1
ans_a = []
ans_b = []
for i in range(N):
    A+=q[i]
    if i!=0:
        B-=q[i-1]
    A+=1
    B-=1
    ans_a.append(A)
    ans_b.append(B)
    
print(*ans_a)
print(*ans_b)

Submission status: Runtime Error

Solution code:
#AGC007 A
'''
問題
縦H行で横W列の盤面がある
コマははじめ左上隅のマスに置かれており，右下隅に移動した
駒は1マスずつ上下左右に動ける
駒が通ったことのあるマスが提示されるので，駒が常に右または下にしか動いていなかったどうか判定せよ
ただし通ったことのあるマスは'#',一度も通らなかったマスは'.'で与えられる

考察
各行0,1,...,i,...,H-1に対して'#'のマスが存在する範囲を[ai,bi]とする。ただし0<=ai<=bi<=W-1
このとき各0,1,...,j,...,H-2について b_j == a_(j+1) であればよい
'''

import re

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

ans = ''
answers = ('Possible','Impossible')

r = re.compile(r'\.*#+\.*')

for i in range(H):
	s = input()
	if len(r.findall(s)) == 1:
		A.append(s)
	else:
		#'#'が2箇所以上にわかれていたらその時点でアウト
		ans = answers[1]
		break
		
for i in range(H-1):
	if A[i].rfind('#') == A[i+1].find('#'):
		continue
	else:
		ans = answers[1]
		break

if ans == '':
	ans = answers[0]

print(ans)

Submission status: Runtime Error

Solution code:
#AGC007 A
'''
問題
縦H行で横W列の盤面がある
コマははじめ左上隅のマスに置かれており，右下隅に移動した
駒は1マスずつ上下左右に動ける
駒が通ったことのあるマスが提示されるので，駒が常に右または下にしか動いていなかったどうか判定せよ
ただし通ったことのあるマスは'#',一度も通らなかったマスは'.'で与えられる

考察
各行0,1,...,i,...,H-1に対して'#'のマスが存在する範囲を[ai,bi]とする。ただし0<=ai<=bi<=W-1
このとき各0,1,...,j,...,H-2について b_j == a_(j+1) であればよい
'''

import re

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

ans = ''
answers = ('Possible','Impossible')

r = re.compile(r'\.*#+\.*')

for i in range(H):
	s = input()
	#'#'が2箇所以上にわかれていたらその時点でアウト
	if len(r.findall(s)) == 1:
		A.append(s)
	else:
		ans = answers[1]
		break
		
for i in range(H-1):
	if A[i].rfind('#') == A[i+1].find('#'):
		continue
	else:
		ans = answers[1]
		break

if ans == '':
	ans = answers[0]

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
input_nums = [int(n) for n in input().slice(“ ”)]
h = input_nums[0]
w = input_nums[1]

count = 0

for i in range(h):
	for c in input():
		if c == “#”:
			count += 1

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

Submission status: Runtime Error

Solution code:
from random import shuffle
from collections import Counter
def inpl(): return list(map(int, input().split()))

#N = 20000
#P = list(range(1, N+1))
#shuffle(P)

N = int(input())
P = inpl()

A = [0]*N
B = [0]*N
S = [10**9 - N] * (N)
for i, p in enumerate(P):
    S[p-1] += i

A[0] = 1
B[0] = S[0] - 1

for i in range(1, N):
    A[i] = max(A[i-1] + 1, S[i] - B[i-1] + 1)
    B[i] = S[i] - A[i]

for i in range(N-1):
    assert A[i] < A[i+1]
    assert B[i] > B[i+1]

assert B[-1] > 0
print(*A)
print(*B)

Submission status: Runtime Error

Solution code:
from random import shuffle
from collections import Counter
def inpl(): return list(map(int, input().split()))

#N = 20000
#P = list(range(1, N+1))
#shuffle(P)

N = int(input())
P = inpl()

A = [0]*N
B = [0]*N
S = [10**9 - N] * (N)
for i, p in enumerate(P):
    S[p-1] += i

A[0] = 1
B[0] = S[0] - 1

for i in range(1, N):
    A[i] = max(A[i-1] + 1, S[i] - B[i-1] + 1)
    B[i] = S[i] - A[i]

for i in range(N-1):
    assert A[i] < A[i+1]
    assert B[i] > B[i+1]

assert B[-1] > 0
print(*A)
print(*B)

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())
grid = [["."]*(W+2) for _ in range(W+2)]
for j in range(1, H+1):
    l = input()
    for i in range(len(l)-1):
        grid[j][i+1] = l[i]


r = 1
c = 1
while r <= H and c <= W:
    if grid[r+1][c] == "#" and grid[r][c+1] == ".":
        r += 1
    elif grid[r+1][c] == "." and grid[r][c+1] == "#":
        c += 1
    elif r == H and c == W:
        ans = "Possible"
        break
    else:
        ans = "Impossible"
        break
print(ans)

Submission status: Runtime Error

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: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

y = 0
x = 0

goal_y = H - 1
goal_x = W - 1

ans = 'Impossible'
counts = 0
for item in inputs:
    counts += item.count('#')

if counts != (H + W - 1):
    ans = 'Impossible'
else:
    for i in range(H + W - 2):
        if 0 <= x <= W - 1 and inputs[y][x + 1] == '#':
            x = x + 1
        elif 0 <= y <= H - 1 and inputs[y + 1][x] == '#':
            y = y + 1
        else:
            ans = 'Impossible'
            break
    ans = 'Possible' if y == goal_y and x == goal_x else 'Impossible'

print(ans)

Submission status: Runtime Error

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

y = 0
x = 0

goal_y = H - 1
goal_x = W - 1

counts = 0
for item in inputs:
    counts += item.count('#')

if counts != (H + W - 1):
    ans = 'Impossible'
else:
    for i in range(H + W - 2):
        if 0 <= x <= W - 1 and inputs[y][x + 1] == '#':
            x = x + 1
        elif 0 <= y <= H - 1 and inputs[y + 1][x] == '#':
            y = y + 1
        else:
            ans = 'Impossible'
            break
    ans = 'Possible' if y == goal_y and x == goal_x else 'Impossible'

print(ans)

Submission status: Runtime Error

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

y = 0
x = 0

goal_y = H - 1
goal_x = W - 1

counts = 0
for item in inputs:
    counts += item.count('#')

if counts != (H + W - 1):
    print('Impossible')
else:
    for i in range(H + W - 2):
        if 0 <= x <= W - 1 and inputs[y][x + 1] == '#':
            x = x + 1
        elif 0 <= y <= H - 1 and inputs[y + 1][x] == '#':
            y = y + 1
    print('Possible' if y == goal_y and x == goal_x else 'Impossible')

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from functools import lru_cache
@lru_cache(maxsize=None)
def search(i,j):
  global s,h,w
  if i==h-1and j==w-1:return 1
  r=0
  if i<h-1and s[i+1][j]=='#':r|=search(i+1,j)
  else if j<w-1and s[i][j+1]=='#':r|=search(i,j+1)
  if i>0and s[i-1][j]=='#':r=0
  if j>0and s[i][j-1]=='#':r=0
  return r
h,w=map(int,input().split())
s=[input()for _ in[0]*h]
print(('P'*search(0,0)or'Imp')+'ossible')

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
A = [input() for _ in range(H)]
pos = {x:0, y:0}
cnt = 0
for i in range(H):
  cnt += A[i].count('#')

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

Submission status: Runtime Error

Solution code:
import sys


H, W = map(int, input().split())
m = [input() for i in range(H)]

valid = True
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
for y in range(H):
    for x in range(W):
        if m[y][x] != '#':
            continue
        cnt = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < W and \
               0 <= ny and ny < H and m[ny][nx] == '#':
                cnt += 1
        if cnt >= 3:
            valid = False
            print("Impossible")
            sys.exit()


def rec(x, y):
    if x == W - 1 and y == H - 1:
        return True

    if m[y][x] != '#':
        return False
    dx = [0, 1]
    dy = [1, 0]
    valid = False
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx and nx < W and \
           0 <= ny and ny < H and m[ny][nx] == '#':
            ret = rec(nx, ny)
            if ret:
                return ret
    return False


if rec(0, 0):
    print("Possible")
else:
    print("Impossible")

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(raw_input())
p = map(int,raw_input().split())
a = [i for i in xrange(1, n+1)]
b = [i for i in reversed(xrange(1, n+1))]

for i in p:
    count = 0
    a[i] += count
    count += 1
for i in a:
    print i,
print ""
for i in b:
    print i,

Submission status: Runtime Error

Solution code:
#agc007a

h,w=map(int(raw_input())
cnt=0
for i in range(h):
 cnt+=raw_input().count('#')
if cnt==h+w-1
 print 'Possible'
else:
 print 'Impossible'

Submission status: Runtime Error

Solution code:
N = input()
l = input().split()

N=int(N)
a=range(1,N+1)
b=range(1,N+1)
a=[i*N for i in a]
b=[i*N for i in b]
b.reverse()

c=0
for i in l:
    i=int(i)
    b[i-1]+=c
    c+=1

for i in a:
    print(i,end=" ")
print("")
for i in b:
    print(i,end=" ")

Submission status: Runtime Error

Solution code:
def rl(proc=None):
    if proc is not None:
        return proc(sys.stdin.readline())
    else:
        return sys.stdin.readline().rstrip()

def srl(proc=None):
    if proc is not None:
        return map(proc, rl().split())
    else:
        return rl().split()

def fix(a):
    mn = min(a) - 1
    return [x - mn for x in a]

def main():
    N = rl(int)
    p = srl(int)
    a = range(N)
    b = list(reversed(a))
    for i, v in enumerate(p[1:], 1):
        a[v-1] += i
        for j in xrange(v, N):
            a[j] += i
            b[j] -= i
    print " ".join(map(str, fix(a)))
    print " ".join(map(str, fix(b)))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n, e, t = map(int, raw_input().split())
X = map(int, raw_input().split())

if n > 2001:
    exit(1)
ans = 0
bef = 0
bef_i = 0

d = [[0 for i in xrange(n)] for j in xrange(n)]
for i in xrange(n):
    el = d[i]
    xi = X[i]
    for j in xrange(i, n):
        el[j] = max(2*(X[j] - xi), t) + X[j] - xi
for i in xrange(n):
    for j in xrange(i):
        d[0][i] = min(d[0][j]+d[j+1][i]+(X[j+1]-X[j]), d[0][i])
print d[0][n-1]+ e - X[-1] + X[0]

Submission status: Runtime Error

Solution code:
import sys
 
H, W = map(int, input().split())
 
matrix = []
for i in range(H):
	row = sys.stdin.readline()
	matrix.append(row)
	
x=0
y=0
flag = True
strResult="Possible"
while((x<W-1) & (y<H-1) & flag):
	if matrix[y][x+1] == '#':
		x += 1
		for y2 in range(y+1,H):
			if matrix[y2][x-1] == '#':
				strResult = "Impossible"
				flag = False
				break
	elif matrix[y+1][x] == '#':
		y += 1
		for x2 in range(x+1,W):
			if matrix[y-1][x2] == '#':
				strResult = "Impossible"
				flag = false
				break
	else:
		strResult = "Impossible"
		flag = False
			
print (strResult)

Submission status: Runtime Error

Solution code:
n=int(raw_input())
p=map(lambda x:int(x)-1,raw_input().split())
a=range(1,n+1)
b=range(n,0,-1)
for i in xrange(1,n):
    if p[i]>p[i-1]:
        diff=abs(a[p[i]]+b[p[i]]-(a[p[i-1]]+b[p[i-1]]))
        for j in xrange(p[i],n):
            a[j]=a[j]+diff+1
    else:
        diff=abs(a[p[i]]+b[p[i]]-(a[p[i-1]]+b[p[i-1]]))
        for j in xrange(p[i],-1,-1):
            b[j]=b[j]+diff+1
print(" ".join(map(str,a)))
print(" ".join(map(str,b)))

Submission status: Runtime Error

Solution code:
N = int(input())
P = [int(x) for x in input().split()]

a = [i* 10**3+1 for i in range(N)]
b= list(reversed(a))



for i in range(N):
    #P[i] =2* i
    p = P[i]-1
    a[p]+=i

print(" ".join(map(str,a)) )
print(" ".join(map(str,b)) )


def check():
    tmp =0
    for i in P:
        i-=1
        print(tmp<a[i]+b[i])
        tmp=a[i]+b[i]

#check()

Submission status: Runtime Error

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