Problem:


Score: 400 points

Problem statement

We have an H \times W grid whose squares are painted black or white. The square at the i-th row from the top and the j-th column from the left is denoted as (i, j).

Snuke would like to play the following game on this grid. At the beginning of the game, there is a character called Kenus at square (1, 1). The player repeatedly moves Kenus up, down, left or right by one square. The game is completed when Kenus reaches square (H, W) passing only white squares.

Before Snuke starts the game, he can change the color of some of the white squares to black. However, he cannot change the color of square (1, 1) and (H, W). Also, changes of color must all be carried out before the beginning of the game.

When the game is completed, Snuke's score will be the number of times he changed the color of a square before the beginning of the game. Find the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed, that is, Kenus can never reach square (H, W) regardless of how Snuke changes the color of the squares.  

The color of the squares are given to you as characters s_{i, j}. If square (i, j) is initially painted by white, s_{i, j} is .; if square (i, j) is initially painted by black, s_{i, j} is #.

Constraints

H is an integer between 2 and 50 (inclusive).

W is an integer between 2 and 50 (inclusive).

s_{i, j} is . or # (1 \leq i \leq H, 1 \leq j \leq W).

s_{1, 1} and s_{H, W} are ..

Input

Input is given from Standard Input in the following format:

H W
s_{1, 1}s_{1, 2}s_{1, 3} ... s_{1, W}
s_{2, 1}s_{2, 2}s_{2, 3} ... s_{2, W}
 :   :
s_{H, 1}s_{H, 2}s_{H, 3} ... s_{H, W}

Output

Print the maximum possible score that Snuke can achieve, or print -1 if the game cannot be completed.

Sample Input 1

3 3
..#
#..
...

Sample Output 1

2

The score 2 can be achieved by changing the color of squares as follows:

Sample Input 2

10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

Sample Output 2

209



Sample input:
3 3
..#
#..
...


Sample output:
2

Submission status: Wrong Answer

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

from collections import deque

H, W = map(int, input().split())

field = []
for _ in range(H):
    line = list(input())
    field.append(line)
# print(H, W, field)


def is_valid(i, j):
    cond_i = i >= 0 and i <= H - 1
    cond_j = j >= 0 and j <= W - 1
    return cond_i and cond_j


def adj(i, j):
    up, down = [i - 1, j], [i + 1, j]
    left, right = [i, j - 1], [i, j + 1]
    res = []
    for i_adj, j_adj in up, down, left, right:
        if is_valid(i_adj, j_adj):
            res.append([i_adj, j_adj])
    return res


def bfs(que, dist):
    while len(que) > 0:
        i, j = que.popleft()
        # print(f"i, j: {i}, {j}")
        for i_adj, j_adj in adj(i, j):
            # print(f"i_adj, j_adj: {i_adj}, {j_adj}")
            if dist[(i_adj, j_adj)] == -1:
                que.append([i_adj, j_adj])
                dist[(i_adj, j_adj)] = dist[(i, j)] + 1


que = deque()
keys = [(i, j) for i in range(H) for j in range(W)]
values = [-1 for _ in range(H * W)]
dist = dict(zip(keys, values))
# print(dist)

que.append([0, 0])
dist[(0, 0)] = 0
bfs(que, dist)

n_black = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            n_black += 1


if field[0][0] == '#':
    print(-1)
elif dist[(H - 1, W - 1)] == -1:
    print(-1)
else:
    steps_min = dist[(H - 1, W - 1)] + 1
    n_white = W * H - n_black
    ans = n_white - steps_min
    print(ans)

Submission status: Wrong Answer

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

from collections import deque

H, W = map(int, input().split())

field = []
for _ in range(H):
    line = list(input())
    field.append(line)
# print(H, W, field)


def is_valid(i, j):
    cond_i = i >= 0 and i <= H - 1
    cond_j = j >= 0 and j <= W - 1
    return cond_i and cond_j


def adj(i, j):
    up, down = [i - 1, j], [i + 1, j]
    left, right = [i, j - 1], [i, j + 1]
    res = []
    for i_adj, j_adj in up, down, left, right:
        if is_valid(i_adj, j_adj):
            res.append([i_adj, j_adj])
    return res


def bfs(que, dist):
    while len(que) > 0:
        i, j = que.popleft()
        # print(f"i, j: {i}, {j}")
        for i_adj, j_adj in adj(i, j):
            # print(f"i_adj, j_adj: {i_adj}, {j_adj}")
            if dist[(i_adj, j_adj)] == -1:
                que.append([i_adj, j_adj])
                dist[(i_adj, j_adj)] = dist[(i, j)] + 1


que = deque()
keys = [(i, j) for i in range(H) for j in range(W)]
values = [-1 for _ in range(H * W)]
dist = dict(zip(keys, values))
# print(dist)

que.append([0, 0])
dist[(0, 0)] = 0
bfs(que, dist)

n_black = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            n_black += 1


if field[0][0] == '#' or field[H - 1][W - 1] == '#':
    print(-1)
elif dist[(H - 1, W - 1)] == -1:
    print(-1)
else:
    steps_min = dist[(H - 1, W - 1)] + 1
    n_white = W * H - n_black
    ans = n_white - steps_min
    print(ans)

Submission status: Wrong Answer

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

from collections import deque

H, W = map(int, input().split())

field = []
for _ in range(H):
    line = list(input())
    field.append(line)
# print(H, W, field)


def is_valid(i, j):
    cond_i = i >= 0 and i <= H - 1
    cond_j = j >= 0 and j <= W - 1
    return cond_i and cond_j


def adj(i, j):
    up, down = [i - 1, j], [i + 1, j]
    left, right = [i, j - 1], [i, j + 1]
    res = []
    for i_adj, j_adj in up, down, left, right:
        if is_valid(i_adj, j_adj):
            res.append([i_adj, j_adj])
    return res


def bfs(que, dist):
    while len(que) > 0:
        i, j = que.popleft()
        # print(f"i, j: {i}, {j}")
        for i_adj, j_adj in adj(i, j):
            # print(f"i_adj, j_adj: {i_adj}, {j_adj}")
            if dist[(i_adj, j_adj)] == -1:
                que.append([i_adj, j_adj])
                dist[(i_adj, j_adj)] = dist[(i, j)] + 1


que = deque()
keys = [(i, j) for i in range(H) for j in range(W)]
values = [-1 for _ in range(H * W)]
dist = dict(zip(keys, values))
# print(dist)

que.append([0, 0])
dist[(0, 0)] = 0
bfs(que, dist)

n_black = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            n_black += 1


if field[0][0] == '#':
    print(-1)
elif dist[(H - 1, W - 1)] == 0 and H != 1 and W != 1:
    print(-1)
else:
    steps_min = dist[(H - 1, W - 1)] + 1
    n_white = W * H - n_black
    ans = n_white - steps_min
    print(ans)

Submission status: Wrong Answer

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

from collections import deque

H, W = map(int, input().split())

field = []
for _ in range(H):
    line = list(input())
    field.append(line)
# print(H, W, field)


def is_valid(i, j):
    cond_i = i >= 0 and i <= H - 1
    cond_j = j >= 0 and j <= W - 1
    return cond_i and cond_j


def adj(i, j):
    up, down = [i - 1, j], [i + 1, j]
    left, right = [i, j - 1], [i, j + 1]
    res = []
    for i_adj, j_adj in up, down, left, right:
        if is_valid(i_adj, j_adj):
            res.append([i_adj, j_adj])
    return res


def bfs(que, dist):
    while len(que) > 0:
        i, j = que.popleft()
        # print(f"i, j: {i}, {j}")
        for i_adj, j_adj in adj(i, j):
            # print(f"i_adj, j_adj: {i_adj}, {j_adj}")
            if dist[(i_adj, j_adj)] == -1:
                que.append([i_adj, j_adj])
                dist[(i_adj, j_adj)] = dist[(i, j)] + 1


que = deque()
keys = [(i, j) for i in range(H) for j in range(W)]
values = [-1 for _ in range(H * W)]
dist = dict(zip(keys, values))
# print(dist)

que.append([0, 0])
dist[(0, 0)] = 0
bfs(que, dist)

n_black = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            n_black += 1


if field[0][0] == '#':
    print(-1)
elif dist[(H - 1, W - 1)] == 0 and H == 1 and W == 1:
    print(-1)
else:
    steps_min = dist[(H - 1, W - 1)] + 1
    n_white = W * H - n_black
    ans = n_white - steps_min
    print(ans)

Submission status: Wrong Answer

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

from collections import deque

H, W = map(int, input().split())

field = []
for _ in range(H):
    line = list(input())
    field.append(line)
# print(H, W, field)


def is_valid(i, j):
    cond_i = i >= 0 and i <= H - 1
    cond_j = j >= 0 and j <= W - 1
    return cond_i and cond_j


def adj(i, j):
    up, down = [i - 1, j], [i + 1, j]
    left, right = [i, j - 1], [i, j + 1]
    res = []
    for i_adj, j_adj in up, down, left, right:
        if is_valid(i_adj, j_adj):
            res.append([i_adj, j_adj])
    return res


def bfs(que, dist):
    while len(que) > 0:
        i, j = que.popleft()
        # print(f"i, j: {i}, {j}")
        for i_adj, j_adj in adj(i, j):
            # print(f"i_adj, j_adj: {i_adj}, {j_adj}")
            if dist[(i_adj, j_adj)] == -1:
                que.append([i_adj, j_adj])
                dist[(i_adj, j_adj)] = dist[(i, j)] + 1


que = deque()
keys = [(i, j) for i in range(H) for j in range(W)]
values = [-1 for _ in range(H * W)]
dist = dict(zip(keys, values))
# print(dist)

que.append([0, 0])
dist[(0, 0)] = 0
bfs(que, dist)

n_black = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            n_black += 1


if field[0][0] == '#' or dist[(H - 1, W - 1)] == -1:
    print(-1)
else:
    steps_min = dist[(H - 1, W - 1)] + 1
    n_white = W * H - n_black
    ans = n_white - steps_min
    print(ans)

Submission status: Wrong Answer

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

from collections import deque

H, W = map(int, input().split())

field = []
for _ in range(H):
    line = list(input())
    field.append(line)
# print(H, W, field)


def is_valid(i, j):
    cond_i = i >= 0 and i <= H - 1
    cond_j = j >= 0 and j <= W - 1
    return cond_i and cond_j


def adj(i, j):
    up, down = [i - 1, j], [i + 1, j]
    left, right = [i, j - 1], [i, j + 1]
    res = []
    for i_adj, j_adj in up, down, left, right:
        if is_valid(i_adj, j_adj):
            res.append([i_adj, j_adj])
    return res


def bfs(que, dist):
    while len(que) > 0:
        i, j = que.popleft()
        # print(f"i, j: {i}, {j}")
        for i_adj, j_adj in adj(i, j):
            # print(f"i_adj, j_adj: {i_adj}, {j_adj}")
            if dist[(i_adj, j_adj)] == -1:
                que.append([i_adj, j_adj])
                dist[(i_adj, j_adj)] = dist[(i, j)] + 1


que = deque()
keys = [(i, j) for i in range(H) for j in range(W)]
values = [-1 for _ in range(H * W)]
dist = dict(zip(keys, values))
# print(dist)

que.append([0, 0])
dist[(0, 0)] = 0
bfs(que, dist)

n_black = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            n_black += 1


if field[0][0] == '#':
    print(-1)
else:
    steps_min = dist[(H - 1, W - 1)] + 1
    n_white = W * H - n_black
    ans = n_white - steps_min
    print(ans)

Submission status: Wrong Answer

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

from collections import deque

H, W = map(int, input().split())

field = []
for _ in range(H):
    line = list(input())
    field.append(line)
# print(H, W, field)


def is_valid(i, j):
    cond_i = i >= 0 and i <= H - 1
    cond_j = j >= 0 and j <= W - 1
    return cond_i and cond_j


def adj(i, j):
    up, down = [i - 1, j], [i + 1, j]
    left, right = [i, j - 1], [i, j + 1]
    res = []
    for i_adj, j_adj in up, down, left, right:
        if is_valid(i_adj, j_adj):
            res.append([i_adj, j_adj])
    return res


def bfs(que, dist):
    while len(que) > 0:
        i, j = que.popleft()
        # print(f"i, j: {i}, {j}")
        for i_adj, j_adj in adj(i, j):
            # print(f"i_adj, j_adj: {i_adj}, {j_adj}")
            if dist[(i_adj, j_adj)] == -1:
                que.append([i_adj, j_adj])
                dist[(i_adj, j_adj)] = dist[(i, j)] + 1


que = deque()
keys = [(i, j) for i in range(H) for j in range(W)]
values = [-1 for _ in range(H * W)]
dist = dict(zip(keys, values))
# print(dist)

que.append([0, 0])
dist[(0, 0)] = 0
bfs(que, dist)

n_black = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            n_black += 1

n_white = W * H - n_black
steps_min = dist[(H - 1, W - 1)] + 1
ans = n_white - steps_min

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
grid_graph = [list(input()) for _ in range(H)]
# 幅優先で最短経路を求めるだけ
q = deque()
q.append([0, 0])
distance = [[1000]*W for _ in range(H)]
distance[0][0] = 0
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while len(q):
    cy, cx = q.popleft()
    for dy, dx in adjacent:
        ny, nx = cy+dy, cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if distance[ny][nx] != 1000:
            continue
        if grid_graph[ny][nx] == "#":
            continue
        distance[ny][nx] = distance[cy][cx] + 1
        q.append([ny, nx])
black = 0
for i in range(H):
    for j in range(W):
        if grid_graph[i][j] == "#":
            black += 1
print(H*W - distance[H-1][W-1] - black - 1)  # 最後の-1は出発地点のマスを黒くできない分

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
moves = ((1, 0), (0, 1), (0, -1), (-1, 0))

def bfs(sy, sx):
    q = deque([[sy, sx]])
    dist = [[float('inf')]*w for _ in range(h)]
    dist[sy][sx] = 0 

    while q:
        y, x = q.popleft()
        for dy, dx in moves:
            ny = y + dy 
            nx = x + dx 
            if 0 <= ny < h and 0 <= nx < w and dist[ny][nx] == float('inf'):
                dist[ny][nx] = dist[y][x] + 1 
                q += [[ny, nx]]

    return dist 

d = bfs(0, 0)[h-1][w-1]
block = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            block += 1
print(h*w-d-block-1)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy
from collections import deque
sys.setrecursionlimit(10**6)

H, W = [int(n) for n in input().split(' ')]
S = [list(input()) for i in range(H)]

dist = [[-1]*W for i in range(H)]
dist[0][0] = 1
Q = deque([])
Q.append([0,0])
while Q:
    y, x = Q.popleft()
    if [y, x] == [H-1, W-1]:
        break
    for i, j in [[1,0], [-1,0], [0,1], [-1,0]]:
        if y+i<0 or x+j<0 or y+i>=H or x+j>=W:
            continue
        if dist[y+i][x+j]==-1 and S[y+i][x+j]==".":
            dist[y+i][x+j] = dist[y][x] + 1
            Q.append([y+i, x+j])
if dist[H-1][W-1]==-1:
    print(-1)
else:
    white = 0
    for i in range(H):
        for j in range(W):
            if S[i][j]==".":
                white += 1
    print(white-dist[H-1][W-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

import numpy as np
import sys
#input = sys.stdin.readline

sys.setrecursionlimit(5000)

def bfs(point, field, target, H, W):
    visited = [[-1 for _ in range(W+2)] for _ in range(H+2)]
    visited[point[0]][point[1]] = 1
    que = deque()
    que.append(point)

    while True:
        v = que.popleft()
        depth = visited[v[0]][v[1]]
        for a in [(v[0]-1, v[1]), (v[0]+1, v[1]), (v[0], v[1]-1), (v[0], v[1]+1)]:
            if field[a[0]][a[1]] == 0 and visited[a[0]][a[1]] == -1:
                visited[a[0]][a[1]] = 1 + depth
                if a == target:
                    print(visited)
                    return visited[a[0]][a[1]]
                else:
                    que.append(a)
        if len(que) == 0:
            return 0

H, W = list(map(int, input().split()))
target = (H, W)
field = [[-1] * (W+2)]
number_of_whites = 0
for _ in range(H):
    s = input()
    number_of_whites += s.count('.')
    field.append([-1] + [0 if c=='.' else -1 for c in s] + [-1])
field += [[-1] * (W+2)]

shortest_path = bfs((1, 1), field, target, H, W)
if shortest_path > 0:
    print(number_of_whites - shortest_path)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

import numpy as np
import sys
#input = sys.stdin.readline

sys.setrecursionlimit(5000)

def main():
    H, W = list(map(int, input().split()))
    target = (H, W)
    field = [[-1] * (W+2)]
    number_of_whites = 0
    for _ in range(H):
        s = input()
        number_of_whites += s.count('.')
        field.append([-1] + [0 if c=='.' else -1 for c in s] + [-1])
    field += [[-1] * (W+2)]

    visited = []
    point = (1, 1)
    que = deque()
    que.append((point, 1))
    shortest_path = 0
    
    while len(que) > 0:
        v, depth = que.popleft()
        visited.append(v)
        for a in [(v[0]-1, v[1]), (v[0]+1, v[1]), (v[0], v[1]-1), (v[0], v[1]+1)]:
            if field[a[0]][a[1]] == 0 and a not in visited:
                if a == target:
                    shortest_path = depth + 1
                    break
                else:
                    que.append((a, depth+1))
    if shortest_path > 0:
        print(number_of_whites - shortest_path)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque

    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]
    f_inf = float('inf')
    maze = [[f_inf] * w for _ in range(h)]
    maze[0][0] = 0
    que = deque([[0, 0]])
    while que:
        y, x = que.popleft()
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_y, next_x = y + i, x + j
            if -1 < next_y < h and -1 < next_x < w:
                if grid[next_y][next_x] != "#":
                    if maze[next_y][next_x] > maze[y][x] + 1:
                        maze[next_y][next_x] = maze[y][x] + 1
                        que.append([next_y, next_x])

    res = h * w - (maze[h - 1][w - 1] + 1)
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                res -= 1
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
def bfs():
    #sからそのマスまでの最短距離を保存する配列
    d = [[float("inf")]*m for _ in range(n)]
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    #s,gの座標を得る
    sx,sy = 0,0
    gx,gy = n-1,m-1
    #キューにs座標をセットしてsのマスを0にする
    q = deque([])
    q.append((sx,sy))
    d[sx][sy] = 0
    
    #全部の行けるところをqueに入れてsからの距離を＋1ずつしていく
    while q:
        p = q.popleft()
        #gでbreakしなければ行ける全てのマスまでの最短距離を求める事になる
        if p[0] == gx and p[1] == gy:
            break
        #上下左右のマスを調べる
        for k in range(4):
            xi,yi = p[0]+dx[k],p[1]+dy[k]
            #そのマスにいけて行ったことないなら、そこを起点に再起＋そこまでの距離を求める
            if 0 <= xi < n and 0 <= yi < m and maze[xi][yi] != "#" and d[xi][yi] == float("inf"):
                q.append((xi,yi))
                d[xi][yi] = d[p[0]][p[1]] + 1

    #gまでの最短距離を返す
    return d[gx][gy]

n,m = map(int, input().split())
maze = [list(input()) for _ in range(n)]
c = 0
for i in range(n):
    for j in range(m):
        if maze[i][j] == ".":
            c += 1
print(c - bfs() -1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
M=[input() for _ in range(H)]
D=[[10**5]*W for _ in range(H)]

cnt=0
for i in range(H):
    cnt+=M[i].count('#')

visited=[[0]*W for _ in range(H)]
q=deque([[0,0,0]])

while q:
    x,y,dist=q.popleft()
    if visited[x][y]==1:
        continue
    visited[x][y]=1
    D[x][y]=dist
    
    for i,j in [(1,0),(-1,0),(0,1),(0,-1)]:
        if x+i>=H or y+j>=W or x+i<0 or y+j<0:
            continue
        if M[x+i][y+j]=='#':
            continue
        q.append([x+i,y+j,dist+1])

print((H*W-1-D[H-1][W-1])-cnt)

Submission status: Wrong Answer

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

ex = [[0] * w for i in range(h)]

ex[0][0] = 1
do = [[0,0]]
check = [[1,0],[-1,0],[0,1],[0,-1]]

white = 0
for i in s:
  white += i.count('.')




while(len(do)!=0):
  x,y = do.pop(0)

  
  for i,j in check:
    a = x + i
    b = y + j
    if(-1<a<h and -1<b<w):
      if(a == h-1 and b == w-1):
        print(white-(ex[x][y])-1)
        exit()
      elif(ex[a][b] == 0 and s[a][b] =='.'):
        ex[a][b] = ex[x][y] +1
        do.append([a,b])

Submission status: Wrong Answer

Solution code:
import sys

def input():
    return sys.stdin.buffer.readline()[:-1]

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

for i in range(1, h+1):
    for j in range(1, w+1):
        if maze[i][j] == '#':
            cou += 1

ng = True
pos = [[1, 1, 0]]
while len(pos) > 0:
    x, y, depth = pos.pop(0)
    if ([x, y] == [h, w]) & (maze[x][y] != '#'):
        ans = h * w - cou - depth - 1
        #print(cou)
        #print(depth)
        print(ans)
        ng = False
        break
    maze[x][y] = 'f'

    if maze[x+1][y] == '.':
        pos.append([x+1, y, depth+1])
    if maze[x][y+1] == '.':
        pos.append([x, y+1, depth+1])
    if maze[x-1][y] == '.':
        pos.append([x-1, y, depth+1])
    if maze[x][y-1] == '.':
        pos.append([x, y-1, depth+1])
    #print(pos)
    #print(maze)


if (len(pos) == 0) & ng:
    print(-1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
maze = [['#'] * (w+2)]
cou = 0
for i in range(h):
    a = ['#'] + list(input()) + ['#']
    maze.append(a)
x = ['#'] * (w+2)
maze.append(x)

for i in range(1, h+1):
    for j in range(1, w+1):
        if maze[i][j] == '#':
            cou += 1

ng = True
pos = [[1, 1, 0]]
while len(pos) > 0:
    x, y, depth = pos.pop(0)
    if ([x, y] == [h, w]) & (maze[x][y] != '#'):
        ans = h * w - cou - depth - 1
        #print(cou)
        #print(depth)
        print(ans)
        ng = False
        break
    maze[x][y] = 'f'

    if maze[x+1][y] == '.':
        pos.append([x+1, y, depth+1])
    if maze[x][y+1] == '.':
        pos.append([x, y+1, depth+1])
    #print(pos)
    #print(maze)


if (len(pos) == 0) & ng:
    print(-1)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
maze = [[9] * (w+2)]
cou = 0
for i in range(h):
    a = [9]
    l = list(input())
    for j in range(w):
        if l[j] == '.':
            a.append(0)
        else:
            a.append(9)
            cou += 1
    a.append(9)
    maze.append(a)
x = [9] * (w+2)
maze.append(x)
maze[h][w] = 1

ng = True
pos = [[1, 1, 0]]
while len(pos) > 0:
    x, y, depth = pos.pop(0)
    if maze[x][y] == 1:
        ans = h * w - cou - depth - 1
        print(ans)
        ng = False

    maze[x][y] = 2

    if maze[x+1][y] < 2:
        pos.append([x+1, y, depth+1])
    if maze[x][y+1] < 2:
        pos.append([x, y+1, depth+1])

if (len(pos) == 0) & ng:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from queue import Queue
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
s = [STR() for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
arr[0][0] = 0
que = [[0, 0]]
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while len(que):
    y, x = map(int, que.pop())
    if s[y][x] == '.':
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                tmp = arr[y][x]
                arr[y][x] = min(arr[y][x], arr[ny][nx] + 1)
                if arr[ny][nx] >= inf:
                    que.append([ny, nx])
if arr[h - 1][w - 1] >= inf:
    print(-1)
    exit()
ss = 0
for i in range(h):
    ss += s[i].count('.')
print(ss - arr[h - 1][w - 1] - 1)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from queue import Queue
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
s = [STR() for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
arr[0][0] = 0
que = [[0, 0]]
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while len(que):
    y, x = map(int, que.pop())
    if s[y][x] == '.':
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                tmp = arr[y][x]
                arr[y][x] = min(arr[y][x], arr[ny][nx] + 1)
                if arr[ny][nx] >= inf:
                    que.append([ny, nx])
ss = 0
for i in range(h):
    ss += s[i].count('.')
print(ss - arr[h - 1][w - 1] - 1)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from queue import Queue
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w = MAP()
s = [STR() for _ in range(h)]
arr = [[inf for _ in range(w)] for _ in range(h)]
arr[0][0] = 0
quey = Queue()
quex = Queue()
quey.put(1)
quey.put(0)
quex.put(0)
quex.put(1)
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while not quex.empty():
    y, x = quey.get(), quex.get()
    if s[y][x] == '.':
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                tmp = arr[y][x]
                arr[y][x] = min(arr[y][x], arr[ny][nx] + 1)
                if arr[ny][nx] >= inf:
                    quex.put(nx)
                    quey.put(ny)
ss = 0
for i in range(h):
    ss += s[i].count('.')
print(ss - arr[h - 1][w - 1] - 1)

Submission status: Wrong Answer

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

dp = [[2501] * W for _ in range(H)]
dp[0][0] = 1

q = [(0, 0)]
while q:
    nq = []
    while q:
        y, x = q.pop()
        t = dp[y][x] + 1
        if y < H - 1:
            if s[y + 1][x] == '.' and dp[y + 1][x] > t:
                dp[y + 1][x] = t
                nq.append((y + 1, x))
        if y > 0:
            if s[y - 1][x] == '.' and dp[y - 1][x] > t:
                dp[y - 1][x] = t
                nq.append((y - 1, x))
        if x < W - 1:
            if s[y][x + 1] == '.' and dp[y][x + 1] > t:
                dp[y][x + 1] = t
                nq.append((y, x + 1))
        if x > 0:
            if s[y][x - 1] == '.' and dp[y][x - 1] > t:
                dp[y][x - 1] = t
                nq.append((y, x - 1))
    q = nq

print(sum(s[y].count('.') for y in range(H)) - dp[H - 1][W - 1])

Submission status: Wrong Answer

Solution code:
#088_D
import queue
h, w = map(int, input().split())
inf = 10 ** 5
s = [input() for _ in range(h)]
d = [[inf]*w for _ in range(h)]

que = queue.Queue()
que.put((0, 0))
d[0][0] = 0
while not que.empty():
    qx, qy = que.get()
    if qx == h-1 and qy == w-1:
        break
        
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        px, py = qx+dx, qy+dy
        if 0 <= px < h and 0<= py < w:
            if s[px][py] == '#':
                continue
            elif d[px][py] != inf:
                continue
            d[px][py] = d[qx][qy] + 1
            que.put((px, py))
            
print(h * w - (d[h-1][w-1]+1) - sum(s[i].count('#') for i in range(h)))

Submission status: Wrong Answer

Solution code:
from collections import deque


h, w = map(int, input().split())
field = [list(input()) for _ in range(h)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
nokoshi = 1
que = deque([(0, 0)])
done = [[False] * w for _ in range(h)]

white_num = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == ".":
            white_num += 1

while que:
    for i in range(len(que)):
        y, x = que.popleft()

        if y == h - 1 and x == w - 1:
            print(white_num - nokoshi)
            exit()

        if y < 0 or y >= h or x < 0 or x >= w or field[y][x] == "#" or done[y][x] is True:
            continue
        done[y][x] = True

        for dy, dx in directions:
            que.append((y+dy, x+dx))

    nokoshi += 1

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

INF = float('inf')
path = [[INF] * W for _ in range(H)]
q = deque()

q.append((0, 0, 1))
path[0][0] = 1
isGoal = False
while q:
    x, y, s = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx = x + dx
        ny = y + dy
        if (nx, ny) == (H - 1, W - 1):
            path[nx][ny] = s + 1
            isGoal = True
            break
        if 0 <= nx < H and 0 <= ny < W and path[nx][ny] > s + 1:
            q.append((nx, ny, s + 1))
            path[nx][ny] = s + 1
    else:
        continue
    break

cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            cnt += 1

if isGoal:
    print(cnt - path[H - 1][W - 1])
else:
    print(-1)