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:
#import string,itertools,fractions,heapq,re,array,bisect
#from math import *
#from collections import Counter
def rl(s): return xrange(len(s))

INF = 2147483647


import sys
stdin = sys.stdin

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

lines = [stdin.readline() + '.' for _ in range(H)] + ['.' * W]

fail = False
for y, line in enumerate(lines):
    for x, ch in enumerate(line):
        if ch != '#': continue
        if x == W-1 and y == H-1: continue

        right = (line[x+1] == '#')
        down = (lines[y+1][x] == '#')
        if not (right ^ down):
            fail = True

        if not (x == 0 and y == 0):
            if x == 0:
                if lines[y-1][x] != '#': fail = True
            elif y == 0:
                if line[x-1] != '#': fail = True
            else:
                if not ( (lines[y-1][x] == '#') ^ (line[x-1] == '#') ):
                    fail = True

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

Submission status: Accepted

Solution code:
H,W=[int(x) for x in input().split()]

A = [list(map(lambda x: x=="#" ,input())) for _ in range(H)]

#print(A)


try:
    for i in range(H):
        for j in range(W):
            if A[i][j]:
                start=i,j
                raise
except:
    pass


def a(i,j):
    if i<H and j<W:
        return A[i][j]
    return False

tmp =start
used = [start]
while True:
    #print(tmp)
    i,j =tmp
    if a(i+1,j):
        tmp = i+1,j
        used.append(tmp)
        continue
    if a(i,j+1):
        tmp = i ,j+1
        used.append(tmp)
    else:
        break

for i in range(H):
    for j in range(W):
        if A[i][j]:
            if (i,j) in used:
                continue
            else:
                #print(i,j)
                print("Impossible")
                exit()
print("Possible")

Submission status: Accepted

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

def solve():
    x, y = 0, 0
    while x != w - 1 or y != h - 1:
        m[y][x] = '.'

        if y < h - 1 and m[y + 1][x] == '#':
            if x < w - 1 and m[y][x + 1] == '#':
                return False
            else:
                if '#' in m[y]:
                    return False
                y += 1
        elif x < w - 1 and m[y][x + 1] == '#':
            for i in range(h):
                if '#' == m[i][x]:
                    return False
            x += 1
        else:
            return False

    return True

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

Submission status: Accepted

Solution code:
h, w = map(int, raw_input().split())
s = [list(raw_input().strip()) for _ in xrange(h)]
def dfs(x, y):
    if x == w - 1 and y == h - 1:
        s[y][x] = '.'
        return 1
    if x < w - 1 and s[y][x+1] == '#' and dfs(x + 1, y):
        s[y][x] = '.'
        return 1
    if y < h - 1 and s[y+1][x] == '#' and dfs(x, y + 1):
        s[y][x] = '.'
        return 1
    return 0
if dfs(0, 0) and sum(''.join(r).count('#') for r in s) == 0:
    print "Possible"
else:
    print "Impossible"

Submission status: Accepted

Solution code:
h,w=map(int,raw_input().split())
l=[]
#l=map(int,raw_input().split())
for i in range(h):
    l.append(list(raw_input()))
l[0][0]='.'
x=y=0
while 1:
    if x+1<w and l[y][x+1]=='#':
        x+=1
        l[y][x]='.'
    elif y+1<h and l[y+1][x]=='#':
        y+=1
        l[y][x]='.'
    else:
        break
for i in l:
    if '#' in i:
        print 'Impossible'
        exit()
print 'Possible'

Submission status: Accepted

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

x = y = 0
A[0][0] = '.'
while 1:
    if y+1 < h and A[y+1][x] == '#':
        A[y+1][x] = '.'
        y += 1
    elif x+1 < w and A[y][x+1] == '#':
        A[y][x+1] = '.'
        x += 1
    else: break
if y == h-1 and x == w-1 and all(all(f is '.' for f in e) for e in A):
    print "Possible"
else:
    print "Impossible"

Submission status: Accepted

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


left = 0
possible = True
for i in range(H):
    for j in range(W):
        if array[i][j] == "#":
            if j < left:
                possible = False
                break
            if j > left:
                left = j

if possible:
    print "Possible"
else:
    print "Impossible"

Submission status: Accepted

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

current = (0,0)
good = True
for y in range(H):
    for x in range(W):
        if grid[y][x] == "#":
            count = 0
            aboveCount = 0
            if W-1>x and grid[y][x+1] == "#":
                count+=1
            if H-1>y and grid[y+1][x] == "#":
                count+=1
            if x>0 and grid[y][x-1] == "#":
                aboveCount+=1
            if 0<y and grid[y-1][x] == "#":
                aboveCount+=1
            if (aboveCount==0 and y+x!=0) or (count!=1 and y+x!=H+W-2):
                good = False
                break
if good:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
import sys
h,w=map(int,raw_input().split())
a=[list(raw_input()) for _ in range(h)]
b=[['.']*w for _ in range(h)]
i=j=0
flag=True
while flag:
    b[i][j]='#'
    if (i,j)==(h-1,w-1):break
    flag=False
    if i+1<h:
        if a[i+1][j]=='#':i+=1;flag=True
    if not flag and j+1<w:
        if a[i][j+1]=='#':j+=1;flag=True
if a==b:print 'Possible'
else:print 'Impossible'

Submission status: Accepted

Solution code:
import re

def main():
    H, W = map(int, raw_input().split())
    prev_end = 0
    HASH_RE = re.compile(r"#+")
    for i in range(H):
        A = raw_input()
        if HASH_RE.search(A, endpos=prev_end-1) is not None:
            print "Impossible"
            return 0

        m = HASH_RE.search(A, pos=prev_end-1)
        if m is None:
            print "Impossible"
            return 0

        if HASH_RE.search(A, pos=m.end()):
            print "Impossible"
            return 0

        prev_end = m.end()

    print "Possible"

if __name__ == "__main__":
    main()

Submission status: Accepted

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

used[0][0] = True
q = [(0, 0)]

while len(q) > 0:
    y, x = q[0]
    q = q[1:]
    if x+1 < W and board[y][x+1]=='#' and not used[y][x+1]:
        used[y][x+1] = True;
        q.append((y, x+1))
    elif y+1 < H and board[y+1][x]=='#' and not used[y+1][x]:
        used[y+1][x] = True;
        q.append((y+1, x))

ans = True
for i in range(H):
    for j in range(W):
        if board[i][j] == '#':
            ans = ans and used[i][j]

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

Submission status: Accepted

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

x,y = 0,0
while (x!=W-1 or y!=H-1):
    A[y][x] = "."
    r = x<W-1 and A[y][x+1]=="#"
    d = y<H-1 and A[y+1][x]=="#"

    if int(r)+int(d)!=1:
        print "Impossible"
        exit(0)
    if r:
        x += 1
    if d:
        y += 1

if sum(a.count("#") for a in A)!=1:
    print "Impossible"
    exit(0)
print "Possible"

Submission status: Accepted

Solution code:
H, W = map(int, raw_input().split())
B = [raw_input() for _ in xrange(H)]
r, c = 0, 0
s = set()

while r != H-1 or c != W-1:
    s.add((r, c))
    if r < H-1 and c < W-1:
        if B[r+1][c] == '#' and B[r][c+1] == '#':
            print 'Impossible'
            exit()
        elif B[r+1][c] == '.' and B[r][c+1] == '.':
            print 'Impossible'
            exit()
        elif B[r+1][c] == '#' and B[r][c+1] == '.':
            r += 1
            continue
        else:
            c += 1
            continue
    elif r == H-1:
        if B[r][c+1] == '.':
            print 'Impossible'
            exit()
        else:
            c += 1
            continue
    else:
        if B[r+1][c] == '.':
            print 'Impossible'
            exit()
        else:
            r += 1
            continue

s.add((H-1, W-1))

t = set()
for i in xrange(H):
    for j in xrange(W):
        if B[i][j] == '#':
            t.add((i, j))

if s == t:
    print 'Possible'
else:
    print 'Impossible'

Submission status: Accepted

Solution code:
line=input().split()
h=int(line[0])
w=int(line[1])
m = []
m.append("."*(w+2))
for i in range (h):
    m.append("." + input() + ".")
m.append("."*(w+2))
works=True
for i in range (1,h+1):
    for j in range (1,w+1):
        if m[i][j]=="#":
            if m[i+1][j]=="#" and m[i][j+1]=="#":
                works=False
            if m[i-1][j]=="#" and m[i][j-1]=="#":
                works=False
if works:
    print ("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

H, W = ln()

panel = [['.'] + list(s()) + ['.'] for h in xrange(H)]

cur = 1

for i in xrange(H):
    for j in xrange(cur, W + 1):
        if panel[i][j] == '#':
            panel[i][j] = '.'
            cur = j
        else:
            break

success = True
for i in xrange(H):
    for j in xrange(1, W + 1):
        if panel[i][j] == '#':
            success = False
            break
    if not success:
        break

if success:
    print 'Possible'
else:
    print 'Impossible'

Submission status: Accepted

Solution code:
#!/usr/bin/python2
# -*- coding: utf-8 -*-

import sys

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 go(a, x, y):
    if a[x][y] != '#':
        return []
    r = [(x, y)]
    while True:
        for tx, ty in ((x+1, y), (x, y+1)):
            if 0 <= tx < len(a) and 0 <= ty < len(a[0]) and a[tx][ty] == '#':
                x = tx
                y = ty
                break
        else:
            break
        r.append((x,y))
    return r


def main():
    R, C = srl(int)
    a = []
    for _ in xrange(R):
        a.append(rl())
    b = go(a, 0, 0)
    if not b or b[-1] != (R-1, C-1):
        print "Impossible"
        return
    s = sum(x.count('#') for x in a)
    print "Impossible" if s != len(b) else "Possible"

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
a1 = []
s = input()
for j in range(w):
    if s[j] == "#":
        a1.append(j)
a =[]
for i in range(h - 1):
    s = input()
    for j in range(w):
        if s[j] == "#":
            a.append(j)
    if a[0] < a1[len(a1) - 1]:
        print("Impossible")
        raise SystemExit
    a1 = [i for i in a]
    a = []
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:
#!/usr/bin/env python3


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !

H,W=map(int,raw_input().split())
c=0
for _ in xrange(H):
    s=raw_input()
    for i in xrange(W):
        if s[i]=="#": c+=1
if H+W-1==c: print "Possible"
else: print "Impossible"

Submission status: Runtime Error

Solution code:
import sys


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

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

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

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

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

print("Possible")

Submission status: Runtime Error

Solution code:
import sys


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

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

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

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

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

print("Possible")

Submission status: Runtime Error

Solution code:
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    short h,w,ans = 0;
    cin >> h >> w;
    char ai[10];
    rep(i,h) {
        cin >> ai;
        rep(j,8) if (ai[j] == '#') ans ++;
    }
    if (ans == h+w-1) cout << "Possible\n";
    else cout << "Impossible\n";
}

Submission status: Runtime Error

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


ans = 'Possible'
ans = 'Impossible'

def check(i,j):
    if mat_a[i][j] == '.':
        return True

    count = 0
    try:
        if mat_a[i][j-1] == '#':
            count += 1
    except:
        pass

    try:
        if mat_a[i-1][j] == '#':
            count += 1
    except:
        pass

    try:
        if mat_a[i][j+1] == '#':
            count += 1
    except:
        pass

    try:
        if mat_a[i+1][j] == '#':
            count += 1
    except:
        pass

    if count == 2 or count ==4:
        return True
    else:
        return False    


ans = True
for i in range(h):
    for j in range(w):
        if not check(i,j):
            if i+1 == h and j+1 == w:
                continue
            if i == 0 and j == 0:
                continue
            ans = False
            break

if ans:
    print('Possible')
else:
    print('Impossible')
(env3) (kentaro:~/git/2020/atcode/20200717/3 2020-07-17T17:09:31)$ vi main.py 
(env3) (kentaro:~/git/2020/atcode/20200717/3 2020-07-17T17:10:52)$ cat main.py 
h, w = map(int, input().split())
mat_a = [ list(input()) for _ in range(h) ]

def check(i,j):
    if mat_a[i][j] == '.':
        return True

    count = 0
    try:
        if mat_a[i][j-1] == '#':
            count += 1
    except:
        pass

    try:
        if mat_a[i-1][j] == '#':
            count += 1
    except:
        pass

    try:
        if mat_a[i][j+1] == '#':
            count += 1
    except:
        pass

    try:
        if mat_a[i+1][j] == '#':
            count += 1
    except:
        pass

    if count == 2 or count == 4:
        return True
    else:
        return False    


ans = True
for i in range(h):
    for j in range(w):
        if not check(i,j):
            if i+1 == h and j+1 == w:
                continue
            if i == 0 and j == 0:
                continue
            ans = False
            break

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

Submission status: Runtime Error

Solution code:
H,W=4,5
a = [input() for i in range(H)]


ans=0
cnt=0

for i in range(H-1):
    for j in range(W-1):
        if a[i][j] == '#' and a[i+1][j] == '#' and  a[i][j+1] == '#':
            cnt+=1
            break
        elif a[i][j] == '#' and a[i+1][j] == '.' and  a[i][j+1] == '.':
            cnt+=1
            break
        else:
            continue
 
print('Impossible' if cnt>0 else 'Possible')

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
a=[]
for i in range(h):
  at=list(str(input()))
  a.append(at)
i=0
j=0
t=0
while True:
  if a[i][j+1]=="#":
    for k in range(i+1,h):
      if a[k][j]=="#":
        t=1
        break
    else:
      j=j+1
  elif a[i+1][j]=="#":
    for k in range(j+1,w):
      if a[i][k]=="#":
        t=1
        break
    else:
      i=i+1
  if t==1:
    print("Impossible")
    break
  elif i==h-1 and j==w-1:
    print("Possible")
    break

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = map(int, input().split())
a = [None]*h
for i in range(h):
    a[i] = input()
cx = 0
cy = 0
d = set()
while (cx,cy)!=(h-1, w-1):
    val = 0
#     print(cx,cy)
    for dx, dy in [(1,0), (0,1)]:
        ccx = cx+dx
        ccy = cy+dy
        if ccx>=h or ccy>=w or a[ccx][ccy]==".":
            continue
        nx, ny = ccx, ccy
        val += 1
    if val>=2 or val==0:
        ans = "Impossible"
        break
    cx, cy = nx, ny
else:
    vv = sum(item=="#" for item in items for items in a)
    if vv==h+w-1:
        ans = "Possible"
    else:
        ans = "Impossible"
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["#","#"]:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
            if a[i][j:j+3] == ["#","#","#"] and w > 2:
                if a[i+2][j] == '#':
                    print("Impossible")
                    exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["#","#"]:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
            if a[i][j:j+3] == ["#","#","#"] and n > w:
                if a[i+2][j] == '#':
                    print("Impossible")
                    exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
def solve():
    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    for i in range(h-1):
        for j in range(w-1):
            if a[i][j:j+2] == ["#","#"]:
                if a[i+1][j] == '#':
                    print("Impossible")
                    exit()
            if a[i][j:j+3] == ["#","#","#"]:
                if a[i+2][j] == '#':
                    print("Impossible")
                    exit()
    print("Possible")
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve():
    n, m = getList
    tmp = 0
    for i in range(n):
        s = getS()
        stop = False
        for i, c in enumerate(s):
            if i < tmp:
                if c == "#":
                    print("Impossible")
                    return
            else:
                if not stop:
                    if c == ".":
                        stop = True
                        tmp = i-1
                else:
                    if c == "#":
                        print("Impossible")
                        return
                    
    print("Possible")
    return
                        
                
            
    nums = getList()

    ans = 0
    for i, num in enumerate(nums):
        ans += 2 * (min(abs(k - num), num))


    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()


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

Submission status: Runtime Error

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

def dfs(h,w,c):
  if h == H - 1 and w == W - 1:
    return c + 1
  
  if GRID[h][w] != "#":
    return 0
  
  if H - 1 < h or W -1 < w:
    return 0
  
  right = dfs(h+1,w,c+1)
  down = dfs(h,w+1,c+1)
  c += max(right,down)

  return c

NUM = sum([GRID[x].count("#") for x in range(H)])

n = dfs(0,0,0)

if n == NUM:
  print("Possible")
else:
  print("Impossible")

Submission status: Runtime Error

Solution code:
def main():
    h,w=map(int,input().split())
    a=[]
    for _ in range(h):
        a.append(input())
    now = [0, 0]
    end = [h-1, w-1]
    while now != end:
        nxt = None
        if now[0]+1 < len(a) and a[now[0]+1][now[1]] == "#":
            nxt = now[:]
            nxt[0] += 1
        if now[1]+1 < len(a[now[0]]) and a[now[0]][now[1]+1] == "#":
            if nxt != None:
                print("Impossible")
                return
            nxt = now[:]
            nxt[1] += 1
        now = nxt
    print("Possible")
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
a = [list(input()) for nesya in range(h)]
b = [['.']*w for motsu in range(h)]
b[0][0] = '#'
j = 0
for i in range(h):
  if j < w:
    while a[i][j+1] == '#':
      j += 1
      b[i][j] = '#'
      if j == w-1:
        break
  if i+1 < h:
    b[i+1][j] = '#'

if a == b:
  print('Possible')
else:
  print('Impossible')

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
a = [list(input()) for nesya in range(h)]
b = [['.']*w for motsu in range(h)]
b[0][0] = '#'
j = 0
for i in range(h):
  while a[i][j+1] == '#':
    j += 1
    b[i][j] = '#'
  b[i+1][j] = '#'
if a == b:
  print('Possible')
else:
  print('Impossible')

Submission status: Runtime Error

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

visited = [[False]*W for i in range(H)]
visited[0][0] = True
d = [[0, 0], [-1, -1]]
while d:
  x, y, px, py = d.pop()
  num = 0
  flag = False
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    if 0<=x+dx<H and 0<=y+dy<W and [x+dx, y+dy]!=[px, py] and A[x+dx][y+dy]=='#' and not visited[x+dx][y+dy]:
      visited[x+dx][y+dy] = True
      num += 1
      d.append([x+dx, y+dy, x, y])
      if dx < 0 or dy < 0:
        flag = True
  if (num >= 2) or flag:
    print('Impossible')
    quit()

print('Possible')

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
HW = [list(map(str,input().split())) for _ in range(h)]
sharp = 0
for i in range(w):
  for j in range(h):
    if HW[i][j] == '#':
      sharp += 1

min_root = h + w - 1
if sharp == min_root:
  print('Possible')
else:
  print('Impossible')

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
HW = [list(map(int,input().split())) for _ in range(h)]
min_root = h + w - 1
if sharp == min_root:
  print('Possible')
else:
  print('Impossible')

Submission status: Runtime Error

Solution code:
h,w = map(int,input().split())
HW = [list(map(int,input().split())) for _ in range(h)]
sharp = HW.count('#')
min_root = h + w - 1
if sharp == min_root:
  print('Possible')
else:
  print('Impossible')

Submission status: Runtime Error

Solution code:
import sys
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]+1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=0 and start[1]!=0 and listA[start[0]-1][start[1]]=="#" and listA[start[0]][start[1]-1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#":
    start=[start[0]+1,start[1]]
    continue  
  if start[1]!=W-1 and listA[start[0]][start[1]+1]=="#":
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]+1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=0 and start[1]!=0 and listA[start[0]-1][start[1]]=="#" and listA[start[0]][start[1]-1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#":
    start=[start[0]+1,start[1]]
    continue  
  if start[1]!=W-1 and listA[start[0]][start[1]+1]=="#":
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")

Submission status: Runtime Error

Solution code:
import sys
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]+1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=0 and start[1]!=0 and listA[start[0]-1][start[1]]=="#" and listA[start[0]][start[1]-1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#":
    start=[start[0]+1,start[1]]
    continue  
  if listA[start[0]][start[1]+1]=="#":
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")

Submission status: Runtime Error

Solution code:
import sys
H,W=map(int,input().split())
listA=[list(input()) for i in range(H)]
start=[0,0]
while 1:
  if start==[H-1,W-1]:
    print("Possible")
    sys.exit()
  if start[1]==W-1 and start[0]!=H-1:
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]+1]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=0 and start[1]!=0 and listA[start[0]+1][start[1]]=="#" and listA[start[0]][start[1]-1]=="#" and listA[start[0]-1][start[1]]=="#":
    print("Impossible")
    sys.exit()
  if start[0]!=H-1 and listA[start[0]+1][start[1]]=="#":
    start=[start[0]+1,start[1]]
    continue  
  if listA[start[0]][start[1]+1]=="#":
    start=[start[0],start[1]+1]    
  else:
    print("Impossible")