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 queue import Queue

def bfs(H, W, s):
    inf = 10 ** 20
    d = [[inf for i in range(W)] for j in range(H)]
    q = Queue()

    d[0][0] = 1
    q.put([0, 0])

    dx = (0, -1, 1, 0)
    dy = (-1, 0, 0, 1)

    while not q.empty():
        p = q.get()
        x = p[0]
        y = p[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if(nx >= 0 and nx < H and ny >= 0 and ny < W):
                if(s[nx][ny] == '.' and d[x][y] + 1 < d[nx][ny]):
                    d[nx][ny] = d[x][y] + 1
                    q.put([nx, ny])

    return d[H-1][W-1]

H, W = map(int, input().split())
s = []
wnum = 0
for i in range(H):
    s.append(input())
    for j in range(W):
        if(s[i][j] == "."):
            wnum += 1
print(wnum - bfs(H, W, s))

Submission status: Wrong Answer

Solution code:
H,W=map(int,input().split())
white=0
S=[]
for _ in range(H):
    s=list(input())
    white+=s.count('.')
    S.append(s)

f=[[0 for i in range(W)] for j in range(H)]

def path(i,j):
    s=S[i][j]
    q=[]
    for k in [1,-1]:
        if 0<=i+k<H and f[i+k][j]==0 and S[i+k][j]==s:
            q.append((i+k,j))
        if 0<=j+k<W and f[i][j+k]==0 and S[i][j+k]==s:
            q.append((i,j+k))
    return q

flag=False
que = path(0,0)
f[0][0]=1

l=1
while len(que)>0:
    l+=1
    tmp=[]
    for q in que:
        tmp+=path(*q)
        f[q[0]][q[1]]=1
        if q==(H-1,W-1):
            flag=True
            break
    que=tmp

if flag:
    print(white-l)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter
from functools import reduce
from operator import add
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
queue = deque()
depth = [[-1]*W for _ in range(H)]

cnt = Counter(''.join(reduce(add, s)))


def bfs():
    # if x==W-1 and y==H-1:
    #    return d
    queue.append((0, 0))
    depth[0][0] = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue
            if depth[ny][nx] != -1:
                continue
            if nx == W-1 and ny == H-1:
                depth[ny][nx] = depth[y][x] + 1
                return depth[ny][nx]
            if s[ny][nx] == '.':
                depth[ny][nx] = depth[y][x] + 1
                queue.append((nx, ny))
    return -1

print(H*W-bfs()-cnt['#'])

Submission status: Wrong Answer

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

    stack = [(0, 0, 1)]
    min_cost = float('inf')
    while stack:
        x, y, cost = stack.pop()
        if x == h - 1 and y == w - 1:
            min_cost = min(min_cost, cost)
        else:
            for dx, dy in ((0, 1), (1, 0)):
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w and matrix[nx][ny] == '.':
                    stack.append((nx, ny, cost + 1))

    if min_cost == float('inf'):
        return -1
    else:
        white = sum(row.count('.') for row in matrix)
        return white - min_cost

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque

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

sy = 0
sx = 0

dxy = [(-1,0),(1,0),(0,-1),(0,1)]

INF = 10**9+7

DISTANCE = [[INF for i in range(W)] for j in range(H)]
DISTANCE[sy][sx] = 0

QUEUE = deque([(sy,sx)])

flg = 0

while QUEUE :
    y,x = QUEUE.popleft()
    
    for dy,dx in dxy :
        ny = y+dy
        nx = x+dx
        if (ny < 0) or (nx < 0) or (ny >= H) or (nx >= W) :
            continue
        if MAP[ny][nx] == "#" :
            continue
        if DISTANCE[ny][nx] < INF :
            continue
        
        QUEUE.append([ny,nx])
        DISTANCE[ny][nx] = min(DISTANCE[ny][nx], DISTANCE[y][x]+1)

if DISTANCE[H-1][W-1] < INF :
    flg = 1
        
if flg == 0 :
    ans = -1
else :
    path = H+W-1
    not_score = 0
    for y in range(H) :
        not_score += MAP[y].count("#")
    ans = H*W- path - not_score
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

MAP = [input() for i in range(H)]

sy = 0
sx = 0

dxy = [(-1,0),(1,0),(0,-1),(0,1)]

INF = 10**9+7

DISTANCE = [[INF for i in range(W)] for j in range(H)]

DISTANCE[sy][sx] = 0

QUEUE = deque([(sy,sx)])

flg = 0

while QUEUE :
    y,x = QUEUE.popleft()
    
    for dy,dx in dxy :
        ny = y+dy
        nx = x+dx
        if (ny < 0) or (nx < 0) or (ny >= H) or (nx >= W) :
            continue
        if MAP[ny][nx] == "#" :
            continue
        if DISTANCE[ny][nx] < INF :
            continue
        #if (ny == H-1) and (nx == W-1) :
        #    flg = 1
        #    QUEUE = []
        #    break
        QUEUE.append([ny,nx])
        DISTANCE[ny][nx] = min(DISTANCE[ny][nx], DISTANCE[y][x]+1)

if DISTANCE[H-1][W-1] < INF :
    flg = 1
        
if flg == 0 :
    ans = -1
else :
    not_score = 0
    for y in range(H) :
        not_score += MAP[y].count("#")
    ans = (H-1)*(W-1) - not_score
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

MAP = [input() for i in range(H)]

sy = 0
sx = 0

dxy = [(-1,0),(1,0),(0,-1),(0,1)]

INF = 10**9+7

DISTANCE = [[INF for i in range(W)] for j in range(H)]

DISTANCE[sy][sx] = 0

QUEUE = deque([(sy,sx)])

flg = 0

while QUEUE :
    y,x = QUEUE.popleft()
    
    for dy,dx in dxy :
        ny = y+dy
        nx = x+dx
        if (ny < 0) or (nx < 0) or (ny >= H) or (nx >= W) :
            continue
        if MAP[ny][nx] == "#" :
            continue
        if DISTANCE[ny][nx] < INF :
            continue
        if (ny == H-1) and (nx == W-1) :
            flg = 1
            QUEUE = []
            break
        QUEUE.append([ny,nx])
        DISTANCE[ny][nx] = min(DISTANCE[ny][nx], DISTANCE[y][x]+1)
        
        
if flg == 0 :
    ans = -1
else :
    not_score = 0
    for y in range(H) :
        not_score += MAP[y].count("#")
    ans = (H-1)*(W-1) - not_score
print(ans)

Submission status: Wrong Answer

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

def main():
    na = list(map(int, input().split()))
    H, W = na[0], na[1]
    mp = []
    for i in range(H):
        mp.append(input())

    w_count = 0
    for s in mp:
        w_count += s.count('.')

    dist = [-1 for i in range(H * W)]
    v = (0, 0, 1)
    dist[0] = 1
    q = []
    q.append(v)
    while 0 < len(q):
        x, y, d = v = q.pop(0)
        if 0 < x and dist[W * y + x - 1] == -1:
            dist[W * y + x - 1] = d + 1
            q.append((x - 1, y, d + 1))
        if x < W - 1 and dist[W * y + x + 1] == -1:
            dist[W * y + x + 1] = d + 1
            q.append((x + 1, y, d + 1))
        if 0 < y and dist[W * (y - 1) + x] == -1:
            dist[W * (y - 1) + x] = d + 1
            q.append((x, y - 1, d + 1))
        if y < H - 1 and dist[W * (y + 1) + x] == -1:
            dist[W * (y + 1) + x] = d + 1
            q.append((x, y + 1, d + 1))
        if dist[H * W - 1] != -1:
            break

    if dist[H * W - 1] == -1:
        print(-1)
    else:
        print(w_count - dist[H * W - 1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections

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

ss = [input() for _ in range(h)]
start = [0,0]
goal = [w-1,h-1]
wall_count = 0
for s in ss:
    wall_count += s.count("#")

min_count = h*w
dx = [1,-1,0,0]
dy = [0,0,1,-1]

stack = collections.deque([start])
visited = [[h*w for _ in range(w)] for _ in range(h)]
visited[start[0]][start[1]] = 1

while len(stack) > 0:
    pos = stack.pop()
    
    for x,y in zip(dx, dy):
        next = [pos[0]+x, pos[1]+y]
        
        if next[0]<0 or w-1<next[0] or next[1]<0 or h-1<next[1]:
            continue
        if ss[next[1]][next[0]] == "#":
            continue
        if visited[next[1]][next[0]] < visited[pos[1]][pos[0]] + 1:
            continue
        stack.append(next)
        visited[next[1]][next[0]] = visited[pos[1]][pos[0]] + 1

score = (h*w) - wall_count - visited[h-1][w-1]
print(score)

Submission status: Wrong Answer

Solution code:
import collections

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

ss = [input() for _ in range(h)]
start = [0,0]
goal = [w-1,h-1]
wall_count = 0
for s in ss:
    wall_count += s.count("#")

min_count = h*w
dx = [1,-1,0,0]
dy = [0,0,1,-1]

stack = collections.deque([start])
visited = [[h*w for _ in range(w)] for _ in range(h)]
visited[start[0]][start[1]] = 1

while len(stack) > 0:
    pos = stack.popleft()
    
    for x,y in zip(dx, dy):
        next = [pos[0]+x, pos[1]+y]
        
        if next[0]<0 or w-1<next[0] or next[1]<0 or h-1<next[1]:
            continue
        if ss[next[1]][next[0]] == "#":
            continue
        if visited[next[1]][next[0]] < visited[pos[1]][pos[0]] + 1:
            continue
        stack.appendleft(next)
        visited[next[1]][next[0]] = visited[pos[1]][pos[0]] + 1

score = (h*w) - wall_count - visited[h-1][w-1]
print(score)

Submission status: Wrong Answer

Solution code:
import collections

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

ss = [input() for _ in range(h)]
start = [0,0]
goal = [w-1,h-1]
wall_count = 0
for s in ss:
    wall_count += s.count("#")

min_count = h*w
dx = [1,-1,0,0]
dy = [0,0,1,-1]

stack = collections.deque([start])
visited = [[h*w for _ in range(w)] for _ in range(h)]
visited[start[0]][start[1]] = 1

while len(stack) > 0:
    pos = stack.popleft()
    
    for x,y in zip(dx, dy):
        next = [pos[0]+x, pos[1]+y]
        
        if next[0]<0 or w-1<next[0] or next[1]<0 or h-1<next[1]:
            continue
        if ss[next[1]][next[0]] == "#":
            continue
        if visited[next[1]][next[0]] < visited[pos[1]][pos[0]] + 1:
            continue
        stack.append(next)
        visited[next[1]][next[0]] = visited[pos[1]][pos[0]] + 1

score = (h*w) - wall_count - visited[h-1][w-1]
print(score)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]  # 迷路
D = [[-1] * W for i in range(H)]  # 最短距離
D[0][0] = 0

Black = 0  # 最初の盤面の黒の数
for g in G:
    Black += g.count('#')

# BFS
que = deque([[0, 0]])
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while que:
    nh, nw = que.pop()
    for dh, dw in direction:
        if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
            continue

        if D[nh + dh][nw + dw] > 0:
            continue

        if G[nh + dh][nw + dw] == '#':
            continue

        D[nh + dh][nw + dw] = D[nh][nw] + 1
        que.appendleft([nh + dh, nw + dw])

if D[H - 1][W - 1]:
    print(H * W - D[H - 1][W - 1] - Black - 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

dist = [[10000] * W for i in range(H)]
dist[0][0] = 0

dxy = [(0, 1), (1, 0), (0, -1), (-1, 0)]

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

while q:
    x, y = q.popleft()
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if nx < 0 or ny < 0 or nx >= W or ny >= H:
            continue
        if s[ny][nx] == "#":
            continue
        if dist[ny][nx] < 10000:
            continue
        q.append((nx, ny))
        dist[ny][nx] = dist[y][x] + 1

count = 0
for i in range(H):
    count += s[i].count(".")
print(count - dist[H - 1][W - 1] - 1)

Submission status: Wrong Answer

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

s_list = []
h, w = map(int, input().split())
for i in range(h):
    s_list.append(input())

route = [dict() for _ in range(h*w)]
all_white = 0
for i in range(h):
    for j in range(w):
        if s_list[i][j] == "#":
            continue
        else:
            all_white += 1
        if i != h-1 and s_list[i+1][j] == ".":
            route[w*i+j][w*(i+1)+j] = 1
        if j != w-1 and s_list[i][j+1] == ".":
            route[w*i+j][w*i+j+1] = 1
di = Dijkstra(route, 0, h*w-1)
r = di.execute()
count = len(r)

if count > 1:
    print(all_white-count)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

s_list = []
h, w = map(int, input().split())
for i in range(h):
    s_list.append(input())

route = [dict() for _ in range(h*w)]
all_white = 0
for i in range(h):
    for j in range(w):
        if s_list[i][j] == "#":
            continue
        else:
            all_white += 1
        if i != h-1 and s_list[i+1][j] == ".":
            route[w*i+j][w*(i+1)+j] = 1
        if j != w-1 and s_list[i][j+1] == ".":
            route[w*i+j][w*i+j+1] = 1
di = Dijkstra(route, 0, h*w-1)
r = di.execute()
count = len(r)
if count >= 1:
    print(all_white-count)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        route_count = [0 for _ in range(num_of_city)]
        route_count[self.start_point] = 1
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
                if dist[dest] == dist[src] + cost:
                    route_count[dest] += route_count[src]

        if self.goal_point is not None:
            return self._get_path(self.goal_point, prev)
        else:
            return dist, route_count

    def _get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

s_list = []
h, w = map(int, input().split())
for i in range(h):
    s_list.append(input())

route = [dict() for _ in range(h*w)]
all_white = 0
for i in range(h):
    for j in range(w):
        if s_list[i][j] == "#":
            continue
        else:
            all_white += 1
        if i != h-1 and s_list[i+1][j] == ".":
            route[w*i+j][w*(i+1)+j] = 1
        if j != w-1 and s_list[i][j+1] == ".":
            route[w*i+j][w*i+j+1] = 1
di = Dijkstra(route, 0, h*w-1)
r = di.execute()
count = len(r)
print(all_white-count)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
edges = '#' * (W + 2)
field = [edges]
BK = 0
for _ in range(H):
    row = input()
    field.append('#' + row + '#')
    BK += row.count('#')
field.append(edges)
que = deque([(1, 1, 0)])  # x, y, dist
enq, deq = que.append, que.popleft
visited = [[0] * (W + 2) for _ in [0] * (H + 2)]
visited[1][1] = 1
dxy = [(0, 1), (0, -1), (1, 0), (-1, 0)]
dist = -1
while que:
    x, y, d = deq()
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if not visited[ny][nx] and field[ny][nx] == '.':
            if (nx, ny) == (W, H):
                dist = d + 1
            else:
                enq((nx, ny, d + 1))
                visited[ny][nx] = 1
if dist == -1:
    print(-1)
else:
    print(H * W - BK - dist - 1)

Submission status: Wrong Answer

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

	D = [[0]*W for j in range(H)]

	D[0][0] = 1
	L = [(0,0)]

	for k in range(2,H*W):
		L_next = []
		for l in L:
			w = l[0]
			h = l[1]
			#上
			if (0 < h):
				if ((0 == D[h-1][w]) and ('.'==S[h-1][w])):
					D[h-1][w] = k
					L_next.append((w,h-1))
			#左
			if (0 < w):
				if ((0 == D[h][w-1]) and ('.'==S[h][w-1])):
					D[h][w-1] = k
					L_next.append((w-1,h))
			#下
			if (h < (H - 1)):
				if ((0 == D[h+1][w]) and ('.'==S[h+1][w])):
					D[h+1][w] = k
					L_next.append((w,h+1))
			#右
			if (w < (W - 1)):
				if ((0 == D[h][w+1]) and ('.'==S[h][w+1])):
					D[h][w+1] = k
					L_next.append((w+1,h))
		L = L_next
		if (0 != D[H-1][W-1]):
			break
		if (not L):	#リストが空
			return -1

	return W*H - D[H-1][W-1] - 2

print(main())

Submission status: Wrong Answer

Solution code:
from queue import Queue

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

H, W = [int(_) for _ in input().split()]
S = [[1 if s == "#" else 0 for s in list(input())] for i in range(H)]

black_num = sum([sum(S[i]) for i in range(H)])


def solve():
    visited = [[0] * W for i in range(H)]

    q = Queue()
    q.put((0, 0))

    while not q.empty():
        i, j = q.get()

        for di, dj in directions:
            i_, j_ = i + di, j + dj

            if not (0 <= i_ < H and 0 <= j_ < W):
                continue

            if S[i_][j_] != 0 or visited[i_][j_] != 0:
                continue

            visited[i_][j_] = visited[i][j] + 1
            q.put((i_, j_))

            if i_ == H - 1 and j_ == W - 1:
                print(H * W - black_num - visited[H - 1][W - 1] - 1)
                return


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

graph = [[-1 for _ in range(W)] for _ in range(H)]

que = deque()
x,y = 0,0 #初期値
que.append((x,y))
graph[x][y] = 0
while len(que) > 0:
    # x,y = que.pop()  # 深さ優先探索
    x,y = que.popleft() #幅優先探索
    step = graph[x][y]
    #左
    if y-1 >= 0 and s[x][y-1] == "." and graph[x][y-1] == -1:
        que.append((x,y-1))
        graph[x][y-1] = step + 1
    #右
    if y+1 < W and s[x][y+1] == "." and graph[x][y+1] == -1:
        que.append((x, y+1))
        graph[x][y+1] = step + 1
    #上
    if x-1 >= 0 and s[x-1][y] == "." and graph[x-1][y] == -1:
        que.append((x-1, y))
        graph[x-1][y] = step + 1
    #下
    if x+1 < H and s[x+1][y] == "." and graph[x+1][y] == -1:
        que.append((x+1, y))
        graph[x+1][y] = step + 1

#ゴールから戻って最短ルートにマークする（複数ある場合は一方だけマーク）
que = deque()
x, y = H-1, W-1     #初期値（ゴール）
que.append((x,y))
step = graph[x][y]
graph[x][y] = -2  # 最短ルートにマーク

while len(que) > 0:
    x, y = que.popleft()  # 幅優先探索
    if x == y == 0:
        break
    #左
    if y-1 >= 0 and graph[x][y-1] == step - 1:
        que.append((x, y-1))
        graph[x][y-1] = -2
        step -= 1
        continue
    #右
    if y+1 < W and graph[x][y+1] == step - 1:
        que.append((x, y+1))
        graph[x][y+1] = -2
        step -= 1
        continue
    #上
    if x-1 >= 0 and graph[x-1][y] == step - 1:
        que.append((x-1, y))
        graph[x-1][y] = -2
        step -= 1
        continue
    #下
    if x+1 < H and graph[x+1][y] == step - 1:
        que.append((x+1, y))
        graph[x+1][y] = -2
        step -= 1
        continue

ans = 0
for h in range(H):
    for w in range(W):
        if s[h][w] == "." and graph[h][w] != -2:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque;h,w=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];q=deque([[0,0]]);v[0][0]=0;c=sum(t.count('#')for t in m)
while q:
 y,x=q.popleft()
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t+1and t<h and u+1and u<w and m[t][u]=='.'and v[t][u]<0:v[t][u]=v[y][x]+1;q.append([t,u])
print((h*w-c-v[h-1][w-1]-1)*(v[h-1][w-1]>0)or-1)

Submission status: Wrong Answer

Solution code:
from collections import deque;h,w=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];q=deque([[0,0]]);v[0][0]=0;c=sum(t.count('#')for t in m)
while q:
 y,x=q.popleft()
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t+1and t<h and u+1and u<w and m[t][u]=='.'and v[t][u]<0:v[t][u]=v[y][x]+1;q.append([t,u])
print(h*w-c-v[h-1][w-1]-1)

Submission status: Wrong Answer

Solution code:
from collections import deque;h,w=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];a=b=0;q=deque([[a-1,b-1]]);v[a-1][b-1]=0;c=sum(m.count('#')for t in m)
while q:
 y,x=q.popleft()
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t+1and t<h and u+1and u<w and m[t][u]=='.'and v[t][u]<0:v[t][u]=v[y][x]+1;q.append([t,u])
print(h*w-c-v[h-1][w-1]-1)

Submission status: Wrong Answer

Solution code:
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def main():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    path = [[float("inf")] * W for _ in range(H)]
    white = sum([len(row.replace("#", "")) for row in s])
    scan = [(0, 0, 1)]  # i, j, cost
    while len(scan):
        i, j, cost = scan.pop(0)
        if cost >= path[i][j]:
            continue
        path[i][j] = cost
        for d in directions:
            nexti = i + d[0]
            nextj = j + d[1]
            if 0 <= nexti and nexti < H and \
               0 <= nextj and nextj < W and \
               s[nexti][nextj] == ".":
                scan.append((nexti, nextj, cost + 1))
    print(white - path[H-1][W-1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def main():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    path = [[float("inf")] * W for _ in range(H)]
    white = sum([len(row.replace("#", "")) for row in s])
    scan = [(0, 0, 1)]  # i, j, cost
    while len(scan):
        i, j, cost = scan.pop(0)
        if cost >= path[i][j]:
            continue
        path[i][j] = cost
        if i == H - 1 and j == W - 1:
            break
        for d in directions:
            nexti = i + d[0]
            nextj = j + d[1]
            if 0 <= nexti and nexti < H and \
               0 <= nextj and nextj < W and \
               s[nexti][nextj] == ".":
                scan.append((nexti, nextj, cost + 1))
    print(white - path[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(map(str, input())) for i in range(H)]
numWhite = -2  # [1,1], [H,W]を除く
for h in range(H):
    numWhite += S[h].count(".")


dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


def bfs():
    que = deque([])
    que.append([0, 0])
    D = []
    for h in range(H):
        D.append([float('inf') for _ in range(W)])
    D[0][0] = 0
    while len(que) > 0:
        p = que.popleft()
        if p == [H-1, W-1]:
            break
        else:
            for i in range(4):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]
                if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != '#' and D[nx][ny] == float('inf'):
                    que.append([nx, ny])
                    D[nx][ny] = D[p[0]][p[1]] + 1
    return D[H-1][W-1]


ans = numWhite - bfs() + 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
H, W = [int(_) for _ in input().split()]
S = []
count_dot = 0
for _ in range(H):
    s = input()
    count_dot += s.count('.')
    S += [list(s)]
S[0][0] = 1
for i, j in itertools.product(range(H), range(W)):
    if S[i][j] in list('.#'):
        continue
    for x, y in ([i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]):
        if x < 0 or H <= x or y < 0 or W <= y or S[x][y] == '#':
            continue
        elif S[x][y] == '.':
            S[x][y] = S[i][j] + 1
        else:
            S[x][y] = min(S[x][y], S[i][j] + 1)
if S[-1][-1] in list('.#'):
    print(-1)
else:
    print(count_dot - S[-1][-1])

Submission status: Wrong Answer

Solution code:
def bfs(sx, sy, gx, gy):
    inf = 2**31 - 1
    que = []
    d = {h: {w: inf for w in range(W)} for h in range(H)}

    que.append((sx, sy))
    d[sy][sx] = 0

    while len(que):
        p = que.pop(0)

        if p[0] == gx and p[1] == gy:
            break

        for i in range(4):
            nx, ny = p[0] + dx[i], p[1] + dy[i]

            if (0 <= nx < W) and (0 <= ny < H) and (maze[ny][nx] != '#') and (d[ny][nx] == inf):
                que.append((nx, ny))
                d[ny][nx] = d[p[1]][p[0]] + 1

    return d[gy][gx]


def wall_count(l):
    temp = []
    for s in l:
        temp.extend(s)
    return temp.count('#')


if __name__ == '__main__':
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)

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

    maze = [list(input()) for h in range(H)]
    walls = wall_count(maze)

    print(H*W - walls - bfs(0, 0, W-1, H-1) - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W=map(int,input().split())
L=[]
cnt=0
for i in range(H+2):
    if i==0 or i==H+1:
        S="#"*(W+2)
    else:
        S=input()
        S="#"+S+"#"
    L1=[]
    for j in range(W+2):
        if S[j]==".":
            cnt+=1
        L1.append(S[j])
    L.append(L1)
L[1][1]=0
D=deque()
D.append([1,1])
h=[0,1,0,-1]
w=[1,0,-1,0]
i=0
for i in range(10000):
    #print(D)
    #print(L)
    if len(D)==0:
        print(-1)
        exit()
    elif D[0][0]==H and D[0][1]==W:
        print(cnt-L[H][W]-1)
        exit()
    for k in range(3):
        if L[D[0][0]+h[k]][D[0][1]+w[k]]==".":
            if [D[0][0]+h[k],D[0][1]+w[k]] not in D:
                D.append([D[0][0]+h[k],D[0][1]+w[k]])
            L[D[0][0]+h[k]][D[0][1]+w[k]]=L[D[0][0]][D[0][1]]+1
            
        elif L[D[0][0]+h[k]][D[0][1]+w[k]]=="#":
            pass
        else:
            if L[D[0][0]+h[k]][D[0][1]+w[k]]>L[D[0][0]][D[0][1]]+1:
                L[D[0][0]+h[k]][D[0][1]+w[k]]=L[D[0][0]][D[0][1]]+1
    D.popleft()