Problem: 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.

Submission attempts (in order):
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')



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



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



def dfs(grid, start, wall, h, w):
    stack = []
    push, pop = stack.append, stack.pop
    push(start)
    grid[start[0]][start[1]] = wall
    dxy = [(0,1), (1,0)]

    while stack:
        h, w = pop()
        cnt = 0
        for dx,dy in dxy:
            x, y = w+dx, h+dy
            if grid[y][x] == wall:
                continue
            push((y,x))
            grid[y][x] = wall
            cnt += 1
        if cnt > 1:
            return False
    for i in range(1, h+1):
        for j in range(1, w+1):
            if grid[i][j] != wall:
                return False
    return True


def resolve():
    h, w = map(int, input().split())
    grid = {}
    wall = '.'
    edges = [wall] * (w+2)
    grid = [edges]
    for i in range(h):
        s = input()
        grid.append([wall] + list(s) + [wall])
    grid.append(edges)
    print("Possible" if dfs(grid, (1, 1), wall, h, w) else "Impossible")

if __name__ == "__main__":
    resolve()


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted