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)]; z = 0
for i in range(h):
    for j in range(w):
        if i == 0 and j == 0 or i == h-1 and j == w-1: continue
        if a[i][j] == "#":
            x = y = 0
            if i != 0:
                if a[i-1][j] == "#": x += 1
            if j != 0:
                if a[i][j-1] == "#": x += 1
            if i != h-1:
                if a[i+1][j] == "#": y += 1
            if j != w-1:
                if a[i][j+1] == "#": y += 1
            if x != 1 or y != 1: print("Impossible"); z = 1; break
    if z == 1: break
else: print("Possible")

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

cur = (0, 0)
while True:
    x, y = cur
    if x == W - 1 and y == H - 1:
        print("Possible")
        break
    nx1, ny1 = x + 1, y
    nx2, ny2 = x, y + 1
    if A[ny1][nx1] == '#' and A[ny2][nx2] == '#':
        print("Impossible")
        break
    if A[ny1][nx1] == '#':
        cur = (nx1, ny1)
    elif A[ny2][nx2] == '#':
        cur = (nx2, ny2)
    else:
        print("Impossible")
        break

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [''] * H
for i in range(H):
    A[i] = input()
x, y = 0, 0
while True:
    if (x < H-1 and A[x+1][y] == '#') and (y < W-1 and A[x][y+1] == '#'):
        print('Impossible')
        exit()
    elif (x > 0 and A[x-1][y] == '#') and (y > 0 and A[x][y-1] == '#'):
        print('Impossible')
        exit()
    elif (x == H-1 or A[x+1][y] == '.') and (y == W-1 or A[x][y+1] == '.'):
        print('Impossible')
        exit()
    elif x == H-1 and y == W-1:
            print('Possible')
            exit()
    elif x < H-1 and A[x+1][y] == '#':
        x += 1
        continue
    elif y < W-1 and A[x][y+1] == '#':
        y += 1
        continue

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [''] * H
for i in range(H):
    A[i] = input()
x, y = 0, 0
while True:
    if (x < H-1 and A[x+1][y] == '#') and (y < W-1 and A[x][y+1] == '#'):
        print('Impossible')
        exit()
    elif (x > 0 and A[x-1][y] == '#') and (y > 0 and A[x][y-1] == '#'):
        print('Impossible')
        exit()
    elif (x == H-1 or A[x+1][y] == '.') and (y == W-1 or A[x][y+1] == '.'):
        print('Impossible')
        exit()
    else:
        if x == H-1 and y == W-1:
            print('Possible')
            exit()
        elif x < H-1 and A[x+1][y] == '#':
            x += 1
            continue
        elif y < W-1 and A[x][y+1] == '#':
            y += 1
            continue

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [''] * H
for i in range(H):
    A[i] = input()
x, y = 0, 0
while True:
    if x == H-1 and y == W-1:
        print('Possible')
        exit()
    if (x < H-1 and A[x+1][y] == '#') and (y < W-1 and A[x][y+1] == '#'):
        print('Impossible')
        exit()
    elif (x > 0 and A[x-1][y] == '#') and (y > 0 and A[x][y-1] == '#'):
        print('Impossible')
        exit()
    elif (x == H-1 or A[x+1][y] == '.') and (y == W-1 or A[x][y+1] == '.'):
        print('Impossible')
        exit()
    elif x < H-1 and A[x+1][y] == '#':
        x += 1
        continue
    elif y < W-1 and A[x][y+1] == '#':
        y += 1
        continue

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [''] * H
for i in range(H):
    A[i] = input()
x, y = 0, 0
while True:
    if x == H-1 and y == W-1:
        print('Possible')
        exit()
    if (x < H-1 and A[x+1][y] == '#') and (y < W-1 and A[x][y+1] == '#'):
        print('Impossible')
        exit()
    elif (x == H-1 or A[x+1][y] == '.') and (y == W-1 or A[x][y+1] == '.'):
        print('Impossible')
        exit()
    elif x < H-1 and A[x+1][y] == '#':
        x += 1
        continue
    elif y < W-1 and A[x][y+1] == '#':
        y += 1
        continue

Submission status: Wrong Answer

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

#import
#import math
#import numpy as np
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

for i in range(H):
    for j in range(W):
        if i == j == 0:
            continue

        if A[i][j] != "#":
            continue

        ul = 0
        dr = 0

        if i != 0:
            if A[i - 1][j] == "#":
                ul += 1
        if i != H - 1:
            if A[i + 1][j] == "#":
                dr += 1
        if j != 0:
            if A[i][j - 1] == "#":
                ul += 1
        if j != W - 1:
            if A[i][j + 1] == "#":
                dr += 1

        if dr > 1 or ul > 1:
            print("Impossible")
            exit()

print("Possible")

Submission status: Wrong Answer

Solution code:

h,w = map(int,input().split())
s = []
s.append(["."]*(w+2))
for i in range(h):
    t = ["."]
    t.extend(list(input()))
    t.append(".")
    s.append(t)

s.append(["."]*(w+2))
f = 0
for i in range(h):
    for j in range(w):
        a,b = i+1,j+1
        if s[a][b] == "#":
            if a == 1 and b == 1:
                continue
            if s[a][b-1] == "." and s[a-1][b] == ".":
                f += 1
            if s[a][b+1] == "#" and s[a+1][b] == "#":
                f += 1
if f == 0:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
a = [input() for _ in range(h)]
right_limit = [0]*h
for j in range(w):
    if a[0][j] == "#":
        right_limit[0] = j

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

Submission status: Wrong Answer

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

right_limit = [0]*h
for i in range(w):
    if a[0][i] == ".":
        right_limit[0] = i-1
        break
    else:
        right_limit[0] = w-1

for i in range(1, h):
    for j in range(w-1):
        if j+1 == w-1 and a[i][j] == "#":
            right_limit[i] = w-1

        if j < right_limit[i-1]:
            if a[i][j] == "#":
                print("Impossible")
                exit()
            else:
                continue
        if a[i][j+1] == ".":
            right_limit[i] = j

print("Possible")

Submission status: Wrong Answer

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

right_limit = [0]*h
for i in range(w):
    if a[0][i] == ".":
        right_limit[0] = i-1
        break
    else:
        right_limit[0] = w-1

for i in range(1, h):
    limit_flag = False
    for j in range(w-1):
        if not limit_flag:
            if j+1 == w-1 and a[i][j] == "#":
                right_limit[i] = w-1

            if j < right_limit[i-1]:
                if a[i][j] == "#":
                    print("Impossible")
                    exit()
                else:
                    continue
            if a[i][j+1] == ".":
                right_limit[i] = j
                limit_flag = True
        else:
            if a[i][j+1] == "#":
                print("Impossible")
                exit()

print("Possible")

Submission status: Wrong Answer

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

right_limit = [0]*h
for i in range(w):
    if a[0][i] == ".":
        right_limit[0] = i-1
        break
    else:
        right_limit[0] = w-1

for i in range(1, h):
    for j in range(w-1):
        if j < right_limit[i-1]:
            if a[i][j] == "#":
                print("Impossible")
                exit()
            else:
                continue
        if a[i][j+1] == "#":
            continue
        right_limit[i] = j
        break
    else:
        right_limit[i] = w-1
print("Possible")

Submission status: Wrong Answer

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

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

    a.append('.' * (w-1))

    print(a)
    i = 0
    j = 0
    while True:
        if a[i+1][j] == '#' and a[i][j+1] == '.':
            i += 1
        elif a[i+1][j] == '.' and a[i][j+1] == '#':
            j += 1
        else:
            print('Impossible')
            return 0
        if i == h-1 and j == w-1:
            break
        print(i, j)

    print('Possible')
    return 0


if __name__ == "__main__":
    main()


'''

possible判定条件

前のコマの位置（左or上）以外は右or下のみに#がある

'''

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
A=[input()for i in range(H)]
for i in range(H):
    A[i]=A[i]+"."
A.append("."*(W+1))
p,q=1,1
c=1
t=0
for i in A:
    t+=i.count("#")
if t!=H+W-1:
    c=0
for i in range(H+W-2):
    print(p,q)
    if A[p-1][q-1]==".":
        c=0
        break
    if A[p][q-1]=="." and A[p-1][q]=="#":
        q+=1
    elif A[p][q-1]=="#" and A[p-1][q]==".":
        p+=1
    else:
        c=0
        break
print("Possible" if c else "Impossible")

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
A=[input()for i in range(H)]
for i in range(H):
    A[i]=A[i]+"."
A.append("."*(W+1))
p,q=1,1
c=1
for i in range(H+W-2):
    if A[p-1][q-1]==".":
        c=0
        break
    if A[p][q-1]=="." and A[p-1][q]=="#":
        q+=1
    elif A[p][q-1]=="#" and A[p-1][q]==".":
        p+=1
    else:
        c=0
        break
print("Possible" if c else "Impossible")

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
a=[input() for i in range(h)]
for i in range(h-1):
  for j in range(w-1):
    if a[i][j]=='#':
      if a[i+1][j]=='#' and a[i][j+1]=='#':
        print('Impossible')
        exit()
      if a[i+1][j]!='#' and a[i][j+1]!='#':
        print('Impossible')
        exit()
print('Possible')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# A - Shik and Stone
import sys
sys.setrecursionlimit(10**7)
H,W = map(int,input().split())
mp = [list(input()) for _ in range(H)]

dw = [1,0]
dh = [0,1]

seen = [[False]*W for _ in range(H)]
def dfs(h,w):
    seen[h][w] = True
    # まず右に進もうとする
    nxt_h = h + dh[0]
    nxt_w = w + dw[0]
    if not(-1<nxt_w<W): 
        return
    # 右が壁なら下に進む
    if mp[nxt_h][nxt_w] == '.':
        nxt_h = h + dh[1]
        nxt_w = w + dw[1]
    if not(-1<nxt_h<H):
        return
    if (seen[nxt_h][nxt_w] == True) or (mp[nxt_h][nxt_w] == '.'):
        return
    dfs(nxt_h,nxt_w)
        
dfs(0,0)

result = 'Possible'
for h in range(H):
    for w in range(W):
        if mp[h][w] == '#':
            if seen[h][w] == False:
                result = 'Impossible'
                break
print(result)

Submission status: Wrong Answer

Solution code:
# A - Shik and Stone
import sys
sys.setrecursionlimit(10**7)
H,W = map(int,input().split())
mp = [list(input()) for _ in range(H)]

dw = [1,0]
dh = [0,1]

seen = [[False]*W for _ in range(H)]
def dfs(h,w):
    seen[h][w] = True
    # まず右に進もうとする
    nxt_h = h + dh[0]
    nxt_w = w + dw[0]
    if not(-1<nxt_w<W): 
        return
    # 右が壁なら下に進む
    if mp[nxt_h][nxt_w] == '.':
        nxt_h = h + dh[1]
        nxt_w = w + dw[1]
    if not(-1<nxt_h<H):
        return
    if (seen[nxt_h][nxt_w] == True) or (mp[nxt_h][nxt_w] == '.'):
        return
    dfs(nxt_h,nxt_w)

result = 'Possible'
for h in range(H):
    for w in range(W):
        if mp[h][w] == '#':
            if seen[h][w] == False:
                result = 'Impossible'
                break
print(result)

Submission status: Wrong Answer

Solution code:
# A - Shik and Stone
H,W = map(int,input().split())
mp = [list(input()) for _ in range(H)]

dw = [1,0]
dh = [0,1]

seen = [[False]*W for _ in range(H)]
def dfs(h,w):
    seen[h][w] = True
    # まず右に進もうとする
    nxt_h = h + dh[0]
    nxt_w = w + dw[0]
    if not(-1<nxt_w<W): 
        return
    # 右が壁なら下に進む
    if mp[nxt_h][nxt_w] == '.':
        nxt_h = h + dh[1]
        nxt_w = w + dw[1]
    if not(-1<nxt_h<H):
        return
    if (seen[nxt_h][nxt_w] == True) or (mp[nxt_h][nxt_w] == '.'):
        return
    dfs(nxt_h,nxt_w)
        
dfs(0,0)
for S in seen:
    print(S)

result = 'Possible'
for h in range(H):
    for w in range(W):
        if mp[h][w] == '#':
            if seen[h][w] == False:
                result = 'Impossible'
                break
print(result)

Submission status: Wrong Answer

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

print("Possible")

Submission status: Wrong Answer

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]

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

while now != [h-1,w-1]:
    if now[0] == h-1:
        if grid[h-1][now[1]+1] == "#" and grid[h-1][max(now[1]-1,0)] == ".":
            now = [h-1, now[1]+1]
        else:
            print("Impossible")
            exit()
    elif now[1] == w-1:
        if grid[now[0]+1][w-1] == "#" and grid[max(now[0]-1,0)][w-1] == ".":
            now = [now[0]+1, w-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()

print("Possible")

Submission status: Wrong Answer

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]

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

while now != [h-1,w-1]:
    if now[0] == h-1:
        if grid[h-1][now[1]+1] == "#" and grid[h-1][now[1]-1] == ".":
            now = [h-1, now[1]+1]
        else:
            print("Impossible")
            exit()
    elif now[1] == w-1:
        if grid[now[0]+1][w-1] == "#" and grid[now[0]-1][w-1] == ".":
            now = [now[0]+1, w-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()

print("Possible")

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque


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 = []
gl = []
now = [0,0]
nowl = [[0,0]]

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

while now != [h-1,w-1]:
    if now[0] == h-1:
        if grid[h-1][now[1]+1] == "#":
            now = [h-1, now[1]+1]
            continue
        else:
            print("Impossible")
            exit()
    elif now[1] == w-1:
        if grid[now[0]+1][w-1] == "#":
            now = [now[0]+1, w-1]
            continue
        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()
    nowl.append(now)

nowl.append([h-1,w-1])

for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            gl.append([i,j])

if gl == nowl:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque


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]

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

while now != [h-1,w-1]:
    if now[0] == h-1:
        if grid[h-1][now[1]+1] == "#":
            now = [h-1, now[1]+1]
            continue
        else:
            print("Impossible")
            exit()
    elif now[1] == w-1:
        if grid[now[0]+1][w-1] == "#":
            now = [now[0]+1, w-1]
            continue
        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()

print("Possible")

Submission status: Wrong Answer

Solution code:
def search(y,x,oy,ox):
    if y == h-1 and x == w-1:
        return True
    l = []
    for i,j in t:
        ny,nx = y+i,x+j
        if (0 <= ny < h and 0 <= nx < w) and not (ny == oy and nx == ox):
            if a[ny][nx] == "#":
                l.append((ny,nx))
    #print(l)
    if 1 < len(l) or len(l) == 0:
        return False
    else:
        return search(l[0][0],l[0][1],y,x)

h,w = map(int,input().split())
a = [list(input()) for i in range(h)]
t = ((0,1),(1,0))

f = search(0,0,0,0)
print("Possible" if f else "Impossible")

Submission status: Wrong Answer

Solution code:
def check(h, w):
  if A[h][w] != r:
    return True
  if h == H - 1 and w == W - 1:
    return True
  cnt = 0
  if h + 1 < H:
    cnt += A[h + 1][w] == r
  if w + 1 < W:
    cnt += A[h][w + 1] == r
  if cnt == 1:
    return True
  else:
    return False

H, W = list(map(int, input().split()))
A = [list(input()) for _ in range(H)]
r = "#"

for i in range(H):
  for j in range(W):
    if not check(i, j):
      print("Impossible")
      exit()

print("Possible")

Submission status: Wrong Answer

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

if ((A=="#").sum(axis=0)>2).sum()>=1 or ((A=="#").sum(axis=1)>2).sum()>=1:
  print("Impossible")
else:
  print("Possible")

Submission status: Wrong Answer

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

x = 0
y = 0
while x < h or y < w:
    print(x, y)
    if x < h - 1 and grid[x + 1][y] == "#":
        grid[x][y] = "."
        x += 1
    elif y < w - 1 and grid[x][y + 1] == "#":
        grid[x][y] = "."
        y += 1
    else:
        break

if x != h - 1 or y != w - 1:
    print("Impossible")
else:
    grid[x][y] = "."
    for line in grid:
        if "#" in line:
            print("Impossible")
            quit()
    print("Possible")

Submission status: Wrong Answer

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

for line in grid:
    print(line)

x = 0
y = 0
while x < h or y < w:
    print(x, y)
    if x < h - 1 and grid[x + 1][y] == "#":
        grid[x][y] = "."
        x += 1
    elif y < w - 1 and grid[x][y + 1] == "#":
        grid[x][y] = "."
        y += 1
    else:
        break

if x != h - 1 or y != w - 1:
    print("Impossible")
else:
    grid[x][y] = "."
    for line in grid:
        if "#" in line:
            print("Impossible")
            quit()
    print("Possible")

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
v=[[1]*w for _ in range(h)]
q=[(0,0)]
dxy=((-1,0),(0,-1),(1,0),(0,1))
while q:
  x,y=q.pop()
  v[x][y]=0
  for dx,dy in dxy:
    nx=x+dx
    ny=y+dy
    if not(0<=nx<h and 0<=ny<w) or s[nx][ny]=='.':continue
    elif v[nx][ny] and (dx==-1 or dy==-1):
      print('Impossible')
      exit()
    elif v[nx][ny]:q+=[(nx,ny)]
print('Possible')

Submission status: Wrong Answer

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

g = []
for _ in range(h):
    a = input() + "?"
    g.append(list(a))

g.append(["?"]*w)

y, x = 0, 0

for _ in range(h+w-2):
    if g[y+1][x] == "#" and g[y][x+1] != "#":
        y += 1
    elif g[y][x+1] == "#" and g[y+1][x] != "#":
        x += 1
    else:
        print("Impossible")
        exit()
print("Possible")

Submission status: Wrong Answer

Solution code:
import sys
import queue
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = queue.Queue()
d.put([0, 0, 0])
vals = set()

while not d.empty():
    now = d.get()
    a[now[0]][now[1]] = '#'
    if now[2] in vals:
        print('Impossible')
        sys.exit()
    else:
        vals.add(now[2])
        
    if now[0] == h-1 and now[1] == w-1:
        print('Possible')
        sys.exit()
    else:
        if now[0]+1 < h:
            if a[now[0]+1][now[1]] == '#':
                d.put([now[0]+1, now[1], now[2]+1])
        if now[1]+1 < w:
            if a[now[0]][now[1]+1] == '#':
                d.put([now[0], now[1]+1, now[2]+1])        
print('Impossible')

Submission status: Wrong Answer

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

d = queue.Queue()
d.put([0, 0, 0])
vals = set()
while not d.empty():
    now = d.get()
    a[now[0]][now[1]] = 'a'
    if now[2] in vals:
        print('Impossible')
        sys.exit()
    else:
        vals.add(now[2])
        
    if now[0] == h-1 and now[1] == w-1:
        print('Possible')
        sys.exit()
    else:
        if now[0]+1 < h:
            if a[now[0]+1][now[1]] == '#':
                d.put([now[0]+1, now[1], now[2]+1])
        if now[1]+1 < w:
            if a[now[0]][now[1]+1] == '#':
                d.put([now[0], now[1]+1, now[2]+1])        
print('Impossible')

Submission status: Wrong Answer

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

d = queue.Queue()
d.put([0, 0, 0])
vals = set()
while not d.empty():
    now = d.get()
    a[now[0]][now[1]] = 'a'
    if now[2] in vals:
        print('Impossible')
        sys.exit()
    else:
        vals.add(now[2])
        
    if now[0] == h-1 and now[1] == w-1:
        print('Possible')
        sys.exit()
    else:
        if now[0]+1 < h:
            if a[now[0]+1][now[1]] == '#':
                d.put([now[0]+1, now[1], now[2]+1])
        if now[1]+1 < w:
            if a[now[0]][now[1]+1] == '#':
                d.put([now[0], now[1]+1, now[2]+1])        
print('Impossible')

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
l = []
for i in range(h):
    l.append(list(input()) + ["."])
l[-1][w-1] = "g"
l.append(["."]*(w+1))

def dfs(x, y):
    if x == w or y == h or l[y][x] == ".":
        return
    elif l[y][x] == "g":
        print("Possible")
        exit()
    else:
        if l[y][x+1] == "#" and l[y+1][x] == "#":
            print("Impossible")
            exit()
        dfs(x+1, y)
        dfs(x, y+1)
dfs(0, 0)
print("Impossible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
l = []
for i in range(h):
    l.append(list(input()))
l[h-1][w-1] = "g"

def dfs(x, y):
    if x == w or y == h or l[y][x] == ".":
        return
    elif l[y][x] == "g":
        print("Possible")
        exit()
    else:
        if x+1 != w and l[y][x+1] == "#" and y+1 != h and l[y+1][x] == "#":
            print("Impossible")
            exit()
        dfs(x+1, y)
        dfs(x, y+1)

ans = False
dfs(0, 0)
print("Impossible")

Submission status: Wrong Answer

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

def dfs(x, y):
    field[x][y] = '.'
    if y + 1 < w:
        dfs(x, y+1)
        if x + 1 < h:
            dfs(x+1, y+1)

dfs(0, 0)

flg = True

for i in range(h):
    for j in range(w):
        if field[i][j] == '#':
            flg = False
            break

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

Submission status: Wrong Answer

Solution code:
# def dfs(y, x):
#     if gridgraph[y+1][x] == "#" and y+1 != H:
#         flag[y+1][x] = True
#         dfs(y+1, x)
#     elif gridgraph[y][x+1] == "#" and x+1 != W:
#         flag[y][x+1] = True
#         dfs(y, x+1)
#     elif y == H-1 and x == W-1:
#         return

from collections import deque

H, W = map(int, input().split())
gridgraph = [input() for _ in range(H)]
# 移動経路を右or下のみに限定して，目的地に着いたかどうか判定する, 深さ優先探索しかない, 幅優先探索で右と下が同時に#なら終わりという制約でもいいかも
q = deque()
q.append([0, 0])
flag = [[False]*W for _ in range(H)]
adjacents = [[1, 0], [0, 1]]
while len(q):
    ny, nx = q.popleft()
    flag[ny][nx] = True
    if (ny+1 != H and gridgraph[ny+1][nx] == "#") and (nx+1 != W and gridgraph[ny][nx+1] == "#"):
        break
    if (ny+1 != H and gridgraph[ny+1][nx] != "#") and (nx+1 != W and gridgraph[ny][nx+1] != "#"):
        break
    for dy, dx in adjacents:
        if ny+dy == H or nx+dx == W:
            continue
        if gridgraph[ny+dy][nx+dx] == "#":
            q.append([ny+dy, nx+dx])

if ny == H-1 and nx == W-1:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
c = [0]*(h+2)
for i in range(1,h+1):
    c[i] = [0] + list(input()) + [0]
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

x,y = 1,1

ans = 1
while 1:
    if x == h and y == w:
        break
    
    s = 0
    t = 0
    if c[x+1][y] == "#":
        s = 1
    if c[x][y+1] == "#":
        t = 1
            
    if s == 1 and t == 1:
        ans = 0
        break
    elif s == 0 and t == 0:
        ans = 0
        break
    elif s == 1:
        x += 1
    else:
        y += 1
        
print(["Impossible","Possible"][ans])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
c = [0]*h
for i in range(h):
    c[i] = list(input())

x,y = 0,0

ans = 1
while 1:
    if x == h-1 and y == w-1:
        break
    
    s = 0
    t = 0
    if x < h-1:
        if c[x+1][y] == "#":
            s = 1
    if y < w-1:
        if c[x][y+1] == "#":
            t = 1
            
    if s == 1 and t == 1:
        ans = 0
        break
    elif s == 0 and t == 0:
        ans = 0
        break
    elif s == 1:
        x += 1
    else:
        y += 1
        
print(["Impossible","Possible"][ans])

Submission status: Wrong Answer

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

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

x = 0
y = 0

while True:
    c = []
    neighbours = 0
    if x != w-1:
        c.append([x+1, y, 1])
    if y != h-1:
        c.append([x, y+1, 3])

    for coords in c:
        if grid[coords[1]][coords[0]] == "#":
            neighbours += 1
            x2 = coords[0]
            y2 = coords[1]

    if neighbours != 1:
        print("Impossible")
        break

    c = []
    neighbours = 0
    if x != 0:
        c.append([x-1, y, 0])
    if y != 0:
        c.append([x, y-1, 2])

    for coords in c:
        if grid[coords[1]][coords[0]] == "#":
            neighbours += 1

    if neighbours > 1:
        print("Impossible")
        break

    if x == w-1 and y == h-1:
        print("Possible")
        break

    x = x2
    y = y2