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:
from collections import deque

H,W=map(int,input().split())
S=[input() for i in range(H)]
black=0
for i in range(H):
    black+=S[i].count("#")

C=[[0 for _ in range(W)] for j in range(H)]
F=[[False for _ in range(W)] for j in range(H)]
def bfs():
    q=deque([[0,0]])
    F[0][0]=True
    d=[[0,1],[1,0],[-1,0],[0,-1]]
    while q:
        y,x=q.popleft()
        for a,b in d:
            ny=y+a
            nx=x+b
            if 0<=ny<H and 0<=nx<W:
                if S[ny][nx]=="." and F[ny][nx]!=True:
                    q.append([ny,nx])
                    C[ny][nx]=C[y][x]+1
                    F[ny][nx]=True
bfs()
ans=H*W-C[H-1][W-1]-1-black
print(ans)

Submission status: Wrong Answer

Solution code:
from queue import Queue
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(input()))
tx = [1,0,-1,0]
ty = [0,1,0,-1]
cnt = 0
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '#':
            cnt += 1
q = Queue()
q.put([0,0,1])
while not q.empty():
    x, y, index = q.get()
    MAP[x][y] = '#'
    if x == H - 1 and y == W - 1:
        cnt += index
        break
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and MAP[nx][ny] == '.':
            q.put([nx,ny,index+1])

ans = H * W - cnt
print(ans)

Submission status: Wrong Answer

Solution code:
from queue import Queue
H, W = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(input()))
tx = [1,0,-1,0]
ty = [0,-1,0,1]
cnt = 0
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '#':
            cnt += 1
q = Queue()
q.put([0,0,1])
while not q.empty():
    x, y, index = q.get()
    MAP[x][y] = '#'
    if x == H - 1 and y == W - 1:
        cnt += index
        break
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and MAP[nx][ny] == '.':
            q.put([nx,ny,index+1])

ans = H * W - cnt
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

H, W = map(int,input().split())
MAP = []
INF = 10 ** 8
for _ in range(H):
    MAP.append(list(input()))
tx = [1,0,-1,0]
ty = [0,-1,0,1]
def dfs(x, y, index):
    if x < 0 or H <= x or y < 0 or W <= y:
        return INF
    if MAP[x][y] == '#':
        return INF
    if x == H - 1 and y == W - 1:
        return index
    ret = INF
    if MAP[x][y] == '.':
        MAP[x][y] = index
    else:
        MAP[x][y] = min(MAP[x][y], index)
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        ret = min(ret, dfs(nx, ny, MAP[x][y]+1))
    return ret
cnt = 0
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '#':
            cnt += 1
cnt += dfs(0,0,1)
ans = H * W - cnt
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

H, W = map(int,input().split())
MAP = []
INF = 10 ** 8
for _ in range(H):
    MAP.append(list(input()))
tx = [1,0,-1,0]
ty = [0,-1,0,1]
def dfs(x, y, index):
    if x < 0 or H <= x or y < 0 or W <= y:
        return INF
    if MAP[x][y] == '#':
        return INF
    if x == H - 1 and y == W - 1:
        return index
    ret = INF
    MAP[x][y] = '#'
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        ret = min(ret, dfs(nx, ny, index+1))
    return ret
cnt = 0
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '#':
            cnt += 1
cnt += dfs(0,0,1)
ans = H * W - cnt
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

directions = [[-1,0],[1,0],[0,-1],[0,1]]

A = [[-1]*W for i in range(H)]  #(sy,sx)からの最短距離
A[0][0] = 0

q = deque([[0,0]])

while q:
    y,x = q.pop()
    for dy,dx in directions:
        if not (0<= y+dy < H and 0 <= x+dx < W):
            continue
        elif s[y+dy][x+dx] == '#':
            continue
        elif A[y+dy][x+dx] != -1:
            continue
        else:
            A[y+dy][x+dx] = A[y][x] + 1
            q.appendleft([y+dy,x+dx])

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

print(a-A[H-1][W-1]-1)

Submission status: Wrong Answer

Solution code:
import heapq

H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(list(input()))
nodes = []
nodedict = {}
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            nid = len(nodes)
            nodedict[(i,j)] = nid
            nodes.append((i,j))

N = len(nodes)
INF = H*W
edges = [[False]*N for _ in range(N)]

def link(i1,j1,i2,j2):
    n1 = nodedict[(i1,j1)]
    n2 = nodedict[i2,j2]
    edges[n1][n2] = edges[n2][n1] = True

for i in range(H):
    for j in range(W):
        if maze[i][j] != '.': continue
        if i > 0 and maze[i-1][j]=='.': link(i,j,i-1,j)
        if i < H-1 and maze[i+1][j]=='.': link(i,j,i+1,j)
        if j > 0 and maze[i][j-1]=='.': link(i,j,i,j-1)
        if j < W-1 and maze[i][j+1]=='.': link(i,j,i,j+1)

dist = [INF] * len(nodes)

def path():
    dist[0] = 0
    n0 = nodedict[(0, 0)]
    pq = [(0, n0)]
    determined = {n0}
    while pq:
        d, nid = heapq.heappop(pq)
        for i, linked in enumerate(edges[nid]):
            if linked and i not in determined:
                dist[i] = min(dist[i], d+1)
                determined.add(i)
                heapq.heappush(pq, (d+1, i))
    goal = nodedict[(H-1, W-1)]
    return dist[goal] + 1



print(len(nodes) - path())

Submission status: Wrong Answer

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

if sij[0][0] == '#' or sij[h-1][w-1] == '#':
    print(-1)
    exit()

q = queue.Queue()

q.put([0,0])

vx = [0,1,0,-1]
vy = [1,0,-1,0]

check = [0]*(h*w)
check[0] = 1

while not q.empty():
    x,y = q.get()
    for i in range(4):
        nx = x+vx[i]
        ny = y+vy[i]
        if nx >= 0 and nx <= w-1 and ny >= 0 and ny <= h-1:
            if check[ny*w+nx] == 0 and sij[ny][nx] == '.':
                q.put([nx,ny])
                check[ny*w+nx] = check[y*w+x] + 1
                if ny == h-1 and nx == w-1:
                    check[ny*w+nx] = check[y*w+x] + 1
                    break
kuro = 0

for i in range(h):
    for j in range(w):
        if sij[i][j] == '#':
            kuro += 1
if check[-1] == 0:
    print(-1)
    exit()
print(h*w-kuro-check[-1],check)

Submission status: Wrong Answer

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

if sij[0][0] == '#' or sij[h-1][w-1] == '#':
    print(-1)
    exit()

q = queue.Queue()

q.put([0,0])

vx = [0,1,0,-1]
vy = [1,0,-1,0]

check = [0]*(h*w)
check[0] = 1

while not q.empty():
    x,y = q.get()
    for i in range(4):
        nx = x+vx[i]
        ny = y+vy[i]
        if nx >= 0 and nx <= w-1 and ny >= 0 and ny <= h-1:
            if check[ny*w+nx] == 0:
                q.put([nx,ny])
                check[ny*w+nx] = check[y*w+x] + 1
            if ny == h-1 and nx == w-1:
                check[ny*w+nx] = check[y*w+x] + 1
                break
kuro = 0

for i in range(h):
    for j in range(w):
        if sij[i][j] == '#':
            kuro += 1
            
print(h*w-kuro-check[-1])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
map_a = [[] for _ in range(h)]
for i in range(h):
    for c in input():
            map_a[i].append(0 if c == "#" else 1)
d = [(1,0),(0,1),(-1,0),(0,-1)]

area = 0
stack = [(0,0)]

while stack:
    x,y = stack.pop()
    for u,v in d:
        m = x + u; n = y + v
        if 0<=m<h and 0<=n<w:
            if map_a[m][n]==1:
                map_a[m][n] = map_a[x][y]+1
                stack.append((m,n))
                area += 1
if map_a[-1][-1] == 1:
    print(-1);exit()

pound = 0
for i in range(h):
    for c in map_a[i]:
        if c == 1:
            pound += 1
print(area-map_a[-1][-1]+pound)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
map_a = [[] for _ in range(h)]
for i in range(h):
    for c in input():
            map_a[i].append(0 if c == "#" else 1)
d = [(1,0),(0,1),(-1,0),(0,-1)]

area = 0
stack = [(0,0)]
while stack:
    x,y = stack.pop()
    for u,v in d:
        m = x + u; n = y + v
        if 0<=m<h and 0<=n<w:
            if map_a[m][n]==1:
                map_a[m][n] = map_a[x][y]+1
                stack.append((m,n))
                area += 1

pound = 0
for i in range(h):
    for c in map_a[i]:
        if c == 1:
            pound += 1
print(area-map_a[-1][-1]+pound)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
areas = []
blacks = 0
for _ in range(H):
    texts = list(input().rstrip())
    for char in texts:
        if char == '#':
            blacks += 1
    areas.append(texts)

# start は 0,0
# goal はH-1,W-1
# .を#に変更できる
# たくさん変更すればするほどポイントは高い
# 全部のマス - 元から#だった数 - 最短距離

inf = float('inf')


def bfs(start_point, goal_point):
    scores = [[inf for _ in range(W)] for _ in range(H)]
    queue = deque([start_point])
    scores[0][0] = 0
    move_positions = [[-1, 0], [0, -1], [1, 0], [0, 1]]
    while queue:
        now_point = queue.popleft()
        for move_position in move_positions:
            next_point = [now_point[0] + move_position[0],
                          now_point[1] + move_position[1]]
            if 0 <= next_point[0] < H and 0 <= next_point[1] < W:
                if areas[next_point[0]][next_point[1]] == '.':
                    if scores[next_point[0]][next_point[1]] > scores[now_point[0]][now_point[1]] + 1:
                        scores[next_point[0]][next_point[1]
                                              ] = scores[now_point[0]][now_point[1]] + 1
                        queue.append(next_point)
    return scores[H - 1][W - 1]


cost = bfs([0, 0], [H - 1, W - 1]) + 1

print(H * W - blacks - cost)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
from collections import deque

def resolve():
    H, W = map(int, input().split())
    s = []
    white_num = 0
    for i in range(H):
        s.append(input())
        white_num += s[i].count('.')

    dir = ((0, 1), (1, 0), (0, -1), (-1, 0))
    dist = [[-1]*W for _ in range(H)]
    que = deque()
    que.append((0, 0))
    dist[0][0] = 0

    while len(que)>0:
        now_y, now_x = que.popleft()
        if now_y==H-1 and now_x==W-1:
            break
        for dy, dx in dir:
            next_y = now_y+dy
            next_x = now_x+dx
            if 0<=next_y<H and 0<=next_x<W and s[next_y][next_x]=='.' and dist[next_y][next_x]==-1:
                que.append((next_y, next_x))
                dist[next_y][next_x] = dist[now_y][now_x] + 1

    min_step = dist[H-1][W-1]+1
    if min_step==-1:
        print(-1)
    else:
        print(white_num-min_step)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
from collections import deque

def resolve():
    H, W = map(int, input().split())
    s = []
    white_num = 0
    for i in range(H):
        s.append(input())
        white_num += s[i].count('.')

    dir = ((0, 1), (1, 0), (0, -1), (-1, 0))
    dist = [[-1]*W for _ in range(H)]
    que = deque()
    que.append((0, 0))
    dist[0][0] = 0

    while len(que)>0:
        now_y, now_x = que.popleft()
        if now_y==H-1 and now_x==W-1:
            break
        for dy, dx in dir:
            next_y = now_y+dy
            next_x = now_x+dx
            if 0<=next_y<H and 0<=next_x<W and s[next_y][next_x]=='.' and dist[next_y][next_x]==-1:
                que.append((next_y, next_x))
                dist[next_y][next_x] = dist[now_y][now_x] + 1


    print(white_num-(dist[H-1][W-1]+1))

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
from collections import deque, Counter

def main():

    h, w = MII()
    h += 2; w += 2
    grid = '#' * w
    for _ in range(h-2):
        grid += '#' + IS() + '#'
    grid += '#' * w

    if grid[1+w] == '#' or grid[(h-1)*w-2] == '#': print(-1); exit(0)

    c = Counter(grid)
    dot = c['.']

    def bfs(start, goal):
        INF = 10**9
        dist = [INF] * (h*w)
        dist[start] = 1
        q = deque([start])
        while q:
            v = q.popleft()
            if v == goal: return dist[v]
            dv = dist[v]
            for mv in (-1,1,w,-w):
                x = v + mv
                if grid[x] == '#': continue
                dw = dv + 1
                if dw >= dist[x]: continue
                dist[x] = dw
                q.append(x)
        return -1
    res = bfs(1+w, (h-1)*w-2)
    print(dot-res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
from collections import deque, Counter

def main():

    h, w = MII()
    h += 2; w += 2
    grid = '#' * w
    for _ in range(h-2):
        grid += '#' + IS() + '#'
    grid += '#' * w

    c = Counter(grid)
    dot = c['.']

    def bfs(start, goal):
        INF = 10**9
        dist = [INF] * (h*w)
        dist[start] = 1
        q = deque([start])
        while q:
            v = q.popleft()
            if v == goal: return dist[v]
            dv = dist[v]
            for mv in (-1,1,w,-w):
                x = v + mv
                if grid[x] == '#': continue
                dw = dv + 1
                if dw >= dist[x]: continue
                dist[x] = dw
                q.append(x)
        return -1
    res = bfs(1+w, (h-1)*w-2)
    print(dot-res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

shortest_path = [[float('inf')] * (w+1) for _ in range(h+1)]

shortest_path[1][1] = 1
q = deque([(1,1)])

while q:
    x,y = q.popleft()
    cost = shortest_path[y][x]
    for j,i in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
        if s[i][j] == "#":
            continue
        else:
            if shortest_path[i][j] > cost+1:
                q.append((j,i))
                shortest_path[i][j] = cost+1

print(sum( st.count(".") for st in s) - shortest_path[h][w])

Submission status: Wrong Answer

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc088/tasks/abc088_d
# 19:01-20:04 chudan
# 20:17-20:26 done


def main():
    H, W = map(int, input().split())

    INF = 10**10
    n_white = 0
    s = [[-1] * (W+2) for _ in range(H+2)]
    for i in range(H):
        for j, x in enumerate(input()):
            # white => 1, black => -1
            s[i+1][j+1] = INF if x == "." else -1
            n_white += 1 if x == "." else 0
    s[1][1] = 0

    fixed = set([])
    while True:
        # 最短から貪欲に伸ばして行く
        x, y = H, W  # init
        for i in range(1, H+1):
            for j in range(1, W+1):
                if s[i][j] != -1 and s[i][j] <= s[x][y] and "{}_{}".format(i, j) not in fixed:
                    x, y = i, j
                    
        fixed.add("{}_{}".format(x, y))
        
        if x == H and y == W:
            shortest = s[x][y]
            break

        if s[x][y-1] != -1:
            s[x][y-1] = min(s[x][y]+1, s[x][y-1])
            # fixed.add("{}_{}".format(x, y-1))
        if s[x][y+1] != -1:
            s[x][y+1] = min(s[x][y]+1, s[x][y+1])
            # fixed.add("{}_{}".format(x, y+1))
        if s[x-1][y] != -1:
            s[x-1][y] = min(s[x][y]+1, s[x-1][y])
            # fixed.add("{}_{}".format(x-1, y))
        if s[x+1][y] != -1:
            s[x+1][y] = min(s[x][y]+1, s[x+1][y])
            # fixed.add("{}_{}".format(x+1, y))
    
    return n_white - (shortest + 1)


print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque
import itertools

h,w=map(int, input().split())
d=[list(input()) for i in range(h)]
inf=10**7

def bfs():
    for i, j in itertools.product([i for i in range(h)], [j for j in range(w)]):
        if d[i][j]=='.':
            d[i][j]=inf
    que=deque([[0,0]])
    d[0][0]=0

    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            ny,nx=y+i,x+j
            if nx>=0 and nx<w and ny>=0 and ny<h:
                dist=d[ny][nx]
                if dist!='#':
                    if dist>d[y][x]+1:
                        d[ny][nx]=d[y][x]+1
                        que.append([ny,nx])

bfs()
ans=h*w-d[h-1][w-1]-1
for i, j in itertools.product([i for i in range(h)], [j for j in range(w)]):
    if d[i][j]=='#': 
        ans-=1
if ans>0:
    print(ans)
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
from collections import deque
import itertools

h,w=map(int, input().split())
d=[list(input()) for i in range(h)]
inf=10**7

def bfs():
    for i, j in itertools.product([i for i in range(h)], [j for j in range(w)]):
        if d[i][j]=='.':
            d[i][j]=inf
    que=deque([[0,0]])
    d[0][0]=0

    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            ny,nx=y+i,x+j
            if nx>=0 and nx<w and ny>=0 and ny<h:
                dist=d[ny][nx]
                if dist!='#':
                    if dist>d[y][x]+1:
                        d[ny][nx]=d[y][x]+1
                        que.append([ny,nx])

bfs()
ans=h*w-d[h-1][w-1]-1
for i, j in itertools.product([i for i in range(h)], [j for j in range(w)]):
    if d[i][j]=='#': 
        ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w = map(int,input().split())
s = []
s.append(["#"]*(w+2))
for i in range(h):
    s.append(["#"]+list(input())+["#"])
s.append(["#"]*(w+2))
dx = [1,0,-1,0]
dy = [0,-1,0,1]
q = deque([(1,1)])
dis = [[-1]*(w+2) for _ in range(h+2)]
dis[1][1] = 0
while q:
    x,y = q.popleft()
    for i in range(4):
        if s[x+dx[i]][y+dy[i]] == "." and dis[x+dx[i]][y+dy[i]] == -1:
                dis[x+dx[i]][y+dy[i]] = dis[x][y] +1
                q.append((x+dx[i],y+dy[i]))
count = 0
for i in range(h+2):
    for j in range(w+2):
        if s[i][j] == ".":
            count += 1
print(count-dis[h][w]-1)

Submission status: Wrong Answer

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

from collections import deque
try:
    from typing import Deque
except ImportError:
    pass


def main():
    H, W = [int(x) for x in input().split()]
    s = [input() for _ in range(H)]
    q = deque()
    dist = {
        (0, 0): 1,
    }
    q.append((0, 0))
    while q:
        sy, sx = q.popleft()
        for dy, dx in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            ty = sy + dy
            tx = sx + dx
            if not (0 <= ty < H and 0 <= tx < W):
                continue
            if (ty, tx) in dist:
                continue
            dist[ty, tx] = dist[sy, sx] + 1
            q.append((ty, tx))
    if (H - 1, W - 1) not in dist:
        print(-1)
        return
    print(sum(si.count(".") for si in s) - dist[H - 1, W - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
s=[list('X'+input()+'X') for i in range(H)]
s.append('X'*(W+2))
s.insert(0,'X'*(W+2))

wnum=0
for i in range(1,H+1):
    for j in range(1,W+1):
        if s[i][j]=='.':
            wnum+=1

sd=[[-1 for i in range(W+2)] for j in range(H+2)]
d=[[0,1],[0,-1],[1,0],[-1,0]]
que=deque([[1,1]])
sd[1][1]=1
while len(que)>0:
    p=que.popleft()
    if p==[H,W]:
        break
    for v in d:
        ny=p[0]+v[0]
        nx=p[1]+v[1]
        if s[ny][nx]=='.' and sd[ny][nx]==-1:
            sd[ny][nx]=sd[p[0]][p[1]]+1
            que.append([ny,nx])

if sd[H][W]==-1:
    exit()

print(wnum-sd[H][W])

Submission status: Wrong Answer

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

gh = h-1
gw = w-1
def bfs():
  que = deque([])
  ch = 0
  cw = 0
  d[ch][cw] = 0

  dh = [1,0,-1,0]
  dw = [0,1,0,-1]
  
  que.append([ch,cw])
  while que:
    p = que.popleft()
    if p[0] == gh and p[1] == gw:
      return
    for i in range(4):
      nh = p[0] + dh[i]
      nw = p[1] + dw[i]
      
      if nh >= 0 and nh < h and nw >=0 and nw < w and \
          d[nh][nw] == float('inf') and s[nh][nw] != '#':
        d[nh][nw] = d[p[0]][p[1]] + 1
        que.append([nh, nw])

d = [[float('inf') for _ in range(w)] for _ in range(h)]
bfs()
white = 0
root = d[gh][gw]

for i in range(h):
  for j in range(w):
    if s[i][j] == '.':
      white += 1
print(white-root-1)

Submission status: Wrong Answer

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

gh = h-1
gw = w-1
def bfs():
  que = deque([])
  ch = 0
  cw = 0
  d[ch][cw] = 0

  dh = [1,0,-1,0]
  dw = [0,1,0,-1]
  
  que.append([ch,cw])
  while que:
    p = que.popleft()
    for i in range(4):
      nh = p[0] + dh[i]
      nw = p[1] + dw[i]
      
      if nh >= 0 and nh < h and nw >=0 and nw < w and \
          d[nh][nw] == float('inf') and s[nh][nw] != '#':
        d[nh][nw] = d[p[0]][p[1]] + 1
        if nh == gh and nw == gw:
          return
        que.append([nh, nw])

d = [[float('inf') for _ in range(w)] for _ in range(h)]
bfs()
white = 0
root = d[gh][gw]

for i in range(h):
  for j in range(w):
    if s[i][j] == '.':
      white += 1
print(white-root-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
s = [None] * H
count = 0

for i in range(H):
  s[i] = input()
  count += s[i].count('#')

# 隣接リストを作る
adj = [[] for _ in range(W*H)]
  
dx = [-1,1,0,0]
dy = [0,0,-1,1]
  
for i in range(H):
  for j in range(W):
    if s[i][j] == '.':
      for k in range(4):
        y = i + dy[k]
        x = j + dx[k]
        if 0<=x<W and 0<=y<H:
          if s[y][x] == '.':
            adj[W*i+j].append(W*y+x)
# print(adj)
  
queue = deque([0])
visit = [-1] * (W*H)
visit[0] = 1
  
while queue:
  now = queue.popleft()
  for u in adj[now]:
    if visit[u] < 0:
      queue.append(u)
      visit[u] = visit[now] + 1

# print(visit,count)
print(W*H - visit[W*H-1] - count)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = ["#"*(w+2)]
white_cnt = 0
for _ in range(h):
    row = input()
    white_cnt += row.count('.')
    maze.append("#"+row+"#")
else:
    maze.append("#"*(w+2))

w += 2
h += 2
INF = 10**9
dist = [[INF]*w for _ in range(h)]
dist[1][1] = 0
next_block = deque([(1, 1)])
dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
cnt = 0
while next_block:
    i, j = next_block.popleft()
    for x, y in dirc:
        if maze[i+x][j+y] == '#':
            continue
        if dist[i+x][j+y] == INF:
            next_block.append((i+x, j+y))
        dist[i+x][j+y] = min(dist[i+x][j+y],
                             min(dist[i+x+v][j+y+w] for v, w in dirc)+1)

print(white_cnt-dist[-2][-2]-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = ["#"*(w+2)]
white_cnt = 0
for _ in range(h):
    row = input()
    white_cnt += row.count('.')
    maze.append("#"+row+"#")
else:
    maze.append("#"*(w+2))

w += 2
h += 2
INF = 10**9
dist = [[INF]*w for _ in range(h)]
dist[1][1] = 0
next_block = deque([(1, 1)])
dirc = [(-1, 0), (0, 1), (1, 0), (0, -1)]
cnt = 0
while next_block:
    i, j = next_block.popleft()
    for x, y in dirc:
        if maze[i+x][j+y] == '#':
            continue
        if dist[i+x][j+y] != INF:
            continue
        next_block.append((i+x, j+y))
        dist[i+x][j+y] = min(dist[i+x+v][j+y+w] for v, w in dirc)+1

print(white_cnt-dist[-2][-2]-1)

Submission status: Wrong Answer

Solution code:
import math
import copy
import sys
import fractions
# import numpy as np
# import statistics
import decimal
import heapq
import collections
import itertools
import bisect

# from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

h, w = map(int, input().split())

table = [[1 for _ in range(w)] for _ in range(h)]
d_table = [[-1 for _ in range(w)] for _ in range(h)]

for i in range(h):
    s = input()
    tmp = list(s)
    for j, ts in enumerate(tmp):
        if ts == ".":
            table[i][j] = 0

ans = -1
search_table = [[-1, 0], [1, 0], [0, -1], [0, 1]]

q = collections.deque([])
q.append([0,0])
table[0][0]=1
d_table[0][0]=0

gy, gx = [h-1, w-1]

while len(q) > 0:
    qy, qx = q.popleft()

    for y, x in search_table:
        cy = qy + y
        cx = qx + x

        if cy < 0 or cy > h - 1 or cx < 0 or cx > w - 1:
            continue

        if table[cy][cx] == 0 and d_table[cy][cx] == -1:
            table[cy][cx] = 1
            d_table[cy][cx] = d_table[qy][qx] + 1
            q.append([cy, cx])

            if cy == gy and cx == gx:
                ans = d_table[cy][cx]

if ans == -1:
    print(-1)
    exit(0)

cnt = [-1 for _ in range(h*w+1)]

for i in range(h):
    for j in range(w):
        tmp = d_table[i][j]
        if tmp > -1:
            cnt[tmp]+=1

res = 0
for c in cnt:
    res += max(0, c)
print(res)

Submission status: Wrong Answer

Solution code:
import queue
from itertools import product

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

ans=-1

def bfs():
    start=[0,0]
    goal=[W-1,H-1]
    distance=[[-1]*H for j in range(W)]
    li_x=[1,-1,0,0]
    li_y=[0,0,1,-1]
    q = queue.Queue()
    q.put(start)
    distance[start[0]][start[1]]=1

    while not q.empty():
        hoge=q.get()
        x=hoge[0]
        y=hoge[1]
        dis=distance[x][y]

        for i in range(4):
            x1=x+li_x[i]
            y1=y+li_y[i]
            if (0 <=x1 < W and 0 <= y1 < H):
                if distance[x1][y1] == -1:
                    if S[y1][x1]=='.':
                        q.put([x1,y1])
                        distance[x1][y1]=dis+1
    m=''
    for i in range(H):
        m+=S[i]
    
    ans=m.count('.')-distance[W-1][H-1]
    return ans

ans=bfs()
print(ans)

Submission status: Wrong Answer

Solution code:
import queue
from itertools import product

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

ans=-1

def bfs():
    start=[0,0]
    goal=[W-1,H-1]
    distance=[[-1]*H for j in range(W)]
    li_x=[1,-1,0,0]
    li_y=[0,0,1,-1]
    q = queue.Queue()
    q.put(start)
    distance[start[0]][start[1]]=1

    while not q.empty():
        hoge=q.get()
        x=hoge[0]
        y=hoge[1]
        dis=distance[x][y]

        for i in range(4):
            x1=x+li_x[i]
            y1=y+li_y[i]
            if (0 <=x1 < W and 0 <= y1 < H):
                if distance[x1][y1] == -1:
                    if S[y1][x1]=='.':
                        q.put([x1,y1])
                        distance[x1][y1]=dis+1
    m=[]
    for i in range(H):
        m.extend(S[i])
    
    ans=m.count('.')-distance[W-1][H-1]
    return ans

ans=bfs()
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(si, sj, gi, gj):
    q = deque()
    q.append([si, sj, 0])
    used = [[False for _ in range(W)] for _ in range(H)]
    used[si][sj] = True

    while len(q) > 0:
        prvi, prvj, cost = q.popleft()
        for i, j in [[prvi - 1, prvj], [prvi + 1, prvj], [prvi, prvj - 1], [prvi, prvj + 1]]:
            if i == gi and j == gj:
                return cost + 1

            if i < 0 or j < 0 or i >= H or j >= W:
                continue

            if used[i][j] or C[i][j] == '#':
                continue

            q.append([i, j, cost + 1])
            used[i][j] = True
    return 0


if __name__ == '__main__':
    H, W = map(int, input().split())
    C = [input() for _ in range(H)]
    min_cost = bfs(0, 0, H - 1, W - 1)
    black_num = sum([row.count('#') for row in C])
    print(H * W - black_num - min_cost - 1)