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: Runtime Error

Solution code:
from collections import deque

gx, gy = w-1, h-1

q = deque()
q.appendleft([0,0])
INF = 10**5

dist = [[INF]*w for _ in range(h)]
dist[0][0] = 0

while q:
  x,y = q.pop()
  
  for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
    nx = x+dx
    ny = y+dy
    
    if 0<=nx<w and 0<=ny<h:
      if dist[ny][nx]==INF and maze[ny][nx] != '#':
        dist[ny][nx] = dist[y][x]+1
        q.appendleft([nx,ny])      

black_num = sum([maze[i].count('#') for i in range(h)])
print( h*w - dist[gy][gx] - black_num -1 )

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
maze = [input() for _ in range(H)]
p_flg = [[0]*W for _ in range(H)]
dyx = [(-1,0),(1,0),(0,-1),(0,1)]

def bfn(y,x,cnt):
    stack = [(y,x,cnt)]
    p_flg[y][x] = cnt
    while stack:
        sy, sx, cnt= stack.pop(0)
        cnt += 1
        for dy, dx in dyx:
            ny, nx = sy+dy, sx+dx
            if ny == H-1 and nx == W-1:
                return cnt
            elif 0<=ny<H and 0<=nx<W:
                if maze[ny][nx] !="#" and not p_flg[ny][nx]:
                    p_flg[ny][nx] = cnt
                    stack.append((ny,nx,cnt))

def main():
    n_obs = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                n_obs += 1
    n_path = bfn(0,0,1) -1
    ans = H*W - n_obs - n_path -1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
maze = [input() for _ in range(H)]
p_flg = [[0]*W for _ in range(H)]
dyx = [(-1,0),(1,0),(0,-1),(0,1)]

def bfn(y,x,cnt):
    stack = [(y,x,cnt)]
    p_flg[y][x] = cnt
    while stack:
        sy, sx, cnt= stack.pop(0)
        cnt += 1
        for dy, dx in dyx:
            ny, nx = sy+dy, sx+dx
            if ny == H-1 and nx == W-1:
                return cnt
            if 0<=ny<H and 0<=nx<W:
                if maze[ny][nx] !="#" and not p_flg[ny][nx]:
                    p_flg[ny][nx] = cnt
                    stack.append((ny,nx,cnt))

def main():
    n_obs = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                n_obs += 1
    n_path = bfn(0,0,1) -1
    ans = H*W - n_obs - n_path -1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import array
import itertools
from collections import defaultdict, deque


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def solve():
    def find_path(p0, p1):
        queue = deque()
        footsteps = dict()

        queue.append((p0, 0))

        while queue:
            p, s = queue.popleft()
            footsteps[p] = s

            if p == p1:
                return s

            for pp in [(p[0] + 1, p[1]), (p[0] - 1, p[1]), (p[0], p[1] + 1), (p[0], p[1] - 1)]:
                if 0 <= pp[0] < width and 0 <= pp[1] < height and field[pp[1]][pp[0]] == '.' and pp not in footsteps:
                    queue.append((pp, s + 1))
                    footsteps[pp] = -1  # placeholder

    height, width = tuple(input_ints())
    field = [input() for _ in range(height)]

    s = find_path((0, 0), (width - 1, height - 1))

    return "".join(field).count(".") - (s + 1)


def main():
    print(solve())


main()

Submission status: Runtime Error

Solution code:
H, W = [int(_) for _ in input().split()]
s = ["" for _ in range(H)]
for i in range(H):
    s[i] = input()
A = [[0, 0]]
d = [[] for _ in range(H)]
for i in range(0, H):
    for j in range(0, W):
        d[i].append(float('inf'))
d[0][0] = 0
while [H-1,W-1] not in A:


    res = float('inf')
    t_i = 0
    t_j = 0
    for i in range(len(A)):
        if d[A[i][0]][A[i][1]] < res:
            res = d[A[i][0]][A[i][1]]
            t_i = A[i][0]
            t_j = A[i][1]
    

    A.remove([t_i,t_j])

    if t_i - 1 >= 0 and s[t_i-1][t_j] == '.':
        if d[t_i-1][t_j] == float('inf'):
            A.append([t_i-1,t_j])
            d[t_i-1][t_j] = res + 1
        elif d[t_i-1][t_j] > res + 1:
            d[t_i-1][t_j] = res + 1



    if t_i + 1 <= H-1 and s[t_i+1][t_j] == '.':
        if d[t_i+1][t_j] == float('inf'):
            A.append([t_i+1,t_j])
            d[t_i+1][t_j] = res + 1
        elif d[t_i+1][t_j] > res + 1:
            d[t_i+1][t_j] = res + 1

   

    if t_j - 1 >= 0 and s[t_i][t_j-1] == '.':
        if d[t_i][t_j-1] == float('inf'):
            A.append([t_i,t_j-1])
            d[t_i][t_j-1] = res + 1
        elif d[t_i][t_j-1] > res + 1:
            d[t_i][t_j-1] = res + 1



    if t_j + 1 <= W-1 and s[t_i][t_j+1] == '.':
        if d[t_i][t_j+1] == float('inf'):
            A.append([t_i,t_j+1])
            d[t_i][t_j+1] = res + 1
        elif d[t_i][t_j+1] > res + 1:
            d[t_i][t_j+1] = res + 1

ans = d[H-1][W-1]

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

print(c-ans-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= y+j <= gy and 0 <= x+k <= gx:
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])

def main():
    h, w = map(int, input().split())
    S = []
    for i in range(h):
        S.append(input())
    
    visited = [[-1]*w for j in range(h)]
    res = bfs(S, visited, 0, 0, h-1, w-1)
    if res == -1:
        print(res)
    else:
        counter = 0
        for i in range(h):
            for j in range(w):
                if S[i][j] == '#':
                    counter += 1
        print(h*w-res-1-counter)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from queue import Queue
h,w=map(int,input().split())
S=[list(input()) for _ in range(h)]

memo=[[-1]*w for _ in range(h)]
def bfs(q):
  x,y,cnt=q.get()
  if x<0 or x>=w or y<0 or y>=h:
    return
  elif S[y][x]=='#':
    return
  elif memo[y][x]<0:
    memo[y][x]=cnt
    q.put([x-1,y,cnt+1])
    q.put([x+1,y,cnt+1])
    q.put([x,y-1,cnt+1])
    q.put([x,y+1,cnt+1])

q=Queue()
q.put([0,0,0])
while not q.empty():
  bfs(q)
if memo[y-1][x-1]==-1:
  print(-1)
  exit()
cnt=0
for i in range(h):
  cnt+=S[i].count('.')
print(cnt-memo[h-1][w-1]-1)

Submission status: Runtime Error

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

from collections import deque
q = deque([(0, 0)])
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
l[0][0] = 0

while q:
    y, x = q.popleft()
    for dy, dx in d:
        if 0 <= y+dy < H and 0 <= x+dx < W and l[y+dy][x+dx] == '.':
            l[y+dy][x+dx] = l[y][x] + 1
            q.append((y+dy, x+dx))

g = l[H-1][W-1]
total = 0
for _l in l:
    for i in _l:
        if i != '#':
            total += 1
print(total - g - 1)

Submission status: Runtime Error

Solution code:
from collections import deque
def DFS(graph,start,end):
    #  深さ優先探索ではスタックを用いたが幅優先探索ではキューを用いる
    c,r = len(graph[0]),len(graph)
    que = deque([])
    que.append(start)
    visited = [[0 for _ in range(c)] for _ in range(r)]

    while visited[end[0]][end[1]]==0:
        now = que.popleft()
        y,x = now
        up,down,left,right = [y-1,x],[y+1,x],[y,x-1],[y,x+1]

        #up
        if visited[up[0]][up[1]]==0:
            if graph[up[0]][up[1]]==".":
                que.append(up)
                visited[up[0]][up[1]]= visited[y][x]+1
            
        #down
        if visited[down[0]][down[1]]==0:
            if graph[down[0]][down[1]]==".":
                que.append(down)
                visited[down[0]][down[1]]= visited[y][x]+1
        #left
        if visited[left[0]][left[1]]==0:
            if graph[left[0]][left[1]]==".":
                que.append(left)
                visited[left[0]][left[1]]= visited[y][x]+1
        #right
        if visited[right[0]][right[1]]==0:
            if graph[right[0]][right[1]]==".":
                que.append(right)
                visited[right[0]][right[1]]= visited[y][x]+1
    
    return visited[end[0]][end[1]]

def main():
    h,w = map(int,input().split())
    ls = [list(input()) for _ in range(h)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if ls[i][j]=="#":
                cnt += 1

    dummy = ["#" for _ in range(w+2)]
    for i in range(h):
        ls[i].append("#")
        ls[i].insert(0,"#")
    ls.insert(0,dummy)
    ls.append(dummy)

    step = DFS(ls,[1,1],[h,w])+1

    if step == 1:
        print(-1)
    else:
        print(h*w-step-cnt)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
def DFS(graph,start,end):
    #  深さ優先探索ではスタックを用いたが幅優先探索ではキューを用いる
    c,r = len(graph[0]),len(graph)
    que = deque([])
    que.append(start)
    visited = [[0 for _ in range(c)] for _ in range(r)]

    while visited[end[0]][end[1]]==0:
        now = que.popleft()
        y,x = now
        up,down,left,right = [y-1,x],[y+1,x],[y,x-1],[y,x+1]

        #up
        if visited[up[0]][up[1]]==0:
            if graph[up[0]][up[1]]==".":
                que.append(up)
                visited[up[0]][up[1]]= visited[y][x]+1
            
        #down
        if visited[down[0]][down[1]]==0:
            if graph[down[0]][down[1]]==".":
                que.append(down)
                visited[down[0]][down[1]]= visited[y][x]+1
        #left
        if visited[left[0]][left[1]]==0:
            if graph[left[0]][left[1]]==".":
                que.append(left)
                visited[left[0]][left[1]]= visited[y][x]+1
        #right
        if visited[right[0]][right[1]]==0:
            if graph[right[0]][right[1]]==".":
                que.append(right)
                visited[right[0]][right[1]]= visited[y][x]+1
    
    return visited[end[0]][end[1]]

def main():
    h,w = map(int,input().split())
    ls = [list(input()) for _ in range(h)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if ls[i][j]=="#":
                cnt += 1

    dummy = ["#" for _ in range(w+2)]
    for i in range(h):
        ls[i].append("#")
        ls[i].insert(0,"#")
    ls.insert(0,dummy)
    ls.append(dummy)

    step = DFS(ls,[1,1],[h,w])+1

    print(h*w-step-cnt)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

origin = 0
for i in maze:
    origin += i.count('#')
# print(origin)


def bfs(y, x, cnt):
    if (y < 0 or h <= y or x < 0 or w <= x):
        return
    if (maze[y][x] != '.'):
        return
    maze[y][x] = cnt
    if (y == h - 1 and x == w - 1):
        return cnt
    queue.append([y + 1, x, cnt + 1])
    queue.append([y - 1, x, cnt + 1])
    queue.append([y, x+1, cnt+1])
    queue.append([y, x-1, cnt+1])


queue.append([0, 0, 0])
while (len(queue) > 0):
    l = queue.popleft()
    bfs(l[0], l[1], l[2])

# print(ans)
print(h*w-origin-maze[h-1][w-1]-1)

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
ls = [input().rstrip() for _ in range(h)]
ds = [[float('inf') for _ in range(w)] for _ in range(h)]
ds[0][0] = 1

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


def bfs(x, y):
    for i in range(4):
        dx, dy = dxdy[i]
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and ls[ny][nx] == '.':
            if ds[ny][nx] > ds[y][x] + 1:
                ds[ny][nx] = ds[y][x] + 1
                bfs(nx, ny)


bfs(0, 0)
d = ds[h - 1][w - 1]
if d < float('inf'):
    s = sum([l.count('.') for l in ls])
    print(s - d)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import collections
H,W = map(int,input().split())
Map = []
black_cnt = 0
for i in range(H):
    tmp = list(input())
    black_cnt += tmp.count('#')
    Map.append(tmp)

Counter = [[float('inf') for j in range(W)]for i in range(H)]
Visited = [[False for j in range(W)]for i in range(H)]
q = collections.deque()
q.append((0,0,0))
while q:
    y,x,cnt = q.popleft()
    if 0>y or H<=y or 0>x or W<=x:
        continue
    if Map[y][x] == '#':
        continue
    if cnt > Counter[y][x]:
        continue
    if Visited[y][x]:
        continue
    Visited[y][x]=True
    Map[y][x] = cnt
    cnt += 1
    q.append((y+1,x,cnt))
    q.append((y-1,x,cnt))
    q.append((y,x+1,cnt))
    q.append((y,x-1,cnt))
print(H*W-Map[H-1][W-1]-black_cnt-1)

Submission status: Runtime Error

Solution code:
import queue

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

A=[list(map(lambda x:0 if x=='#' else 1, input())) for i in range(H)]

q=queue.Queue()
q.put([0,0,0])

T=[[-1]*W for i in range(W)]
T[0][0]=0
while not(q.empty()):
	y,x,d=q.get()
	if T[y][x]!=-1:
		continue
	for nx,ny in [[x-1,y],[x+1,y],[x,y+1],[x,y-1]]:
		if 0<=nx<W and 0<=ny<H and A[ny][nx]:
			T[ny][nx] = T[y][x]+1
			q.put([ny,nx,d+1])

cnt=0
for i in range(H):
	cnt+=sum(A[i])

if T[H-1][W-1]==-1:print(-1)
else:print(cnt-T[H-1][W-1]-1)

Submission status: Runtime Error

Solution code:
import queue

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

A=[list(map(lambda x:0 if x=='#' else 1, input())) for i in range(H)]

q=queue.Queue()
q.put([0,0,0])

T=[[-1]*W for i in range(W)]
T[0][0]=0
while not(q.empty()):
	y,x,d=q.get()
	for nx,ny in [[x-1,y],[x+1,y],[x,y+1],[x,y-1]]:
		if 0<=nx<W and 0<=ny<H and A[ny][nx]:
			T[ny][nx] = T[y][x]+1
			q.put([ny,nx,d+1])

cnt=0
for i in range(H):
	cnt+=sum(A[i])

if T[H-1][W-1]==-1:print(-1)
else:print(cnt-T[H-1][W-1]-1)

Submission status: Runtime Error

Solution code:
import queue

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

A=[list(map(lambda x:0 if x=='#' else 1, input())) for i in range(H)]

q=queue.Queue()
q.put([0,0,0])

T=[[-1]*W for i in range(W)]

while not(q.empty()):
	y,x,d=q.get()
	if T[y][x]!=-1:
		T[y][x]=min(T[y][x],d)
	else:
		T[y][x]=d
		for nx,ny in [[x-1,y],[x+1,y],[x,y+1],[x,y-1]]:
			if 0<=nx<W and 0<=ny<H and A[ny][nx]:
				q.put([ny,nx,d+1])

cnt=0
for i in range(H):
	cnt+=sum(A[i])

if T[H-1][W-1]==-1:print(-1)
else:print(cnt-T[H-1][W-1]-1)

Submission status: Runtime Error

Solution code:
import queue

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

A=[list(map(lambda x:0 if x=='#' else 1, input())) for i in range(H)]

q=queue.Queue()
q.put([0,0,0])

T=[[-1]*W for i in range(W)]

while not(q.empty()):
	y,x,d=q.get()
	if T[y][x]!=-1:
		T[y][x]=min(T[y][x],d)
	else:
		T[y][x]=d
		for nx,ny in [[x-1,y],[x+1,y],[x,y+1],[x,y-1]]:
			if 0<=nx<W and 0<=ny<H and A[ny][nx]:
				q.put([ny,nx,d+1])

cnt=0
for i in range(H):
	cnt+=sum(A[i])


print(cnt-T[H-1][W-1]-1)

Submission status: Runtime Error

Solution code:
from collections import deque

def dfs(stage , visited , start_x,start_y,goal_x,goal_y):
    queue = deque([[start_x,start_y]])
    visited[start_x][start_y] = 1
    while queue:
        x , y = queue.popleft()
        if [x , y] == [goal_x,goal_y]:
            return visited[x][y]
        for dx , dy in ([1,0],[-1,0],[0,1],[0,-1]):
            new_x , new_y = x + dx , dy + y
            #print(new_x,new_y)
            if 0 <= new_x <= goal_x and 0 <= new_y <= goal_y  and stage[new_x][new_y] == "." and visited[new_x][new_y] == -1:
                #print(new_x , new_y)
                visited[new_x][new_y] = visited[x][y] + 1
                queue.append([new_x,new_y])
        #print(queue)
if __name__ == "__main__":
    H , W = map(int , input().split())
    stage = []
    for _ in range(H):
        stage.append(list(input()))
    start_x,start_y ,goal_x,goal_y = 0,0,H-1,W-1
    visited = [[-1] * W for _ in range(H)]
    #print(visited)
    #print(stage)
    #print(visited[0][1])
    sum = 0
    for value in stage:
        sum += value.count('.')
    #print(sum)
    print(sum - dfs(stage,visited,start_x,start_y,goal_x,goal_y))

Submission status: Runtime Error

Solution code:
from collections import deque
h,w = map(int, input().split())
map = [list(input()) for _ in range(h)]
dis = [[float("inf")]*w for _ in range(h)]
dy = [1,0,-1,0]
dx = [0,1,0,-1]
que = deque([])
que.append((0,0))
dis[0][0]=1
count = 0

for num in range(h*w):
    p = que.popleft()
    if p[0]==h-1 and p[1]==w-1:
        break
    for i in range(4):
        ny = p[0] + dy[i]
        nx = p[1] + dx[i]
        if 0<=ny<h and 0<=nx<w and map[ny][nx]!="#" \
           and dis[ny][nx]==float("inf"):
            que.append((ny,nx))
            dis[ny][nx]=dis[p[0]][p[1]]+1

for i in range(h):
    for j in range(w):
        if map[i][j]=="#":
            count+=1

print(h*w-dis[h-1][w-1]-count if dis[h-1][w-1]!=float("inf") else -1)

Submission status: Runtime Error

Solution code:
from collections import deque
#入力
h,w = map(int, input().split())
w = w + 2
maze = [list('#' * (w))]
for i in range(h):
    maze.append(list('#' + input() + '#')) #迷路の読み込み
maze.append(list('#' * (w)))
h = h + 2
                
distance = [[float('inf')] * w for i in range(h)] #まずは無限大の距離と仮定

que = deque() #座標と距離を保存
que.append((1,1,0)) #スタートの座標と距離を入力

while que:
    i,j,k = que.popleft() #先頭を取得
    for di,dj in move:
        if maze[i+di][j+dj] == '.' and distance[i+di][j+dj] > k+1:
            #迷路の道で，今までの距離が今出した距離より長いなら
            distance[i+di][j+dj] = k+1 #より短い今の距離に更新し
            que.append((i+di,j+dj,k+1)) #queの末尾に追加

#初期の道のカウント
road = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            road = road + 1

if distance[h-2][w-2] != float('inf'):
    minimum_distance = distance[h-2][w-2]
else:
    minimum_distance = road

print(road - minimum_distance - 1)

Submission status: Runtime Error

Solution code:
from collections import deque
#入力
h,w = map(int, input().split())
w = w + 2
maze = [list('#' * (w))]
for i in range(h):
    maze.append(list('#' + input() + '#')) #迷路の読み込み
maze.append(list('#' * (w)))
h = h + 2
                
distance = [[float('inf')] * w for i in range(h)] #まずは無限大の距離と仮定

que = deque() #座標と距離を保存
que.append((1,1,0)) #スタートの座標と距離を入力

while que:
    i,j,k = que.popleft() #先頭を取得
    for di,dj in move:
        if maze[i+di][j+dj] == '.' and distance[i+di][j+dj] > k+1:
            #迷路の道で，今までの距離が今出した距離より長いなら
            distance[i+di][j+dj] = k+1 #より短い今の距離に更新し
            que.append((i+di,j+dj,k+1)) #queの末尾に追加

minimum_distance = distance[h-2][w-2]

#初期の道のカウント
road = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            road = road + 1

print(road - minimum_distance - 1)

Submission status: Runtime Error

Solution code:

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

s = []

for i in range(H):

    S = list(input())
    s.append(S)

Q = [[0,0]]
shnum = 0

#print (s)

for i in range(H):

    for j in range(W):

        if s[i][j] == "#":

            shnum += 1


while len(Q) > 0:

    #print (Q)
    #print (s)

    now = Q.pop(0)

    if now[0] == 0 and now[1] == 0:
        s[0][0] = 1
        Q.append([0,1])
        Q.append([1,0])

    elif s[now[0]][now[1]] == "#":
        continue;

    else:

        if s[now[0]][now[1]] == ".":

            far = 10000

        else:

            far = s[now[0]][now[1]]

        flag = 0

        if now[0]-1 >= 0 and s[now[0]-1][now[1]] not in [-1,"#","."]:

            if far > s[now[0]-1][now[1]]+1:
                far = s[now[0]-1][now[1]]+1
                flag = 1

        if now[1]-1 >= 0 and s[now[0]][now[1]-1] not in [-1,"#","."]:

            if far > s[now[0]][now[1]-1]+1:
                far = s[now[0]][now[1]-1]+1
                flag = 2

        if now[0]+1 < H and s[now[0]+1][now[1]] not in [-1,"#","."]:

            if far > s[now[0]+1][now[1]]+1:
                far = s[now[0]+1][now[1]]+1
                flag = 3

        if now[1]+1 < W and s[now[0]][now[1]+1] not in [-1,"#","."]:

            if far > s[now[0]][now[1]+1]+1:
                far = s[now[0]][now[1]+1]+1
                flag = 4

        if flag != 0:
            
            s[now[0]][now[1]] = far

            if now[0]-1 >= 0 and flag != 1:

                Q.append([now[0]-1,now[1]])

            if now[1]-1 >= 0 and flag != 2:

                Q.append([now[0],now[1]-1])

            if now[0]+1 < H and flag != 3:

                Q.append([now[0]+1,now[1]])

            if now[1]+1 < W and flag != 4:

                Q.append([now[0],now[1]+1])


if s[-1][-1] == -1:
    print (-1)

else:
    print (H*W - s[-1][-1] - shnum)

Submission status: Runtime Error

Solution code:
from itertools import product

H, W = map(int, input().split())
S = [input() for _ in range(H)]
G = [[float("inf")]*W for _ in range(H)]
G[0][0] = 1

for _  i, j in product(range(H*W), range(H), range(W)) :
    if S[i][j] == "." :
        for x, y in [(1, 0), (0, 1), (-1, 0), (0, -1)] :
            try :
                G[i][j] = min(1+G[i+x][j+y], G[i][j])
            except : pass

d = sum(s.count(".") for s in S)
a = d-G[-1][-1]
print(-1 if a==-float("inf") else a)

Submission status: Runtime Error

Solution code:
# ABC088D - Grid Repainting
import sys
input = sys.stdin.readline

def dfs(x: int, y: int, cur: int) -> None:
    D[x][y] = cur
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy  # next x, y
        if nx < H and ny < W and S[nx][ny] == "." and D[nx][ny] == 0:
            dfs(a, b, cur + 1)


def main():
    global H, W, S, D, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    D = [[0] * W for _ in range(H)]  # distance
    dxy = [(1, 0), (0, 1)]
    dfs(0, 0, 1)
    white, x = sum(s.count(".") for s in S), D[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# ABC088D - Grid Repainting
import sys

input = sys.stdin.readline


def dfs(x: int, y: int, cur: int) -> None:
    D[x][y] = cur
    for dx, dy in dxy:
        a, b = x + dx, y + dy
        if a < H and b < W and S[a][b] == "." and D[a][b] == 0:
            dfs(a, b, cur + 1)


def main():
    global H, W, S, D, dxy
    H, W = tuple(map(int, input().split()))
    S = tuple(input().rstrip() for _ in range(H))
    D = [[0] * W for _ in range(H)]  # distance
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    dfs(0, 0, 1)
    white, x = sum(s.count(".") for s in S), D[-1][-1]
    ans = white - x if x else -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
def main():
    H,W = map(int,input().split())
    s = [list(map(str,input())) for _ in range(H)]
    INF = 10**5
    maze_list = [[INF for _ in range(W)] for _ in range(H)]
    maze_list[0][0] = 0
    def item(array):
        return [item for sublist in array for item in sublist]

    counter = sorted(list(Counter(item(s)).items()))

    queue = []
    queue.insert(0,(0,0))
    while len(queue):
        x,y = queue.pop()
        if x == H-1 and y == W-1:
            break
        for i in range(4):
            nx,ny = x + [1,0,-1,0][i],y + [0,1,0,-1][i]
            if (0<=nx and nx<H and 0<=ny and ny<W):
                if (s[nx][ny]!="#" and maze_list[nx][ny]==INF):
                    queue.insert(0,(nx,ny))
                    maze_list[nx][ny] = maze_list[x][y] + 1

    if maze_list[H-1][W-1] == INF:
        print(-1)
    else:
        print(counter[1][1]-maze_list[H-1][W-1]-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from collections import deque
def bfs(Y,X,count):
    # print("now",Y+1,X+1)
    # print(count,"手目")
    reached[Y][X]=True

    if Y==goalY and X==goalX:
        result=0
        for i in range(H):
            for j in range(W):
                if F[i][j]=="#":
                    result+=1
        print(H*W - result - count -1)
        exit(1)

    if Y < H-1 :
        if F[Y+1][X]=="." and reached[Y+1][X]==False:
            # print(Y+1+1,X+1,"を積みます")
            yQUE.appendleft(Y+1)
            xQUE.appendleft(X)
            cQUE.appendleft(count+1)
            reached[Y+1][X]=True
    if X < W-1 :
        if F[Y][X+1]=="." and reached[Y][X+1]==False:
            # print(Y+1,X+1+1,"を積みます")
            yQUE.appendleft(Y)
            xQUE.appendleft(X+1)
            cQUE.appendleft(count+1)
            reached[Y][X+1]=True
    if 0 < Y :
        if F[Y-1][X]=="." and reached[Y-1][X]==False:
            # print(Y-1+1,X+1,"を積みます")
            yQUE.appendleft(Y-1)
            xQUE.appendleft(X)
            cQUE.appendleft(count+1)
            reached[Y-1][X]=True
    if 0 < X :
        if F[Y][X-1]=="." and reached[Y][X-1]==False:
            # print(Y+1,X-1+1,"を積みます")
            yQUE.appendleft(Y)
            xQUE.appendleft(X-1)
            cQUE.appendleft(count+1)
            reached[Y][X-1]=True    
    try:
        bfs(yQUE.pop(),xQUE.pop(),cQUE.pop())
    except IndexError:
        print("-1")

H,W = map(int,input().split())
# R,C=7,8
# startY,startX = map(int,input().split())
startY=0
startX=0
# startY,startX = 1,1
# goalY,goalX = map(int,input().split())
goalX=W-1
goalY=H-1
# goalY,goalX = 3,4
F = list(list(input()) for _ in range(H))
# F = [
# '########',
# '#......#',
# '#.######',
# '#..#...#',
# '#..##..#',
# '##.....#',
# '########']
reached = [[False for i in range(W)] for i in range(H)]
count=0
# for i in range (R):
#     print("".join(F[i]))
xQUE =  deque(maxlen=1000000000)
yQUE =  deque(maxlen=1000000000)
cQUE =  deque()
# result=0
# for i in range(H):
#     for j in range(W):
#         if F[i][j]=="#":
#             result+=1
# print(result)
bfs(startY,startX,count)
# print(QUE)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from collections import deque
def bfs(Y,X,count):
    # print("now",Y+1,X+1)
    # print(count,"手目")
    reached[Y][X]=True

    if Y==goalY and X==goalX:
        result=0
        for i in range(H):
            for j in range(W):
                if F[i][j]=="#":
                    result+=1
        print(H*W - result - count -1)
        exit()

    if Y < H-1 :
        if F[Y+1][X]=="." and reached[Y+1][X]==False:
            # print(Y+1+1,X+1,"を積みます")
            yQUE.appendleft(Y+1)
            xQUE.appendleft(X)
            cQUE.appendleft(count+1)
            reached[Y+1][X]=True
    if X < W-1 :
        if F[Y][X+1]=="." and reached[Y][X+1]==False:
            # print(Y+1,X+1+1,"を積みます")
            yQUE.appendleft(Y)
            xQUE.appendleft(X+1)
            cQUE.appendleft(count+1)
            reached[Y][X+1]=True
    if 0 < Y :
        if F[Y-1][X]=="." and reached[Y-1][X]==False:
            # print(Y-1+1,X+1,"を積みます")
            yQUE.appendleft(Y-1)
            xQUE.appendleft(X)
            cQUE.appendleft(count+1)
            reached[Y-1][X]=True
    if 0 < X :
        if F[Y][X-1]=="." and reached[Y][X-1]==False:
            # print(Y+1,X-1+1,"を積みます")
            yQUE.appendleft(Y)
            xQUE.appendleft(X-1)
            cQUE.appendleft(count+1)
            reached[Y][X-1]=True    
    bfs(yQUE.pop(),xQUE.pop(),cQUE.pop())

H,W = map(int,input().split())
# R,C=7,8
# startY,startX = map(int,input().split())
startY=0
startX=0
# startY,startX = 1,1
# goalY,goalX = map(int,input().split())
goalX=W-1
goalY=H-1
# goalY,goalX = 3,4
F = list(list(input()) for _ in range(H))
# F = [
# '########',
# '#......#',
# '#.######',
# '#..#...#',
# '#..##..#',
# '##.....#',
# '########']
reached = [[False for i in range(W)] for i in range(H)]
count=0
# for i in range (R):
#     print("".join(F[i]))
xQUE =  deque(maxlen=100000)
yQUE =  deque(maxlen=100000)
cQUE =  deque()
# result=0
# for i in range(H):
#     for j in range(W):
#         if F[i][j]=="#":
#             result+=1
# print(result)
bfs(startY,startX,count)
# print(QUE)
print("-1")