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: Wrong Answer

Solution code:
h,w = (int(i) for i in input().split())
#print("h w:",h,w)
map_data = [list(input()) for j in range(h)]
map_step = [[0 for i in range(w)] for j in range(h)]
def peek_around(map_data,x,y):
#    print("peek_around {},{}".format(x,y))
    count = 0
    result = []
    for i in range(-1,2,1):
        for j in range(-1,2,1):
            if not i*j == 0:
                continue
#            print("  i,j",i,j)
#            print("  x+i,y+j",x+i,y+j)
            if (0 <= x+i and x+i < h)  and (0 <= y+j and y+j < w):
#                print("checking map_data[{}][{}]".format(x+i,y+j))
                if map_data[x+i][y+j] == "#":
                    result.append([x+i,y+j]) 
                    count += 1
    return count, result
                

g_x = h-1
g_y = w-1
for i in range(g_x,-1,-1):
    for j in range(g_y,-1,-1):
#        print("i,j",i,j)
        if map_data[i][j] == "#":
            steps = map_step[i][j]
            count, result = peek_around(map_data,i,j)
            for element in result:
                x = element[0]
                y = element[1]
                if map_step[x][y] > steps+1:
                    map_step[x][y] = steps+1
#print("map_data:",map_data)
#print("map_step:",map_step)
if map_step[0][0] == h+w-2:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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
strResult="Possible"
while((x<W) & (y<H-1)):
	if ((x<W-1) & (matrix[y][x+1] == '#')):
		x += 1
	elif ((x>0) & (matrix[y+1][x-1] == '#')):
		strResult = "Impossible"
		break
	else:
		y += 1
		if y == H-1:
			for x2 in range(x,W):
				if matrix[H-1][x2] == '.':
					strResult = "Impossible"
					break
	
			
print (strResult)

Submission status: Wrong Answer

Solution code:
h,w = (int(i) for i in input().split())
#print("h w:",h,w)
map_data = [list(input()) for j in range(h)]
map_step = [[0 for i in range(w)] for j in range(h)]
def peek_around(map_data,x,y):
#    print("peek_around {},{}".format(x,y))
    count = 0
    result = []
    for i in range(-1,2,1):
        for j in range(-1,2,1):
            if not i*j == 0:
                continue
#            print("  i,j",i,j)
#            print("  x+i,y+j",x+i,y+j)
            if (0 <= x+i and x+i < h)  and (0 <= y+j and y+j < w):
#                print("checking map_data[{}][{}]".format(x+i,y+j))
                if map_data[x+i][y+j] == "#":
                    result.append([x+i,y+j]) 
                    count += 1
    return count, result
                

g_x = h-1
g_y = w-1
for i in range(g_x,-1,-1):
    for j in range(g_y,-1,-1):
#        print("i,j",i,j)
        if map_data[i][j] == "#":
            steps = map_step[i][j]
            count, result = peek_around(map_data,i,j)
            for element in result:
                x = element[0]
                y = element[1]
                if map_step[x][y] == 0:
                    map_step[x][y] = steps+1
#print("map_data:",map_data)
#print("map_step:",map_step)
if map_step[0][0] == h+w-2:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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
strResult="Possible"
while((x<W) & (y<H-1)):
	if ((x<W-1) & (matrix[y][x+1] == '#')):
		x += 1
	elif ((x>0) & (matrix[y+1][x-1] == '#')):
		strResult = "Impossible"
		break
	else:
		y += 1
		if y == H-1:
			for x2 in range(x,W):
				if matrix[x2][H-1] == '.':
					strResult = "Impossible"
					break
	
			
print (strResult)

Submission status: Wrong Answer

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

for i in range(h-1):
    for j in range(w):
        if a[i][j]=="#":
            if a[i+1][j]=="#" and a[i+1][j-1] == "#":
                print("Impossible")
                sys.exit()
            break
print("Possible")

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys
h,w=[int(x) for x in input().split()]
a=[]
def cell(x,y):
    if x<0 or y<0 or x==h or y==w:
        return 0
    elif a[x][y] =='#':
        return 1
    return 0

def calc(x,y):
    if a[x][y]!='#' or (x==h-1 and y==w-1):
        return True
    if cell(x+1,y)+cell(x,y+1)==2:
        return False
    return True

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

for i in range(h):
    for j in range(w):
        if not calc(i,j):
            print("Impossible")
            sys.exit()
print("Possible")

Submission status: Wrong Answer

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
strResult="Possible"
while((x<W) & (y<H)):
	if (y==H-1):
		for x2 in range(x,W):
			if matrix[x2][H-1] != '#':
				strResult = "Impossible"
		break
	elif ((x<W-1) & (matrix[y][x+1] == '#')):
		x += 1
	elif ((x>0) & (matrix[y+1][x-1] == '#')):
		strResult = "Impossible"
		break
	elif matrix[y+1][x] != '#':
		strResult = "Impossible"
		break
	else:
		y += 1
	
			
print (strResult)

Submission status: Wrong Answer

Solution code:
import sys
lines = sys.stdin.readlines()
sizes = lines[0].split(" ")
H = int(sizes[0])
W = int(sizes[1])
field = []
for line in lines[1:]:
    field.append(line.rstrip())

#print (field)

posQ = [[0,0]]

now = [0,0]
before = [-1,0]

while(now[0]+1<H or now[1]+1<W):
    if (before==now):
        break
    #print (now)
    if now[1]+1<W:
        if field[now[0]][now[1]+1:now[1]+2] == "#":
            posQ.append([now[0],now[1]+1])
    if now[0]+1<H:
        if field[now[0]+1][now[1]:now[1]+1] == "#":
            posQ.append([now[0]+1,now[1]])
    before = now
    now = posQ[len(posQ)-1]

"""
now = [0,0]

if field[now[0]][now[1]+1:now[1]+2] == "#":
    posQ.append([now[0],now[1]+1])
if field[now[0]+1][now[1]:now[1]+1] == "#":
    posQ.append([now[0]+1,now[1]])

now = posQ[len(posQ)-1]

if field[now[0]][now[1]+1:now[1]+2] == "#":
    posQ.append([now[0],now[1]+1])
if field[now[0]+1][now[1]:now[1]+1] == "#":
    posQ.append([now[0]+1,now[1]])


"""

#print (posQ)
#print (len(posQ))
if (len(posQ)!=H+W-1):
    print("Impossible")
else:
    print("Possible")

Submission status: Wrong Answer

Solution code:
import sys
h, w = map(int, input().split())
i = 0
pos = 1
while h > i:
    s = input()
    idx = s.rfind('#')
    if (pos <= idx):
        pos = idx
        i += 1
    else:
        print('Impossible')
        sys.exit()
print('Possible')

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !
def count(ls, item):
    cnt = 0
    for ls1 in ls:
        cnt += ls1.count(item)
    return cnt
    
def dfs(mp, sr, sc, h, w):
    visited = [[ False for i in range(w)] for j in range(h)]
    stack = []
    stack.append((sr, sc))
    visited[sr][sc] = True
    while stack:
        tr, tc = stack.pop()
        nextcells = [(tr + 1, tc), (tr, tc + 1)]
        for nexttr, nexttc in nextcells:
            if 0 <= nexttr < h and 0 <= nexttc < w:
                #print(nexttr, nexttc)
                if mp[nexttr][nexttc] == "#":
                    if nexttr == h - 1 and nexttc == w - 1:
                        if count(visited, True) == count(mp, "#"):
                            return True
                    stack.append((nexttr, nexttc))
                    visited[nexttr][nexttc]
    
    return False
    

if __name__ == "__main__":
    h, w = map(int, input().split(" "))
    mp = []
    for i in range(h):
        mp.append(list(input()))
    #print(mp)
    if dfs(mp, 0, 0, h, w):
        print("Possible")
    else:
        print("Impossible")

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Here your code !
def count(ls, item):
    cnt = 0
    for ls1 in ls:
        cnt += ls1.count(item)
    return cnt
    
def dfs(mp, sr, sc, h, w):
    visited = [[ False for i in range(w)] for j in range(h)]
    stack = []
    stack.append((sr, sc))
    visited[sr][sc] = True
    while stack:
        tr, tc = stack.pop()
        nextcells = [(tr + 1, tc), (tr, tc + 1)]
        for nexttr, nexttc in nextcells:
            if 0 <= nexttr < h and 0 <= nexttc < w:
                print(nexttr, nexttc)
                if mp[nexttr][nexttc] == "#":
                    if nexttr == h - 1 and nexttc == w - 1:
                        if count(visited, True) == count(mp, "#"):
                            return True
                    stack.append((nexttr, nexttc))
                    visited[nexttr][nexttc]
    
    return False
    

if __name__ == "__main__":
    h, w = map(int, input().split(" "))
    mp = []
    for i in range(h):
        mp.append(list(input()))
    print(mp)
    if dfs(mp, 0, 0, h, w):
        print("Possible")
    else:
        print("Impossible")

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w =  map(int, input().split())
a = [list(input()) for i in range(h)]
mv = [[1, 0], [0, 1]]

sx, sy = 0, 0
gx, gy = h - 1, w - 1
nxt = deque()
nxt.appendleft([sx, sy])

for i in range(h - 1):
    count = 0
    for j in range(w):
        if a[i][j] == "#":
            if a[i][j] == a[i + 1][j]:
                count += 1
    if count > 1:
        nxt.clear()
        break

flag = 0
while len(nxt) > 0:
    tmp = nxt.pop()
    nwx, nwy = tmp[0], tmp[1]
    if nwx == gx and nwy == gy:
        flag = 1
        break
    count = 0
    for i in range(2):
        tmpx = mv[i][0] + nwx
        tmpy = mv[i][1] + nwy
        if tmpy < w and tmpx < h:
            if a[tmpx][tmpy] == '#':
                nxt.appendleft([tmpx, tmpy])
                count += 1
    if count > 1:
        break
        
if flag:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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
strResult="Possible"
while((x<W) & (y<H-1)):
	if ((x<W-1) & (matrix[y][x+1] == '#')):
		x += 1
	elif ((x>0) & (matrix[y+1][x-1] == '#')):
		strResult = "Impossible"
		break
	else:
		y += 1
	
			
print (strResult)

Submission status: Wrong Answer

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

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

prevend=0
for i in range(H):
    for j in range(W):
        if A[i][j] == '#' and j < prevend:
            print ("Impossible")
            exit()
        elif j>0 and A[i][j-1] == '#' and A[i][j] == '.':
            prevend = j-1
            break
        elif j==W-1:
            prevend =W-1
print("Possible")

Submission status: Wrong Answer

Solution code:
[i, j] = [int(x) for x in raw_input().split()]

A = []
for row in range(i):
    A.append(raw_input())

tmpi = 0;
tmpj = 0;

success = True
while (tmpi < i-1 and tmpj < j-1):
    if tmpj == j-1:
        hasright = False
    else:
        hasright = A[tmpi][tmpj+1] == '#'
    if tmpi == i-1:
        hasdown = False
    else:
        hasdown = A[tmpi+1][tmpj] == '#'
    if (hasright and hasdown) \
        or (not hasright and not hasdown):
        success = False
        print 'Impossible'
        break
    if (hasright):
        tmpj += 1
    if (hasdown):
        tmpi += 1
if(success and tmpi == i-1 and tmpj == j-1):
    print 'Possible'
else:
    print 'Impossible'

Submission status: Wrong Answer

Solution code:
def solve(x,y):
    global end_flag
    if end_flag:
        MAP[y][x] = '.'
        if y == H-1 and x == W-1:
            end_flag = False
            return 0

        if x+1 < W:
            if MAP[y][x+1] == '#':
                solve(x+1,y)
        if y+1 < H:
            if MAP[y+1][x] == '#':
                solve(x,y+1)
    else:
        return 0

H,W = map(int,raw_input().split(' '))
MAP = []
for i in range(H):
    tmp = list(raw_input())
    MAP.append(tmp)

flag = False
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '#':
            flag = True
if flag:
    end_flag = True
    solve(0,0)

    s_flag = True
    for i in range(H):
        for j in range(W):
            if MAP[i][j] == '#':
                s_flag = False

    if s_flag:
        print 'Possible'
    else:
        print 'Impossible'
else:
    print 'Impossible'

Submission status: Wrong Answer

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

B = list()
for h in range(H):
    B.append(list())
    for w in range(W):
        B[h].append('.')

i = 0
j = 0
ret = "Impossible"
while True:
    B[h][w] = '#'
    # down and right
    if i+1 < H and j+1 < W:
        if A[i][j+1] == "#" and A[i+1][j] == ".":
            # right
            j += 1
        elif A[i][j+1] == "." and A[i+1][j] == "#":
            # down
            i += 1
        else:
            break
    # right only
    elif i+1 == H and j+1 < W:
        if A[i][j+1] == "#":
            # right
            j += 1
        else:
            break
    # down only
    elif i+1 < H and j+1 == W:
        if A[i+1][j] == "#":
            # down
            i += 1
        else:
            break
    elif i+1 == H and j+1 == W:
        if A == B:
            ret = "Possible"
        break
print ret

Submission status: Wrong Answer

Solution code:
import sys
h,w=[int(x) for x in input().split()]
a=[]
def cell(x,y):
    if x<0 or y<0 or x==h or y==w:
        return 0
    elif a[x][y] =='#':
        return 1
    return 0

def calc(x,y):
    if a[x][y]!='#' or (x==h-1 and y==w-1):
        return True
    if cell(x-1,y)+cell(x,y-1)>cell(x+1,y)+cell(x,y+1):
        return False
    return True

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

for i in range(h):
    for j in range(w):
        if not calc(i,j):
            print("Impossible")
            sys.exit()
print("Possible")

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w =  map(int, input().split())
a = [list(input()) for i in range(h)]
mv = [[1, 0], [0, 1]]

sx, sy = 0, 0
gx, gy = h - 1, w - 1
nxt = deque()
nxt.appendleft([sx, sy])

for i in range(h - 1):
    count = 0
    for j in range(w):
        if a[i][j] == "#" and a[i][j] == a[i + 1][j]:
            count += 1
    if count > 1:
        nxt.clear()
        break

flag = 0
while len(nxt) > 0:
    tmp = nxt.pop()
    nwx, nwy = tmp[0], tmp[1]
    if nwx == gx and nwy == gy:
        flag = 1
        break
    for i in range(2):
        tmpx = mv[i][0] + nwx
        tmpy = mv[i][1] + nwy
        if tmpy < w and tmpx < h:
            if a[tmpx][tmpy] == '#':
                nxt.appendleft([tmpx, tmpy])
if flag:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
[i, j] = [int(x) for x in raw_input().split()]

A = []
for row in range(i):
    A.append(raw_input())

tmpi = 0;
tmpj = 0;

success = True
while (tmpi < i and tmpj < j):
    if tmpi == i-1 and tmpj == j-1:
        print "Possible"
        break
    if tmpj == j-1:
        hasright = False
    else:
        hasright = A[tmpi][tmpj+1] == '#'
    if tmpi == i-1:
        hasdown = False
    else:
        hasdown = A[tmpi+1][tmpj] == '#'
    if (hasright and hasdown) \
        or (not hasright and not hasdown):
        print 'Impossible'
        break
    if (hasright):
        tmpj += 1
    if (hasdown):
        tmpi += 1

Submission status: Wrong Answer

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

end_flag = True

def solve(x,y):
    global end_flag
    if end_flag:
        MAP[y][x] = '.'
        if y == H-1 and x == W-1:
            end_flag = False
            return 0

        if x+1 < W:
            if MAP[y][x+1] == '#':
                solve(x+1,y)
        if y+1 < H:
            if MAP[y+1][x] == '#':
                solve(x,y+1)
    else:
        return 0

solve(0,0)

flag = True
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '#':
            flag = False

if flag:
    print 'Possible'
else:
    print 'Impossible'

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w =  map(int, input().split())
a = [list(input()) for i in range(h)]
mv = [[1, 0], [0, 1]]

sx, sy = 0, 0
gx, gy = h - 1, w - 1
nxt = deque()
nxt.appendleft([sx, sy])

for i in range(h - 1):
    count = 0
    for j in range(w):
        if a[i][j] == a[i + 1][j]:
            count += 1
    if count > 1:
        nxt.clear()
        break
        
flag = 0
while len(nxt) > 0:
    tmp = nxt.pop()
    nwx, nwy = tmp[0], tmp[1]
    if nwx == gx and nwy == gy:
        flag = 1
        break
    for i in range(2):
        tmpx = mv[i][0] + nwx
        tmpy = mv[i][1] + nwy
        if tmpy < w and tmpx < h:
            if a[tmpx][tmpy] == '#':
                nxt.appendleft([tmpx, tmpy])
if flag:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        if g[y][x]=="#":
            return True
    return False

def dfs(y,x):
    dx=(0,1)
    dy=(1,0)
    if y==h-1 and x==w-1:
        return True
    for i in xrange(2):
        nxy=y+dy[i]
        nxx=x+dx[i]
        if check(nxy,nxx) and not visited[nxy][nxx]:
            visited[nxy][nxx]=True
            if dfs(nxy,nxx):
                return True
            #visited[nxy][nxx]=True
    return False

h,w=map(int,raw_input().split())
g=[raw_input() for _ in xrange(h)]
visited=[[False]*w for _ in xrange(h)]
visited[0][0]=True
if not dfs(0,0):
    print("Impossible")
    exit()
for i in xrange(h):
    for j in xrange(w):
        if g[i][j]=="#" and not visited[i][j]:
            print("Impossible")
            exit()
print("Possible")

Submission status: Wrong Answer

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

m = []
for i in range(H):
    m.append(input()+'.')

m.append('.'*(W+1))
    
x, y = 0, 0

while not(x==W-1 and y==H-1):
    if(m[y][x+1]=='#' and m[y+1][x]=='.'):
        x+=1
    elif(m[y][x+1]=='.' and m[y+1][x]=='#'):
        y+=1
    else:
        print('Impossible')
        exit()


print('Possible')

Submission status: Wrong Answer

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

H, W = map(int, input().split())
F = [list(input()) for x in range(H)]
ans = True
px = py = 0
while py < H-1 or px < W-1:
    if py<H-1 and F[py+1][px]=='#':
        if px<W-1 and F[py][px+1]=='#':
            ans = False
            break
        py += 1
    elif px<W-1 and F[py][px+1]=='#':
        px += 1
    else:
        ans = False
        break
print('Possible' if ans else 'Impossible')

Submission status: Wrong Answer

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

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

ok = True

for i in range(h):
    for j in range(w):
        if(a[i][j]=='#' and (i>=1 and a[i-1][j]=='#') and (j>=1 and a[i][j-1]=="#")):
            ok = False
#            print i,j


x = 0
y = 0

while(True):
    if(x==h-1 and y==w-1):
        break

    if(x+1<h and a[x+1][y]=="#"):x+=1
    elif(y+1<w and a[x][y+1]=="#"):y+=1
    else:
        ok = False
        break

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

Submission status: Wrong Answer

Solution code:
import sys
h,w = [int(i) for i in raw_input().split()]

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

ok = True

if(a[h-1][w-1]=='.'):
    print "Impossible"
    sys.exit()

for i in range(h):
    for j in range(w):
        if(a[i][j]=='#' and (i>=1 and a[i-1][j]=='#') and (j>=1 and a[i][j-1]=="#")):
            ok = False
#            print i,j

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

Submission status: Wrong Answer

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

m = []
for i in range(H):
    m.append(input()+'.')

m.append('.'*(W+1))
    
x, y = 0, 0

while not(x==W-1 and y==H-1):
    if(m[y][x+1]==m[y+1][x]):
        print('Impossible')
        exit()
    if(m[y][x+1]=='#'):
        x+=1
    elif(m[y+1][x]=='#'):
        y+=1

print('Possible')

Submission status: Wrong Answer

Solution code:
import sys

IMPOSSIBLE = 'IMPOSSIBLE'
POSSIBLE = 'POSSIBLE'

def solve():
    H, W = map(int, sys.stdin.readline().split())
    lines = list(map(lambda s: s.rstrip(), sys.stdin.readlines()))
    maxs = []
    mins = []
    for line in lines:
        m = -1
        for i, w in enumerate(line):
            if w == '#':
                m = i
        maxs.append(m)
        m = len(line)
        for i, w in reversed(list(enumerate(line))):
            if w == '#':
                m = i
        mins.append(m)

    for i, (min, max) in enumerate(zip(mins, maxs)):
        if '.' in lines[i][min:max+1]:
            return IMPOSSIBLE

    for min, max in zip(mins[1:], maxs):
        if min != max:
            return IMPOSSIBLE

    return POSSIBLE

print(solve())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
def check(y,x):
    if 0<=y<=h-1 and 0<=x<=w-1:
        if g[y][x]=="#":
            return True
    return False

def dfs(y,x):
    global f
    dx=(0,1)
    dy=(1,0)
    if y==h-1 and x==w-1:
        return True
    for i in xrange(2):
        nxy=y+dy[i]
        nxx=x+dx[i]
        if check(nxy,nxx) and not visited[nxy][nxx]:
            visited[nxy][nxx]=True
            if dfs(nxy,nxx):
                return True
    return False
h,w=map(int,raw_input().split())
g=[raw_input() for _ in xrange(h)]
visited=[[False]*w for _ in xrange(h)]
visited[0][0]=True
if not dfs(0,0):
    print("Impossible")
    exit()
for i in xrange(h):
    for j in xrange(w):
        if g[i][j]=="#" and not visited[i][j]:
            print("Impossible")
            exit()
print("Possoble")

Submission status: Wrong Answer

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

nowx = 0
nowy = 0
flag = False
while map[nowx][nowy] == '#':
    count = 0
    if nowy < w - 1 and map[nowx][nowy + 1] == '#':
            count += 1
    if nowx < h - 1 and map[nowx + 1][nowy] == '#':
            count += 1
    if nowx == h - 1 and nowy == w - 1:
        flag = True
        break
    if count != 1:
        break
    if nowy < w - 1 and map[nowx][nowy + 1] == '#':
        nowy += 1
    else:
        nowx += 1

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

Submission status: Wrong Answer

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

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

ok = True

for i in range(h):
    for j in range(w):
        if(a[i][j]=='#' and (i>=1 and a[i-1][j]=='#') and (j>=1 and a[i][j-1]=="#")):
            ok = False
#            print i,j

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

Submission status: Wrong Answer

Solution code:
import sys

IMPOSSIBLE = 'IMPOSSIBLE'
POSSIBLE = 'POSSIBLE'

def solve():
    H, W = map(int, sys.stdin.readline().split())
    lines = list(map(lambda s: s.rstrip(), sys.stdin.readlines()))
    maxs = []
    mins = []
    for line in lines:
        m = -1
        for i, w in enumerate(line):
            if w == '#':
                m = i
        maxs.append(m)
        m = len(line)
        for i, w in reversed(list(enumerate(line))):
            if w == '#':
                m = i
        mins.append(m)

    for min, max in zip(mins, maxs):
        if '.' in lines[min:max+1]:
            return IMPOSSIBLE

    for min, max in zip(mins[1:], maxs):
        if min != max:
            return IMPOSSIBLE

    return POSSIBLE

print(solve())

Submission status: Wrong Answer

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

i = 0
j = 0
ret = "Impossible"
while True:
    # down and right
    if i+1 < H and j+1 < W:
        if A[i][j+1] == "#" and A[i+1][j] == ".":
            # right
            j += 1
        elif A[i][j+1] == "." and A[i+1][j] == "#":
            # down
            i += 1
        else:
            break
    # right only
    elif i+1 == H and j+1 < W:
        if A[i][j+1] == "#":
            # right
            j += 1
        else:
            break
    # down only
    elif i+1 < H and j+1 == W:
        if A[i+1][j] == "#":
            # down
            i += 1
        else:
            break
    elif i+1 == H and j+1 == W:
        ret = "Possible"
        break
print ret

Submission status: Wrong Answer

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 0<x and grid[y][x-1] == "#":
                count+=1
            if H-1>y and grid[y+1][x-1] == "#":
                count+=1
            if x<W-1 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==2:
                good = False
                break
if good:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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()
        m = HASH_RE.search(A, pos=prev_end)
        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: Wrong Answer

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

x,y = 0,0
while (x!=W-1 or y!=H-1):
    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

print "Possible"

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

(H, W) = reads()
A = []

for _ in range(H):
  A.append(input()+".")
A.append("." * (W+1))

(y, x) = (0, 0)

while (y, x) != (H-1, W-1):
  if A[y+1][x] == "#" and A[y][x+1] == ".":
    (y, x) = (y+1, x)
  elif A[y+1][x] == "." and A[y][x+1] == "#":
    (y, x) = (y, x+1)
  else:
    print("Impossible"); exit()

print("Possible")

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

h,w = map(int,input().split())
nec = []
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == "#":
            nec.append([i,j])

com = [1 for i in range(w-1)]+[0 for i in range(h-1)]
ans = False
alr = set()
for p in permutations(com):
    if p in alr:
        continue
    else:
        alr.add(p)
    # print(p)
    st = [0, 0]
    root = [[0, 0]]
    for c in p:
        if c == 1:
            nex = [st[0],st[1]+1]
            st = nex
            root.append(nex)
        else:
            nex = [st[0]+1,st[1]]
            st = nex
            root.append(nex)

    flags = [False for i in range(len(nec))]
    for i in range(len(nec)):
        if nec[i] in root:
            flags[i] = True
    # print(flags)
    ans = all(flags) or ans

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

h,w = map(int,input().split())
nec = []
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == "#":
            nec.append([i,j])

com = [1 for i in range(w-1)]+[0 for i in range(h-1)]
ans = False
for p in permutations(com):
    # print(p)
    st = [0, 0]
    root = [[0, 0]]
    for c in p:
        if c == 1:
            nex = [st[0],st[1]+1]
            st = nex
            root.append(nex)
        else:
            nex = [st[0]+1,st[1]]
            st = nex
            root.append(nex)

    flags = [False for i in range(len(nec))]
    for i in range(len(nec)):
        if nec[i] in root:
            flags[i] = True
    # print(flags)
    ans = all(flags) or ans

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

Submission status: Time Limit Exceeded

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 i<h and j+1 < w:
      if 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')