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 = map(int, input().split())
A = [input()+"." for _ in range(H)]
A.append("."*(W+1))
ans = "Possible"
for w in range(W):
    for h in range(H):
        if A[h][w] == "#":
            if A[h-1][w] == "#":
                ans = "Impossible"
                break
            elif A[h][w+1] == "#" and A[h+1][w] == ".":
                pass
            elif A[h][w+1] == "." and A[h+1][w] == "#":
                pass
            elif h == H-1 and w == W-1:
                break
            else:
                ans = "Impossible"
                break
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [input()+"." for _ in range(H)]
A.append("."*(W+1))
ans = "Possible"
for w in range(W):
    for h in range(H):
        if A[h][w] == "#":
            if A[h+1][w] == "#":
                ans = "Impossible"
                break
            elif A[h][w+1] == "#" and A[h+1][w] == ".":
                pass
            elif A[h][w+1] == "." and A[h+1][w] == "#":
                pass
            elif h == H-1 and w == W-1:
                break
            else:
                ans = "Impossible"
                break
print(ans)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [input()+"." for _ in range(H)]
A.append("."*(W+1))
ans = "Possible"
for w in range(W):
    for h in range(H):
        if A[h][w] == "#":
            if A[h][w+1] == "#" and A[h+1][w] == ".":
                pass
            elif A[h][w+1] == "." and A[h+1][w] == "#":
                pass
            elif h == H-1 and w == W-1:
                break
            else:
                ans = "Impossible"
                break
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def DFS(x,y): # h*wの配列logの深さ優先探索
    global h,w,maze,log
    if not (x<0 or h<=x or y<0 or w<=y or maze[x][y]=="."):
        log[x][y]+=1
        maze[x][y]="a"
        if log[x][y]>1:
            print("Impossible")
            exit()
        DFS(x+1,y)
        DFS(x,y+1)
    else:
        return
    

def main():
    n,m = map(int,input().split())
    global h,w,maze,log
    maze=[]
    for _ in range(n):
        maze.append(list(input()))
    log = [[0 for _ in range(m)] for _ in range(n)]
    h=n
    w=m
    for i in range(n):
        maze[i].reverse()
    maze.reverse()
    DFS(0,0)
    for i in range(n):
        for j in range(m):
            if maze[i][j]=="#":
                print("Impossible")
                exit()
    if log[h-1][w-1]==1:print("Possible")
    else:print("Impossible")
    
main()

Submission status: Wrong Answer

Solution code:
def DFS(x,y): # h*wの配列logの深さ優先探索
    global h,w,maze,log
    if not (x<0 or h<=x or y<0 or w<=y or maze[x][y]=="."):
        log[x][y]+=1
        maze[x][y]="."
        if log[x][y]>1:
            print("Impossible")
            exit()
        DFS(x+1,y)
        DFS(x,y+1)
    else:
        return
    

def main():
    n,m = map(int,input().split())
    global h,w,maze,log
    maze=[]
    for _ in range(n):
        maze.append(list(input()))
    log = [[0 for _ in range(m)] for _ in range(n)]
    h=n
    w=m
    for i in range(n):
        maze[i].reverse()
    maze.reverse()
    DFS(0,0)
    for i in range(n):
        for j in range(m):
            if maze[i][j]=="#":
                print("Impossible")
                exit()
    if log[h-1][w-1]==1:print("Possible")
    else:print("Impossible")
    
main()

Submission status: Wrong Answer

Solution code:
def DFS(x,y): # h*wの配列logの深さ優先探索
    global h,w,maze,log
    if not (x<0 or h<=x or y<0 or w<=y or maze[x][y]=="."):
        log[x][y]+=1
        if log[x][y]>1:
            print("Impossible")
            exit()
        DFS(x+1,y)
        DFS(x,y+1)
    else:
        return
    

def main():
    n,m = map(int,input().split())
    global h,w,maze,log
    maze=[]
    for _ in range(n):
        maze.append(list(input()))
    log = [[0 for _ in range(m)] for _ in range(n)]
    h=n
    w=m
    DFS(0,0)
    if log[h-1][w-1]==1:print("Possible")
    else:print("Impossible")
    
main()

Submission status: Wrong Answer

Solution code:
def DFS(x,y): # h*wの配列logの深さ優先探索
    global h,w,maze,log
    if not (x<0 or h<=x or y<0 or w<=y or maze[x][y]=="."):
        log[x][y]=1
        DFS(x+1,y)
        DFS(x,y+1)
    else:
        return
    

def main():
    n,m = map(int,input().split())
    global h,w,maze,log
    maze=[]
    for _ in range(n):
        maze.append(list(input()))
    log = [["" for _ in range(m)] for _ in range(n)]
    h=n
    w=m
    DFS(0,0)
    if log[h-1][w-1]==1:print("Possible")
    else:print("Impossible")
    
main()

Submission status: Wrong Answer

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

i, j = 0, 0
possible = True
while (i, j) != (H - 1, W - 1):
    A[i][j] = '.'
    left = j - 1 >= 0 and A[i][j - 1] == '#'
    right = j + 1 < W and A[i][j + 1] == '#'
    upper = i - 1 >= 0 and A[i - 1][j] == '#'
    lower = i + 1 < H and A[i + 1][j] == '#'
    if (left, right, upper, lower) == (False, False, False, True):
        i += 1
    elif (left, right, upper, lower) == (False, True, False, False):
        j += 1
    else:
        possible = False
        break
print('Possible' if possible else 'Impossible')

Submission status: Wrong Answer

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

i, j = 0, 0
possible = True
while (i, j) != (H - 1, W - 1):
    right = j + 1 < W and A[i][j + 1] == '#'
    down = i + 1 < H and A[i + 1][j] == '#'
    if not right ^ down:
        possible = False
        break
    elif right:
        j += 1
    else:
        i += 1
print('Possible' if possible else 'Impossible')

Submission status: Wrong Answer

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

a = list()
for i in range(h):
    s = input()
    b = list()
    for j in range(w):
        b.append(s[j])
    b.append("q")
    a.append(b)
b = ["q"]*w
a.append(b)

    
ch = 1 
i = 0
j = 0

while(1):

    if(a[i+1][j]=='#' and a[i][j+1]=='#'):
        ch = 0
        break
    elif(a[i+1][j]=='.' and a[i][j+1]=='.'):
        ch = 0
        break
    elif(a[i+1][j]=='q' and a[i][j+1]=='.'):
        ch = 0
        break
    elif(a[i+1][j]=='.' and a[i][j+1]=='q'):
        ch = 0
        break
    elif(i==h-1 and j==w-1):
        break
    elif(a[i+1][j]=='#' and (a[i][j+1]=='.' or a[i][j+1]=='q')):
        i+=1
    elif((a[i+1][j]=='.' or a[i+1][j]=='q') and a[i][j+1]=='#'):
        j+=1
    
if(ch==1):
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(grid, start):
    stack = []
    stack.append(start)
    grid[start[0]][start[1]] = '.'
    dxy = [(0,1), (1,0)]
    while stack:
        h,w = stack.pop()
        for dx,dy in dxy:
            x, y = w+dx, h+dy
            if grid[y][x] == '.':
                continue
            if (y,x) == (h,w):
                return True
            stack.append((y,x))
            grid[y][x] = '.'
    return False

H,W = map(int, input().split())
edges = ['.'] * (W+2)
grid = [edges]
cnt = 0
for i in range(H):
    s = input()
    grid.append(['.'] + list(s) + ['.'])
    cnt += s.count('#')
grid.append(edges)
start = [1,1]
print('Possible' if cnt == (H*W-1) else 'Inpossible')

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(grid, start):
    stack = []
    stack.append(start)
    grid[start[0]][start[1]] = '.'
    dxy = [(0,1), (1,0)]
    while stack:
        h,w = stack.pop()
        for dx,dy in dxy:
            x, y = w+dx, h+dy
            if grid[y][x] == '.':
                continue
            if (y,x) == (h,w):
                return True
            stack.append((y,x))
            grid[y][x] = '.'
    return False

H,W = map(int, input().split())
edges = ['.'] * (W+2)
grid = [edges]
cnt = 0
for i in range(H):
    s = input()
    grid.append(['.'] + list(s) + ['.'])
    cnt += s.count('#')
grid.append(edges)
start = [1,1]
print('Possible' if dfs(grid, start) and cnt == (H*W-1) else 'Inpossible')

Submission status: Wrong Answer

Solution code:
from collections import deque

def dfs(grid, start):
    stack = []
    stack.append(start)
    grid[start[0]][start[1]] = '.'
    dxy = [(0,1), (1,0)]
    while stack:
        h,w = stack.pop()
        grid[h][w] = '.'
        for dx,dy in dxy:
            x, y = w+dx, h+dy
            if grid[y][x] == '.':
                continue
            if (y,x) == (H,W):
                return stack == []
            stack.append((y,x))
    return False

H,W = map(int, input().split())
edges = ['.'] * (W+2)
grid = [edges]
for i in range(H):
    s = input()
    grid.append(['.'] + list(s) + ['.'])
grid.append(edges)
start = [1,1]
print('Possible' if dfs(grid, start) else 'Inpossible')

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
a=10
b=10
for i in range(H):
  A=input()[::-1]
  try:
    c=A.index("#")
    r=A.rfind("#")
    if c<=a and r<b and all(x=="#" for x in A[c:r+1]):
      a=c
      b=r
    else:
      a=10
      break
  except:
    pass
print("Possible" if a!=10 else "Impossible")

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
a=10
for i in range(H):
  A=input()[::-1]
  try:
    c=A.index("#")
    r=A.rfind("#")
    if c<=a and r<=a and all(x=="#" for x in A[c:r+1]):
      a=c
      a=r
    else:
      a=10
      break
  except:
    pass
print("Possible" if a!=10 else "Impossible")

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
a=10
for i in range(H):
  A=input()[::-1]
  try:
    c=A.index("#")
    r=A.rfind('#')
    if c<=a and r<a:
      a=c
      a=r
    else:
      a=10
      break
  except:
    pass
print("Possible" if a!=10 else "Impossible")

Submission status: Wrong Answer

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

import numpy as np

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

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

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


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


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


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

Submission status: Wrong Answer

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

import numpy as np

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

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

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


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


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


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

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
a=10
for i in range(H):
  A=input()[::-1]
  try:
    c=A.index("#")
    if c<=a:
      a=c
    else:
      a=10
      break
  except:
    pass
print("Possible" if a!=10 else "Impossible")

Submission status: Wrong Answer

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

for h in range(H):
  for w in range(W):
    if (h == 0 and w == 0) or (h == H-1 and w == W-1):
      continue
    flag1 = 0
    flag2 = 0
    if grid[h][w] == "#":
      if 0 <= h-1 < H:
        if grid[h-1][w] == "#":
          flag1 += 1
      if 0 <= w-1 < W:
        if grid[h][w-1] == "#":
          flag1 += 1
      if 0 <= h+1 < H:
        if grid[h+1][w] == "#":
          flag2 += 1
      if 0 <= w+1 < W:
        if grid[h][w+1] == "#":
          flag2 += 1
      if flag1 == 1 and flag2 == 1:
        continue
      else:
        print("Impossible")
        exit()
else:
  print("Possible")

Submission status: Wrong Answer

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

prev_left = 0
prev_right = 0

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

if left == W-1 or right == W-1:
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

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

prev_left = -1
prev_right = -1

for i in range(H):
    left = A[i].find('#')
    right = A[i].rfind('#')
    if prev_left < left and prev_right < right:
        prev_left = left
        prev_right = right
    else:
        print('Impossible')
        exit()

print('Possible')

Submission status: Wrong Answer

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

stack = [(0, 0)]
while stack:
    x, y = stack.pop()
    if x == h - 1 and y == w - 1:
        print('Possible')
        exit(0)
    
    x1, y1 = x, y + 1
    x2, y2 = x + 1, y

    if y1 < w and a[x1][y1] == '#' and (x2 == h or a[x2][y2] == '.'):
        stack.append((x1, y1))

    if x2 < h and a[x2][y2] == '#' and (y1 == w or a[x1][y1] == '.'):
        stack.append((x2, y2))

print('Impossible')

Submission status: Wrong Answer

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

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


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

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

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

#print(map)

Submission status: Wrong Answer

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

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


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

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

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

#print(map)

Submission status: Wrong Answer

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

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


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

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

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

#print(map)

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    i = 0
    j = 0
    visited = set([(0, 0), (H-1, W-1)])
    if A[0][0] != "#" or A[H-1][W-1] != "#":
        print("Impossible")
        return
    while i != H-1 and j != W-1:
        if i + 1 < H and A[i+1][j] == "#":
            i += 1
        elif j + 1 < W and A[i][j+1] == "#":
            j += 1
        else:
            print("Impossible")
            return
        visited.add((i, j))
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#" and (i, j) not in visited:
                print("Impossible")
                return
    print("Possible")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    i = 0
    j = 0
    visited = set([(0, 0)])
    while i < H and j < H:
        if i + 1 < H and A[i+1][j] == "#":
            i += 1
        elif j + 1 < W and A[i][j+1] == "#":
            j += 1
        else:
            print("Impossible")
            return
        visited.add((i, j))
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#" and (i, j) not in visited:
                print("Impossible")
                return
    print("Possible")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# 2019/08/16

h,w=map(int,input().split())
w+=2
a=[['.']*w]
for i in range(h):
    a+=[['.']+list(input())+['.']]

a+=[['.']*w]

g=(h,w-2)
cnt=0

i,j=1,1
while i<h or j<w:
    if (i,j)==g:
        ans='Possible'
        break
    if (a[i+1][j]=='#')^(a[i][j+1]=='#'):
        if a[i+1][j]=='#':
            a[i+1][j]='@'
            i+=1
        else:
            a[i][j+1]='@'
            j+=1
    else:
        ans='Impossible'
        break

print(ans)

Submission status: Wrong Answer

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

A = [list(input()) for _ in range(H)]

def move(i, j): #今、マス(i, j)にいる
    if A[i][j] == '.': #道ではない時
        return False
    if i == H - 1 and j == W - 1: #ゴール地点にいる時
        return True
    if i == H - 1: #一番下の段にいるとき
        return move(i, j + 1)
    if j == W - 1: #一番右の列にいるとき
        return move(i + 1, j)
    if A[i + 1][j] == A[i][j + 1]: #両方道 or 両方行き止まり
        return False 
    if A[i + 1][j] == '#': #下が道の時
        return move(i + 1, j)
    if A[i][j + 1] == '#': #右が道の
        return move(i, j + 1)

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

Submission status: Wrong Answer

Solution code:
h,*a=open(0);print("Im"*(sum(x.count("#")for x in a)!=eval(h.replace(" ","+"))-1)+"possible")

Submission status: Wrong Answer

Solution code:
h,*a=open(0);print("IM"*(sum(x.count("#")for x in a)!=eval(h.replace(" ","+"))-1)+"POSSIBLE")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
x = y = 0
while True:
    if x + 1 < w and y + 1 < h:
        if a[y][x+1] == a[y+1][x]:
            print("Impossible")
            exit()
        elif a[y][x+1] == "#":
            x += 1
        elif a[y+1][x] == "#":
            y += 1
    elif y + 1 >= h:
        x += 1
        if a[y][x] != "#":
            print("Impossible")
            exit()
    elif x + 1 >= w:
        y += 1
        if a[y][x] != "#":
            print("Impossible")
            exit()
    if x == w - 1 and y == h - 1:
        print("Possible")
        exit()

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a = []
a.append("."*(w+2))
for i in range(h):
    a.append("." + input() + ".")
a.append("."*(w+2))
ans = "Possible"
for i in range(h+2):
    for j in range(w+2):
        if a[i][j] == "#":
            if (i==1 and j==1) or (i==h and j==w):
                if [a[i-1][j],a[i][j-1]].count("#")!=1:
                    ans = "Impossible"
            else:
                if [a[i-1][j],a[i][j-1]].count("#")!=2:
                    ans = "Impossible"
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a = []
a.append("."*(w+2))
for i in range(h):
    a.append("." + input() + ".")
a.append("."*(w+2))
ans = "Possible"
for i in range(h+2):
    for j in range(w+2):
        if a[i][j] == "#":
            if (i==1 and j==1) or (i==h and j==w):
                if [a[i+1][j],a[i-1][j],a[i][j-1],a[i][j+1]].count("#")!=1:
                    ans = "Impossible"
            else:
                if [a[i+1][j],a[i-1][j],a[i][j-1],a[i][j+1]].count("#")!=2:
                    ans = "Impossible"
print(ans)

Submission status: Wrong Answer

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

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

def solve(i, j):


    if grid[i][j] == ".":
        print("Impossible")
        exit()

    if i == h-1 and j == w-1:
        print("Possible")
        exit()
    
    elif i == h-1:
        if grid[i][j+1] == "#":
            solve(i, j+1)
        else:
            print("Impossible")
            exit()
    elif j == w-1:
        if grid[i+1][j] == "#":
            solve(i+1, j)
        else:
            print("Impossible")
            exit()
    #print("--", i, j)
    else:
        if grid[i][j+1] == "#" and grid[i+1][j] == "#":
            print("Impossible")
            exit()
        else:
            if grid[i][j+1] == "#":
                solve(i, j+1)
            elif grid[i+1][j] == "#":
                solve(i+1, j)
            else:
                print("Impossible")
                exit()

solve(0,0)
#print("Impossible")

Submission status: Wrong Answer

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

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

def solve(i, j):

    if i == 0 and j == 0:
        if grid[i][j] == ".":
            print("Impossible")
            exit()

    if i == h-1 and j == w-1:
        print("Possible")
        exit()
    
    elif i == h-1:
        if grid[i][j+1] == "#":
            solve(i, j+1)
        else:
            print("Impossible")
            exit()
    elif j == w-1:
        if grid[i+1][j] == "#":
            solve(i+1, j)
        else:
            print("Impossible")
            exit()
    #print("--", i, j)
    else:
        if grid[i][j+1] == "#" and grid[i+1][j] == "#":
            print("Impossible")
            exit()
        else:
            if grid[i][j+1] == "#":
                solve(i, j+1)
            elif grid[i+1][j] == "#":
                solve(i+1, j)
            else:
                print("Impossible")
                exit()

solve(0,0)
#print("Impossible")

Submission status: Wrong Answer

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

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

def solve(i, j):
    if i == h-1 and j == w-1:
        print("Possible")
        exit()
    
    elif i == h-1:
        if grid[i][j+1] == "#":
            solve(i, j+1)
        else:
            print("Impossible")
            exit()
    elif j == w-1:
        if grid[i+1][j] == "#":
            solve(i+1, j)
        else:
            print("Impossible")
            exit()
    #print("--", i, j)
    else:
        if grid[i][j+1] == "#" and grid[i+1][j] == "#":
            print("Impossible")
            exit()
        else:
            if grid[i][j+1] == "#":
                solve(i, j+1)
            elif grid[i+1][j] == "#":
                solve(i+1, j)
            else:
                print("Impossible")
                exit()

solve(0,0)
#print("Impossible")

Submission status: Wrong Answer

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

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

def solve(i, j):
    if i == h-1 and j == w-1:
        print("Possible")
        exit()
    
    elif i == h-1:
        if grid[i][j+1] == "#":
            solve(i, j+1)
        else:
            print("Impossible")
            exit()
    elif j == w-1:
        if grid[i+1][j] == "#":
            solve(i+1, j)
        else:
            print("Impossible")
            exit()
    #print("--", i, j)
    else:
        if grid[i][j+1] == "#" and grid[i+1][j] == "#":
            print("Impossible")
            exit()
        else:
            if grid[i][j+1] == "#":
                solve(i, j+1)
            if grid[i+1][j] == "#":
                solve(i+1, j)

solve(0,0)
#print("Impossible")

Submission status: Wrong Answer

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

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

def solve(i, j):
    if i == h-1 and j == w-1:
        print("Possible")
        exit()
    
    if i == h-1:
        if grid[i][j+1] == "#":
            solve(i, j+1)
        else:
            return
    elif j == w-1:
        if grid[i+1][j] == "#":
            solve(i+1, j)
        else:
            return
    #print("--", i, j)
    else:
        if grid[i][j+1] == "#" and grid[i+1][j] == "#":
            return
        else:
            if grid[i][j+1] == "#":
                solve(i, j+1)
            if grid[i+1][j] == "#":
                solve(i+1, j)

solve(0,0)
print("Impossible")

Submission status: Wrong Answer

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

A[0] = list('.' * (W+2))
A[H+1] = list('.' * (W+2))

for i in range(H+2):
    A[i] = ''.join(A[i])
    #print(A[i])



check = 0

for i in range(1,H+1):
    for j in range(1, W+1):
        if i == H and j ==W :
            if A[i][j] == '#':
                pass
            else:
                check = 1
        else:
            if A[i][j] == '#':
                if A[i+1][j] == '.' and A[i][j+1] == '#':
                    pass
                elif A[i+1][j] == '#' and A[i][j+1] == '.':
                    pass
                else:
                    check = 1

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

Submission status: Wrong Answer

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

A[0] = list('.' * (W+2))
A[H+1] = list('.' * (W+2))

#print(A)

check = 0

for i in range(1,H+1):
    for j in range(1, W+1):
        if i == H and j ==W :
            pass
        else:
            if A[i][j] == '#':
                if A[i+1][j] == '.' and A[i][j+1] == '#':
                    pass
                elif A[i+1][j] == '#' and A[i][j+1] == '.':
                    pass
                else:
                    check = 1

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

Submission status: Wrong Answer

Solution code:
#### import ####
import sys
sys.setrecursionlimit(10**7)
import math
from collections import defaultdict

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

H,W = II()
A = [list(map(str, input())) for _ in range(H)]
for i in range(H):
  A[i].append('?')
A.append(['?']*(W+1))

i=0;j=0
while 1:
  if i==H-1 and j==W-1:
    print('Possible')
    exit()
  if A[i+1][j]=='#' and A[i][j+1]=='#':
    print('Impossible')
    exit()    
  if A[i+1][j]=='#':
    i +=1
    continue
  if A[i][j+1]=='#':
    j +=1
    continue
  print('Impossible')
  exit()

Submission status: Wrong Answer

Solution code:
def end_impossible():
    print("Impossible")
    exit()


H, W = map(int, input().split())
A = [input() for _ in range(H)]
for i in range(H - 1, -1, -1):
    for j in range(W - 1, -1, -1):
        if A[i][j] == "#":
            if i > 0 and j > 0:
                if [A[i - 1][j], A[i][j - 1]].count("#") != 1:
                    end_impossible()
            elif i > 0:
                if A[i - 1][j] != "#":
                    end_impossible()
            elif j > 0:
                if A[i][j - 1] != "#":
                    end_impossible()
print("Possible")