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: Accepted

Solution code:
from collections import deque

INF = float('inf')

dr = (-1, 0, 0, 1)
dc = (0, -1, 1, 0)

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

s = []
total_white_count = 0
for _ in range(H):
    t = input()
    s.append(t)
    total_white_count += t.count('.')
p = [[INF for _ in range(W)] for _ in range(H)]

ans = -1

dq = deque()
dq.append((0, 0, 1))
while dq:
    r, c, d = dq.popleft() # 直した

    nd = d + 1
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if not (0 <= nr < H and 0 <= nc < W): continue
        if s[nr][nc] == '#' : continue
        if p[nr][nc] <= nd: continue
        p[nr][nc] = nd
        if nr == H - 1 and nc == W - 1:
            ans = total_white_count - nd
            break
        dq.append((nr, nc, nd))
    else:
        continue
    break

print(ans)

Submission status: Accepted

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

water=[[0]*w for _ in range(h)]
water[0][0]=1
a_index=[]
a_column=[]
a_index.append(0)
a_column.append(0)
b=[]
count=0

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            water[i][j]=3000
            count+=1
while water[h-1][w-1]==0:
    for i,j in zip(a_index,a_column):
        if water[i][j]==1:
            if i>0:
                if water[i-1][j]==0:
                    water[i-1][j]+=1
                    b.insert(0,[i-1,j])
            if i<h-1:
                if water[i+1][j]==0:
                    water[i+1][j]+=1
                    b.insert(0,[i+1,j])
            if j>0:
                if water[i][j-1]==0:
                    water[i][j-1]+=1
                    b.insert(0,[i,j-1])
            if j<w-1:
                if water[i][j+1]==0:
                    water[i][j+1]+=1
                    b.insert(0,[i,j+1])
        water[i][j]+=1

    a_index+=[x[0] for x in b]
    a_column+=[x[1] for x in b]

    if not b:
        print(-1)
        exit()
    b=[]

print(h*w-water[0][0]-count)

Submission status: Accepted

Solution code:
import queue


def func(R, C, c, queue):
    # ゴールできるかを判断(幅優先探索)
    sy, sx = [1, 1]
    gy, gx = [R, C]
    score = R * C
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            if c[i][j] == "#":
                score -= 1

    queue.put([sy, sx])
    visited = [[-1 for i in range(len(c[0]))] for i in range(len(c))]
    count = 0

    def search(sy, sx, queue, visited):
        if c[sy][sx] != "#" and visited[sy][sx] == -1:
            queue.put([sy, sx])
            visited[sy][sx] = 1
        return

    while 1:
        size = queue.qsize()
        if size == 0:
            return -1
        for i in range(size):
            [sy, sx] = queue.get()
            visited[sy][sx] = count
            if sy == gy and sx == gx:
                return score - count - 1
            search(sy + 1, sx, queue, visited)
            search(sy - 1, sx, queue, visited)
            search(sy, sx + 1, queue, visited)
            search(sy, sx - 1, queue, visited)
        count += 1


R, C = [int(i) for i in input().split()]
c = [["#" for i in range(C + 2)] for i in range(R + 2)]
for i in range(1, R + 1):
    c[i][1:-1] = input()
print(func(R, C, c, queue.Queue()))
"""
# print("print(func({}, {}, {}, queue.Queue()))".format(R, C, c))
print(func(3, 3, [['#', '#', '#', '#', '#'], ['#', '.', '.', '#', '#'], ['#', '#', '.', '.', '#'], ['#', '.', '.', '.', '#'], ['#', '#', '#', '#', '#']], queue.Queue()))
print(func(10, 37, [['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'], ['#', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '#'], ['#', '.', '.', '.', '#', '.', '.', '.', '#', '#', '#', '#', '.', '.', '.', '#', '#', '#', '#', '.', '.', '#', '#', '#', '.', '.', '.', '#', '#', '#', '.', '.', '.', '#', '#', '#', '.', '.', '#'], ['#', '.', '.', '#', '.', '#', '.', '.', '#', '.', '.', '.', '#', '.', '#', '#', '.', '.', '.', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#', '.', '#'], ['#', '.', '.', '#', '.', '#', '.', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#', '.', '#'], ['#', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '#', '#', '.', '#', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#', '.', '#', '.', '#', '#', '#', '.', '#', '.', '#', '#', '#', '.', '#'], ['#', '.', '#', '#', '#', '#', '#', '.', '#', '#', '#', '#', '.', '.', '#', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#', '.', '.', '#', '#', '.', '.', '.', '.', '#', '#', '.', '.', '.', '#'], ['#', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#', '.', '#'], ['#', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#', '.', '#', '#', '.', '.', '.', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#', '.', '#', '.', '.', '.', '#', '.', '#'], ['#', '.', '#', '.', '.', '.', '#', '.', '#', '#', '#', '#', '.', '.', '.', '#', '#', '#', '#', '.', '.', '#', '#', '#', '.', '.', '.', '#', '#', '#', '.', '.', '.', '#', '#', '#', '.', '.', '#'], ['#', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '#'], ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']], queue.Queue()))
"""

Submission status: Accepted

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

cnt = Counter(reduce(add, s))

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


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 True
            if s[ny][nx] == '.':
                depth[ny][nx] = depth[y][x] + 1
                queue.append((nx, ny))
    return False

if bfs():
    print(H*W-depth[H-1][W-1]-cnt['#'])
else:
    print(-1)

Submission status: Accepted

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

    stack = [(0, 0)]
    diffs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    distance = [[float('inf')] * w for _ in range(h)]
    distance[0][0] = 1
    while stack:
        x, y = stack.pop()
        for dx, dy in diffs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w \
                           and matrix[nx][ny] == '.' \
                           and distance[x][y] + 1 < distance[nx][ny]:
                distance[nx][ny] = distance[x][y] + 1
                stack.append((nx, ny))

    if distance[h - 1][w - 1] == float('inf'):
        return -1
    else:
        white = sum(row.count('.') for row in matrix)
        return white - distance[h - 1][w - 1]

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

Submission status: Accepted

Solution code:
from collections import deque

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

MAP = [input() for i in range(H)]
INF = 10000
DISTANCE = [[INF for i in range(W)] for j in range(H)]
DISTANCE[0][0] = 0
QUEUE = deque([(0,0)])
dxy = [(-1,0),(1,0),(0,-1),(0,1)]
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[-1][-1] < INF :
    path = 1 + DISTANCE[-1][-1]
    not_score = 0
    for y in range(H) :
        not_score += MAP[y].count("#")
    ans = H*W - path - not_score
else :
    ans = -1
print(ans)

Submission status: Accepted

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 = DISTANCE[H-1][W-1] + 1
    not_score = 0
    for y in range(H) :
        not_score += MAP[y].count("#")
    
    ans = H*W - path - not_score
print(ans)

Submission status: Accepted

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 and mp[y][x - 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 and mp[y][x + 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 and mp[y - 1][x] == '.':
            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 and mp[y + 1][x] == '.':
            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: Accepted

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("#")

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

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

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

if visited[w-1][h-1] == -1:
    print("-1")
else:
    score = (h*w) - wall_count - visited[w-1][h-1]
    print(score)

Submission status: Accepted

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] > 0:
    print(H * W - D[H - 1][W - 1] - Black - 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

from collections import deque

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

start, goal = (1, 1), (H, W)
# 左右上下
directions = [[0,-1],[0,1],[-1,0],[1,0]]
# 四方に一回り大きいフィールドを作る
field = [['*'] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    row = list(input())[:-1]
    for j in range(1, W+1):
        field[i][j] = row[j-1]

# 移動距離メモ
memo = [[float('inf')] * (W+2) for i in range(H+2)]
memo[start[0]][start[1]] = 0
# 訪問済メモ
visited = [[0] * (W+2) for i in range(H+2)]
# 移動元メモ
prevs = [[None] * (W+2) for i in range(H+2)]

def bfs():
    que = deque()
    # スタート位置
    que.append(start)
    while len(que) != 0:
        cur = que.popleft()
        # 見終わった場所はもうやらない
        if visited[cur[0]][cur[1]] == 1:
            continue
        # 訪問済にする
        visited[cur[0]][cur[1]] = 1
        # 4方向見る
        for direction in directions:
            # 上下左右に1つずつ動かした座標
            nxt = list(map(lambda x,y: x+y, cur, direction))
            # 壁か黒マスはスキップ
            if field[nxt[0]][nxt[1]] == '*' or field[nxt[0]][nxt[1]] == '#':
                continue
            # 現在位置+1の距離を移動先に記録
            if field[nxt[0]][nxt[1]] == '.' and memo[nxt[0]][nxt[1]] > memo[cur[0]][cur[1]] + 1:
                memo[nxt[0]][nxt[1]] = memo[cur[0]][cur[1]] + 1
                # ここで移動元のマスを記録
                prevs[nxt[0]][nxt[1]] = (cur[0], cur[1])
                # キューに次のマスを足す
                que.append(nxt)

# 最短経路を出す
bfs()
# ゴールに辿り着けない場合
if memo[goal[0]][goal[1]] == float('inf'):
    print(-1)
    exit()
# 最短経路で使うマスに目印をつける
field[goal[0]][goal[1]] = '@'
nxt = prevs[goal[0]][goal[1]]
for _ in range(memo[goal[0]][goal[1]]):
    field[nxt[0]][nxt[1]] = '@'
    nxt = prevs[nxt[0]][nxt[1]]
# 残っている白マスが塗り替えられる場所
ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        if field[i][j] == '.':
            ans += 1
print(ans)

Submission status: Accepted

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(".")
if dist[H - 1][W - 1] == 10000:
    print(-1)
else:
    print(count - dist[H - 1][W - 1] - 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Dec 30 19:55:40 2018
ABC088D
@author: maezawa
"""

h, w = list(map(int, input().split()))
a = []
for i in range(h):
    a.append(list(input()))
    
b = [[-1]*w for _ in range(h)]
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]

a[0][0]=0
ok = True
finish = False
cnt = 1
current = [0, 0]
front = [current]
nextfront = []

while True:
    for cell in front:
        for direction in dirs:
            y, x = [cell[0]+direction[0], cell[1]+direction[1]]
            if y<0 or y>=h or x<0 or x>=w:
                continue
            if a[y][x] == '.':
                a[y][x] = cnt
                nextfront.append([y, x])
            if y == h-1 and x == w-1:
                finish = True
                break
    if finish == True:
        break
    elif nextfront == []:
        #print(y, x, cnt)
        ok = False
        break
    front = nextfront[:]
    nextfront = []
    cnt += 1
cntblack = 0
for y in range(h):
    for x in range(w):
        if a[y][x] == '#':
            cntblack += 1
#print(a)
if ok:
    print(h*w-1-a[h-1][w-1]-cntblack)
else:
    print(-1)

Submission status: Accepted

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
        if i != 0 and s_list[i-1][j] == ".":
            route[w*i+j][w*(i-1)+j] = 1
        if j != 0 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: Accepted

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

A=[]
a=["#"]*(W+2)
A.append(a)
for i in range(H):
    s=input()
    s="#"+s+"#"
    A.append(list(s))
A.append(a)
#幅優先探索
#print(A)
P=[[1,1]]
A[1][1]=1
x=[1,-1,0,0]
y=[0,0,1,-1]
while P!=[]:
    #print(P)
    for j in range(4):
        if A[P[0][0]+x[j]][P[0][1]+y[j]]=="#":
            pass
        elif A[P[0][0]+x[j]][P[0][1]+y[j]]==".":
            A[P[0][0]+x[j]][P[0][1]+y[j]]=A[P[0][0]][P[0][1]]+1
            P.append([P[0][0]+x[j],P[0][1]+y[j]])
        elif A[P[0][0]+x[j]][P[0][1]+y[j]]<=A[P[0][0]][P[0][1]]+1:
            pass
        else:
            A[P[0][0]+x[j]][P[0][1]+y[j]]=A[P[0][0]][P[0][1]]+1
            P.append([P[0][0]+x[j],P[0][1]+y[j]])
    del P[0]
S=0
for i in range(H+2):
    for j in range(W+2):
        if A[i][j]=="#":
            S+=1
if A[H][W]==".":
    print(-1)
else:
    print((H+2)*(W+2)-S-A[H][W])

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
edges = [0] * (W + 2)
field = [edges]
WH = 0
for _ in range(H):
    row = [c == '.' for c in input()]
    field.append([0] + row + [0])
    WH += sum(row)
field.append(edges)
que = deque([(1, 1, 1)])  # x, y, cnt
enq, deq = que.append, que.popleft
while que:
    x, y, cnt = deq()
    if (x, y) == (W, H):
        print(WH - cnt)
        exit()
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nx, ny = x + dx, y + dy
        if field[ny][nx]:
            enq((nx, ny, cnt + 1))
            field[ny][nx] = 0
print(-1)

Submission status: Accepted

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, 1)])  # x, y, cnt
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)]
while que:
    x, y, cnt = 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):
                res = cnt + 1
                print(H * W - BK - res)
                exit()
            else:
                enq((nx, ny, cnt + 1))
                visited[ny][nx] = 1
print(-1)

Submission status: Accepted

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

	#黒の数をカウント
	sum_black = 0
	for h in range(H):
		for w in range(W):
			if ('#'==S[h][w]):
				sum_black += 1

	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] - sum_black

print(main())

Submission status: Accepted

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

    print(-1)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())
inf = 10**6
field = []
d = []
res = 0
for _ in range(h):
    line = list(input())
    field.append(line)
    d.append([inf]*w)
    for s in line:
        if s==".":
            res += 1

d[0][0] = 0
diff = [
    [1,0]
    ,[0,1]
    ,[-1,0]
    ,[0,-1]
]

flag = True
while flag:
    flag = False
    for hi in range(h):
        for wi in range(w):
            if d[hi][wi]<inf:
                for (dh,dw) in diff:
                    if h>hi+dh>=0 and w>wi+dw>=0 and field[hi+dh][wi+dw]=="." and d[hi+dh][wi+dw]>d[hi][wi]+1:
                        d[hi+dh][wi+dw] = d[hi][wi]+1
                        flag = True

if d[h-1][w-1]<inf:
    print(res-d[h-1][w-1]-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
h, w = map(int, input().split())
d = []
for i in range(h):
    d.append(input())
# [d1, d2, d3, ..., dN]
s = [str(m) for m in d]
#移動ベクトル
dd = ((0, -1), (-1, 0), (0, 1), (1, 0))
dist = []
dotcount = 0
sharpcount = 0
for j in range(h):
    for i in range(w):
        if s[j][i] == ".":
            dotcount += 1
            for dx, dy in dd:  # 下、左、上、右の四方向から生物種が流れこむ、もしくは流れ出る（濃度の違いによって決定される、濃度が高いほうから低いほうに流れる）
                nx = i + dx
                ny = j + dy
                if 0 <= nx < w and 0 <= ny < h:  # L*Lの幅に収まっているときのみ
                    if s[ny][nx] == ".":
                        dist.append([i + j * w, nx + ny * w, 1])
        else:
            sharpcount += 1

class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
# (src, dst, weight)
inputs = dist

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)

d = Dijkstra(g, h * w - 1)
sp = format(d.shortest_distance(0))
#print('最短経路: {}'.format(d.shortest_path(1)))
#print('最短距離: {}'.format(d.shortest_distance(1)))
if sp != "inf":
    needcount = int(sp) + 1
    ans = dotcount - needcount
else:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
import sys

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

cc = 0
for ss in S:
    for st in ss:
        if st == ".":
            cc += 1

for i in range(len(S)):
    S[i] = "#" + S[i] + "#"

temp = ["#" * (W + 2)]
S = temp + S + temp

dd = [[float("inf")] * W for i in range(H)]

def DFS(a, b, d):
    dd[a-1][b-1] = d
    for x, y in [(a+1, b), (a-1, b), (a, b+1), (a, b-1)]:
        if S[x][y] == "#":
            continue
        else:
            if dd[x-1][y-1] > d + 1:
                DFS(x, y, d + 1)

sys.setrecursionlimit(10000)

DFS(1,1,0)
if dd[H-1][W-1] != float("inf"):
    print(cc - dd[H-1][W-1] -1)
else:
    print("-1")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
class Pair:
    x = 0
    y = 0
    def __init__(self, x, y):
        self.x = x
        self.y = y

import queue

# input
h, w = map(int, input().split())
grid = [input() for _ in range(h)]

# calc
def bfs():
    que = queue.Queue()
    d = [[-1 for _ in range(w)] for _ in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que.put(Pair(0, 0))
    d[0][0] = 0
    
    while not que.empty():
        p = que.get()
        
        for i in range(4):
            q_x = p.x + dx[i]
            q_y = p.y + dy[i]
            if q_x == w - 1 and q_y == h - 1:
                return d[p.y][p.x] + 1
            if 0 <= q_x < w and 0 <= q_y < h and grid[q_y][q_x] == "." and d[q_y][q_x] < 0:
                que.put(Pair(q_x, q_y))
                d[q_y][q_x] = d[p.y][p.x] + 1
    
    return -1

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

result = bfs()

# output
if result == -1:
    print(-1)
else:
    print(white - 1 - result)