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())
ban = [list(input()) for _ in range(H)]
tf = [[False for i in range(W)] for j in range(H)]
for i in range(H):
    for j in range(W):
        if ban[i][j] == ".":
            tf[i][j] = True
q = [[0, 0]]

while len(q) > 0:
    i, j = q.pop()
    if i >= H or j >= W:
        continue
    if ban[i][j] == ".":
        continue
    tf[i][j] = True
    q.append([i+1, j])
    q.append([i, j+1])

if tf[-1][-1]:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
"""
1.
i-1行目の右端のマスとi行目の左端のマスが隣接しており、
それらの行においてはそれ以外のマスは隣接していないこと。

2.
i行目の右端のマスとi+1行目の左端のマスが隣接しており、
それらの行においてはそれ以外のマスは隣接していないこと。

以上2点を満たせば'Possible'を出力すればよさそう。
"""
H, W = map(int, input().split())
table = [input() for _ in range(H)]
for i in range(1, H - 1):
    li_pre = [i for i, x in enumerate(table[i - 1]) if x == "#"]
    li_now = [i for i, x in enumerate(table[i]) if x == "#"]
    li_next = [i for i, x in enumerate(table[i + 1]) if x == "#"]
    if len(set(li_pre) & set(li_now)) == 1 and li_pre[-1] == li_now[0] and \
        len(set(li_now) & set(li_next)) == 1 and li_now[-1] == li_next[0]:
        continue
    else:
        print('Impossible')
        exit()
print('Possible')

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque

    h, w = map(int, readline().split())
    a = list()
    a.append("." * (w + 2))
    a.extend(["." + input() + "." for _ in range(h)])
    a.append("." * (w + 2))

    que = deque()
    que.append((1, 1))

    while que:
        cr, cc = que.popleft()
        if (cr, cc) == (h, w):
            return print("Possible")
        if a[cr + 1][cc] == "#":
            que.append((cr + 1, cc))
        if a[cr][cc + 1] == "#":
            que.append((cr, cc + 1))
        if a[cr + 1][cc] == a[cr][cc + 1] == "#":
            return print("Impossible")
        if a[cr - 1][cc] == a[cr][cc - 1] == "#":
            return print("Impossible")

    return print("Impossible")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque

    h, w = map(int, readline().split())
    a = [input() + "." for _ in range(h)]
    a.append("." * (w + 1))

    que = deque()
    que.append((0, 0))

    while que:
        cr, cc = que.popleft()
        if (cr, cc) == (h - 1, w - 1):
            return print("Possible")

        if a[cr + 1][cc] == "#":
            que.append((cr + 1, cc))
        if a[cr][cc + 1] == "#":
            que.append((cr, cc + 1))
        if a[cr + 1][cc] == a[cr][cc + 1] == "#":
            return print("Impossible")

    return print("Impossible")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
a = [sr() for i in range(h)]
def dfs():
    q = deque([[0,0]])
    while q:
        x, y= q.popleft()
        for dx,dy in [[1,0], [0,1]]:
            nx = x+dx
            ny = y+dy
            if nx < w and ny < h and a[ny][nx] == '#':
                q.append([nx,ny])
                if nx == w-1 and ny == h-1:
                    return True
    return False
if dfs():
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

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

def dfs(x, y, ans):
    if a[x][y] == ".":
        return
    elif [x, y] == [h, w] or cnt > ans+1:
        if ans + 1 == cnt:
            print("Possible")
        else:
            print("Impossible")
        exit()

    for v in [[1, 0], [0, 1], [0, -1], [-1, 0]]:
        dfs(x + v[0], y + v[1], ans + 1)

h, w = map(int, input().split())
a = [["."]*w]
a.extend([list("." + input() + ".") for x in range(h)])
a.append(["."]*w)
cnt = 0
for i in range(1,h+1):
    cnt += a[i].count("#")
dfs(1, 1 , 0)

Submission status: Wrong Answer

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

import sys
from collections import deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


# adjacent_2
def adjacent_2(h, w, H, W):
    ret = []
    for (dh, dw) in [(0, 1), (1, 0)]:
        h_ = h + dh
        w_ = w + dw
        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


def adjacent_2_(h, w, H, W):
    ret = []
    for (dh, dw) in [(0, -1), (-1, 0)]:
        h_ = h + dh
        w_ = w + dw
        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


H, W = map(int, readline().split())
M = [list(readline().decode().rstrip()) for _ in range(H)]

que = deque([(0, 0)])
while len(que) != 0:
    acc = que.popleft()
    if acc == (H - 1, W - 1):
        break
    ret = adjacent_2(*acc, H, W)
    cnt = adjacent_2_(*acc, H, W)
    ret = [pos for pos in ret if M[pos[0]][pos[1]] == '#']
    cnt = [pos for pos in cnt if M[pos[0]][pos[1]] == '#']

    if (len(ret) != 1) or (len(cnt) > 1):
        print("Impossible")
        sys.exit()
    que.append(*ret)

print("Possible")

Submission status: Wrong Answer

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

import sys
from collections import deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


# adjacent_2
def adjacent_2(h, w, H, W):
    ret = []
    for (dh, dw) in [(0, 1), (1, 0)]:
        h_ = h + dh
        w_ = w + dw
        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


H, W = map(int, readline().split())
M = [list(readline().decode().rstrip()) for _ in range(H)]

que = deque([(0, 0)])
while len(que) != 0:
    acc = que.popleft()
    if acc == (H - 1, W - 1):
        break
    ret = adjacent_2(*acc, H, W)
    ret = [pos for pos in ret if M[pos[0]][pos[1]] == '#']

    if len(ret) != 1:
        print("Impossible")
        sys.exit()
    que.append(*ret)

print("Possible")

Submission status: Wrong Answer

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

a = [tuple(input()) for i in range(H)]

i = 0
j = 0
L = 0
res = True

while (i!=H-1 or j !=W-1) and res:
    if j < W-1:
        while a[i][j] == '#':
            j += 1
            if j == W-1:
                break
    for k in range(j,W):
        if a[i][k] == '#':
            res =False
            break
    if i < H-1:
        i+=1
        for k in range(i,H):
            for m in range(L,j-1):
                if a[k][m] == '#':
                    res = False
                    break
            if res == False:
                break
        L = j-1
    

if res and a[i][j] == '#':
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

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

a = [tuple(input()) for i in range(H)]

i = 0
j = 0
res = True

while (i!=H-1 or j+1 !=W-1) and res:
    if a[i][j] == '#': # 今の地点が'.'
        if j+1 < W-1:
            while a[i][j+1] == '#': #'.'まで右へ進む
                j += 1
                if j == W-1:
                    break
    else:
        res = False
        break
    for k in range(j+1,W):
        if a[i][k] == '#': # 残りのマスに'#'があれば終了
            res = False
            break
    
    if i < H-1:
        i+=1
        for k in range(j):
            if a[i][k] == '#': # 左からj番目までのマスに'#'があれば終了
                res = False
                break

if res and a[i][j+1] == '#':
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

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

a = [tuple(input()) for i in range(H)]

i = 0
j = 0
res = True

if a[i][j] == '.': # 今の地点が'.'
    res = False
    exit()

while (i!=H-1 or j !=W-1) and res:
    if 1 <= i and a[i][j-1] == '.': # 今の地点が'.'
        res = False
        break
    while a[i][j] == '#' and j !=W-1: #'.'まで右へ進む
        j += 1
    if j < W-1:
        for k in range(j,W):
            if a[i][k] == '#': # 残りのマスに'#'があれば終了
                res = False
                break
    if i < H-1:
        i+=1
    
    for k in range(j-1):
        if a[i][k] == '#': # 左からj番目までのマスに'#'があれば終了
            res = False
            break
if res and a[i][j] == '#':
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

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

a = [tuple(input()) for i in range(H)]

i = 0
j = 0
res = True

if a[i][j] == '.': # 今の地点が'.'
    res = False
    exit()

while (i!=H-1 or j !=W-1) and res:
    if 1 <= i and a[i][j] == '.': # 今の地点が'.'
        res = False
        break
    while a[i][j] == '#' and j !=W-1: #'.'まで右へ進む
        j += 1
    if j < W-1:
        for k in range(j,W):
            if a[i][k] == '#': # 残りのマスに'#'があれば終了
                res = False
                break
    if i < H-1:
        i+=1
    
    for k in range(j-1):
        if a[i][k] == '#': # 左からj番目までのマスに'#'があれば終了
            res = False
            break
if res and a[i][j] == '#':
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

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

a = [tuple(input()) for i in range(H)]

i = 0
j = 0
res = True

while (i!=H-1 or j !=W-1) and res:
    if a[i][j] == '.': # 今の地点が'.'
        res = False
        break
    while a[i][j] == '#' and j !=W-1: #'.'まで右へ進む
        j += 1
    if j < W-1:
        for k in range(j,W):
            if a[i][k] == '#': # 残りのマスに'#'があれば終了
                res = False
                break
    if i < H-1:
        i+=1
    
    for k in range(j-1):
        if a[i][k] == '#': # 左からj番目までのマスに'#'があれば終了
            res = False
            break
if res and a[i][j] == '#':
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

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

a = [tuple(input()) for i in range(H)]

i = 0
j = 0
res = True

while (i!=H-1 or j !=W-1) and res:
    while a[i][j] == '#' and j !=W-1: #'.'まで右へ進む
        j += 1
    if j < W-1:
        for k in range(j,W):
            if a[i][k] == '#': # 残りのマスに'#'があれば終了
                res = False
                break
    if i < H-1:
        i+=1
    
    for k in range(j-1):
        if a[i][k] == '#': # 左からj番目までのマスに'#'があれば終了
            res = False
            break
if res and a[i][j] == '#':
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

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

a = [tuple(input()) for i in range(H)]

i = 0
j = 0
res = True

while (i!=H-1 or j !=W-1) and res:
    while a[i][j] == '#' and j !=W-1: #'.'まで右へ進む
        j += 1
    if j < W-1:
        for k in range(j,W):
            if a[i][k] == '#': # 残りのマスに'#'があれば終了
                res = False
                break
    if i < H-1:
        i+=1
    
    for k in range(j-1):
        if a[i][k] == '#': # 左からj番目までのマスに'#'があれば終了
            res = False
            break
if res:
    print('Possible')
else:
    print('Impossible')

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
A = [[i for i in input()] for _ in range(H)]
ed = [["."]*W for _ in range(H)]
isable = False

def dfs(a, x, y):
    global isable
    if y < 0 or x < 0 or y > H-1 or x > W-1:
        return
    if ed[y][x] == "#":
        return
    if A[y][x] == ".":
        return
    ed[y][x] = "#"
    if y == H-1 and x == W-1:
        if ed == A: isable = True
        return
    dfs(a, x+1, y)
    dfs(a, x, y+1)

dfs(A,0,0)
if isable:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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

def dfs(a, x, y):
    global isable
    if y < 0 or x < 0 or y > H-1 or x > W-1:
        return
    if ed[y][x] == 1:
        return
    if A[y][x] == ".":
        return
    if y == H-1 and x == W-1:
        isable = True
        return
    ed[y][x] = 1
    dfs(a, x+1, y)
    dfs(a, x, y+1)

dfs(A,0,0)
if isable:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
table = []
for _ in range(h):
    table.append(list(input()))
if table[0][0] == "." or table[h - 1][w - 1] == ".":
    print("Impossible")
    exit()
stack = [[0, 0]]
while len(stack) > 0:
    cur = stack.pop()
    if cur[0] == h - 1 and cur[1] == w - 1:
        table[cur[0]][cur[1]] = "."
        break
    for step in [[0, 1], [1, 0]]:
        x, y = cur[1] + step[1], cur[0] + step[0]
        if x < w and y < h and table[y][x] == "#":
            table[y][x] = "."
            stack.append([y, x])
for y in range(h):
    for x in range(w):
        if table[y][x] == "#":
            print("Impossible")
            exit()

print("Possible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
table = []
for _ in range(h):
    table.append(list(input()))
if table[0][0] == "." or table[h - 1][w - 1] == ".":
    print("Impossible")
    exit()
stack = [[0, 0]]
flag = False
while len(stack) > 0 and not flag:
    cur = stack.pop()
    table[cur[0]][cur[1]] = "."
    for step in [[0, 1], [1, 0]]:
        x, y = cur[1] + step[1], cur[0] + step[0]
        if x < w and y < h and table[y][x] == "#":
            table[cur[0]][cur[1]] = "."
            if y == h - 1 and x == w - 1:
                table[y][x] = "."
                flag = True
                break
            stack.append([y, x])
for y in range(h):
    for x in range(w):
        if table[y][x] == "#":
            print("Impossible")
            exit()

print("Possible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
table = []
for _ in range(h):
    table.append(list(input()))
if table[0][0] == "." or table[h - 1][w - 1] == ".":
    print("Impossible")
    exit()
stack = [[0, 0]]
flag = False
while len(stack) > 0 and not flag:
    cur = stack.pop()
    table[cur[0]][cur[1]] = "."
    for step in [[0, 1], [1, 0]]:
        x, y = cur[1] + step[1], cur[0] + step[0]
        if x < w and y < h and table[y][x] == "#":
            if y == h - 1 and x == w - 1:
                table[y][x] = "."
                flag = True
                break
            stack.append([y, x])
for y in range(h):
    for x in range(w):
        if table[y][x] == "#":
            print("Impossible")
            exit()

print("Possible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
table = []
for _ in range(h):
    table.append(list(input()))
if table[0][0] == "." or table[h - 1][w - 1] == ".":
    print("Impossible")
    exit()
stack = [[0, 0]]
while len(stack) > 0:
    cur = stack.pop()
    table[cur[0]][cur[1]] = "."
    if cur[0] == h - 1 and cur[1] == w - 1:
        break
    for step in [[0, 1], [1, 0]]:
        x, y = cur[1] + step[1], cur[0] + step[0]
        if x < w and y < h and table[y][x] == "#":
            stack.append([y, x])
for y in range(h):
    for x in range(w):
        if table[y][x] == "#":
            print("Impossible")
            exit()

print("Possible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
table = []
for _ in range(h):
    table.append(list(input()))
if table[0][0] == "." or table[h - 1][w - 1] == ".":
    print("Impossible")
    exit()
stack = [[0, 0]]
while len(stack) > 0:
    cur = stack.pop()
    if cur[0] == h - 1 and cur[1] == w - 1:
        break
    for step in [[0, 1], [1, 0]]:
        x, y = cur[1] + step[1], cur[0] + step[0]
        if x < w and y < h and table[y][x] == "#":
            table[y][x] = "."
            stack.append([y, x])

for y in range(h):
    for x in range(w):
        if table[y][x] == "#":
            print("Impossible")
            exit()

print("Possible")

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
table = []
for _ in range(h):
    table.append(list(input()))
if table[0][0] == "." or table[h - 1][w - 1] == ".":
    print("Impossible")
    exit()
stack = [[0, 0]]
while len(stack) > 0:
    cur = stack.pop()
    table[cur[0]][cur[1]] = "."
    if cur[0] == h - 1 and cur[1] == w - 1:
        break
    for step in [[0, 1], [1, 0]]:
        x, y = cur[1] + step[1], cur[0] + step[0]
        if x < w and y < h and table[y][x] == "#":
            stack.append([y, x])

for y in range(h):
    for x in range(w):
        if table[y][x] == "#":
            print("Impossible")
            exit()

print("Possible")

Submission status: Wrong Answer

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

stack = [[0, 0]]
while len(stack) > 0:
    cur = stack.pop()
    table[cur[0]][cur[1]] = "."
    if cur[0] == h - 1 and cur[1] == w - 1:
        break
    for step in [[0, 1], [1, 0]]:
        x, y = cur[1] + step[1], cur[0] + step[0]
        if x < w and y < h and table[y][x] == "#":
            stack.append([y, x])

for y in range(h):
    for x in range(w):
        if table[y][x] == "#":
            print("Impossible")
            exit()

print("Possible")

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
a = [input()+'.' for i in range(h)]
a.append("."*(w+1))

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

Submission status: Wrong Answer

Solution code:
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
a = [input()+'.' for i in range(h)]
a.append("."*(w+1))
i = j = 0

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

Submission status: Wrong Answer

Solution code:
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
a = [input()+'.' for i in range(h)]
a.append("."*(w+1))
i = j = 0

while i < h or j < w:
        if a[i+1][j] == '#':
                i += 1
        elif a[i][j+1] == '#':
                j += 1
        elif i < h-1 or j < w-1:
                print("Impossible")
                exit()

        if i == h-1 and j == w-1:
                print("Possible")
                exit()
        elif a[i][j]==a[i+1][j]==a[i][j+1]==a[i+1][j+1]=='#':
                print("Impossible")
                exit()

Submission status: Wrong Answer

Solution code:
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, w = MAP()
a = [input()+'.' for i in range(h)]
a.append("."*(w+1))

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

Submission status: Wrong Answer

Solution code:
H, W=map(int, input().split())
cnt=0
for _ in range(H):
  a=list(input())
  cnt+=a.count("#")
if cnt==H*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)]
a.append('.'*W)

seen = [[False for i in range(W)] for j in range(H)]
h, w = 0, 0
while h < H and w < W:
    seen[h][w] = True

    top = h - 1
    under = h + 1
    right = w + 1
    left = w - 1

    if a[h][right] == a[under][w]:
        print('Impossible')
        exit()

    if h > 0 and w > 0:
        if (a[top][w] == '#' and not seen[top][w]) or (a[h][left] == '#' and not seen[h][left]):
            print('Impossible')
            exit()

    if a[h][right] == '#':
        w = right
    else:
        h = under

    if h == H-1 and w == W-1:
        print('Possible')
        exit()
print('Impossible')

Submission status: Wrong Answer

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

seen = [[False for i in range(W)] for j in range(H)]
h, w = 0, 0
while h < H and w < W:
    right = w + 1
    under = h + 1

    if a[h][right] == a[under][w]:
        print('Impossible')
        exit()
    if a[h][right] == '#':
        w = right
    else:
        h = under

    if h == H-1 and w == W-1:
        print('Possible')
        exit()
print('Impossible')

Submission status: Wrong Answer

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

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

cnt = 0
for aa in A:
    for aaa in aa:
        if aaa == '#':
            cnt += 1

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

Submission status: Wrong Answer

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

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

seen = [[False for x in range(W)] for _ in range(H)]
seen[0][0] = True
nx = [(0,0)]


def check(i, j):
    # 上
    if i > 0 and A[i-1][j] == '#' and seen[i-1][j] != True:
        # return -1
        print("Impossible")
        exit(0)

    # 左
    if j > 0 and A[i][j-1] == '#' and seen[i][j-1] != True:
        # return -1
        print("Impossible")
        exit(0)

    if i < H-1 and A[i+1][j] == '#':
        # seen[i+1][j] = True
        nx.append((i+1,j))
    
    if j < W-1 and A[i][j+1] == "#":
        # seen[i][j+1] = True
        nx.append((i,j+1))
    
    return 0

while len(nx) != 0:
    x, y = nx.pop()
    # print(x,y)
    seen[x][y] = True
    check(x, y)

#route check
for h in range(H):
    for w in range(W):
        if A[h][w] == '#' and seen[h][w] != True:
            print("Impossible")
            exit(0)

if seen[H-1][W-1]:
    print("Possible")
else:
    print("Impossible")

Submission status: Wrong Answer

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

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

seen = [[False for x in range(W)] for _ in range(H)]
seen[0][0] = True
nx = [(0,0)]


def check(i, j):
    # 上
    if i > 0 and A[i-1][j] == '#' and seen[i-1][j] != True:
        # return -1
        print("Impossible")
        exit(0)

    # 左
    if j > 0 and A[i][j-1] == '#' and seen[i][j-1] != True:
        # return -1
        print("Impossible")
        exit(0)

    if i < H-1 and A[i+1][j] == '#':
        # seen[i+1][j] = True
        nx.append((i+1,j))
    
    if j < W-1 and A[i][j+1] == "#":
        # seen[i][j+1] = True
        nx.append((i,j+1))
    
    return 0

while len(nx) != 0:
    x, y = nx.pop()
    # print(x,y)
    seen[x][y] = True
    check(x, y)

#route check
for h in range(H):
    for w in range(W):
        if A[h][w] == '#' and seen[h][w] != True:
            print("Impossible")
            exit(0)

print("Possible")

Submission status: Wrong Answer

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

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

seen = [[False for x in range(W)] for _ in range(H)]
seen[0][0] = True
nx = [(0,0)]


def check(i, j):
    # 上
    if i > 0 and A[i-1][j] == '#' and seen[i-1][j] != True:
        # return -1
        print("Impossible")
        exit(0)

    # 左
    if j > 0 and A[i][j-1] == '#' and seen[i][j-1] != True:
        # return -1
        print("Impossible")
        exit(0)

    if i < H-1 and A[i+1][j] == '#':
        # seen[i+1][j] = True
        nx.append((i+1,j))
    
    if j < W-1 and A[i][j+1] == "#":
        # seen[i][j+1] = True
        nx.append((i,j+1))
    
    return 0

while len(nx) != 0:
    x, y = nx.pop()
    # print(x,y)
    seen[x][y] = True
    check(x, y)

print("Possible")

Submission status: Wrong Answer

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

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

seen = [[False for x in range(W)] for _ in range(H)]
seen[0][0] = True
nx = [(0,0)]


def check(i, j):
    # 上
    if i > 0 and A[i-1][j] == '#' and seen[i-1][j] != True:
        # return -1
        print("Impossible")
        exit(0)

    # 左
    if j > 0 and A[i][j-1] == '#' and seen[i][j-1] != True:
        # return -1
        print("Impossible")
        exit(0)

    if i < H-1 and A[i+1][j] == '#':
        seen[i+1][j] = True
        nx.append((i+1,j))
    
    if j < W-1 and A[i][j+1] == "#":
        seen[i][j+1] = True
        nx.append((i,j+1))
    
    return 0

while len(nx) != 0:
    x, y = nx.pop()
    # print(x,y)
    check(x, y)

print("Possible")