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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF = float('inf')
H,W = map(int,input().split())
s = [input() for _ in range(H)]
cost = [[INF]*W for _ in range(H)]
cost[0][0] = 1
 
def bfs(h,w):
    for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=h+dh<H and 0<=w+dw<W:
            if s[h+dh][w+dw] == '.' and cost[h+dh][w+dw] > cost[h][w]+1:
                cost[h+dh][w+dw] = cost[h][w]+1
                bfs(h+dh,w+dw)
bfs(0,0)
if cost[-1][-1] == INF:
    print(-1)
else:
    ans = H*W-cost[-1][-1]
    for h in range(H):
        ans -= s[h].count('#')
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
count=0
queue=deque([[0,0,0]])
for i in range(h):
    for j in range(w):
        if field[i][j]=='.':
            count+=1
def bfs(x,y,k):
    if (not 0<=x<h) or (not 0<=y<w):
        return
    if field[x][y]=='#':
        return
    queue.append([x,y,k+1])
    
while True:
    if len(queue)==0:
        break
    x,y,k=queue.popleft()
#    print(queue)
#    print(field)
    if x==h-1 and y==w-1:
        print(count-k-1)
        sys.exit()
    
    field[x][y]='#'
    bfs(x+1,y,k)
    bfs(x-1,y,k)
    bfs(x,y-1,k)
    bfs(x,y+1,k)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
d=[(0,1),(1,0),(0,-1),(-1,0)]
h,w=map(int,input().split())
v=[[0]*w for _ in range(h)]
a=[]
for i in range(h):
    s=input()
    a.append([i for i in s])

wh=sum([''.join(i).count('.') for i in a])

def bfs(t,s,u):
    rt=0
    q=deque([(t,s,u)])
    while q:
        y,x,depth=q.popleft()
        v[y][x]=1
        if (y,x)==(h-1,w-1):  # condtion for finish
            return depth
        for dx,dy in d:
            if 0<=y+dy<h and 0<=x+dx<w and v[y+dy][x+dx]==0:
                if a[y+dy][x+dx]=='.':  # condition that the next cell is fine
                    q.append((y+dy,x+dx,depth+1))
    return -1

dis=bfs(0,0,1)
ans=wh-dis if dis>=0 else dis
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
inf=10**10

def dijkstra(s,n,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    for i in range(H):
        for j in range(W):
            if x[i][j]==inf: used[i*W+j]=True
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        p=[]    
        if v>W-1: p.append(v-W)
        if v+W<H*W: p.append(v+W)
        if v%W>0: p.append(v-1)
        if v%W<W-1: p.append(v+1)
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


def f(s):
    r=[]
    for j in range(W):
        if s[j]=="#": r.append(inf)
        elif s[j]==".": r.append(0)
    return r

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

cost = [[float("inf") for i in range(H*W)] for i in range(H*W)] 
for i in range(H*W):
    for j in range(H*W):
        if x[i//W][i%W]==inf or x[j//W][j%W]==inf: continue
        if abs(i-j)==W: cost[i][j],cost[j][i]=1,1
        elif i-j==1 and i%W!=0: cost[i][j],cost[j][i]=1,1
        elif j-i==1 and j%W!=0: cost[i][j],cost[j][i]=1,1

ans=0
for i in range(H):
    for j in range(W):
        if x[i][j]==0: ans+=1

ans-=dijkstra(0,H*W,cost)[H*W-1]+1
print(ans if ans>=0 else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
inf=10**10

def dijkstra(s,n,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        p=[]    
        if v>W-1: p.append(v-W)
        if v+W<H*W: p.append(v+W)
        if v%W>0: p.append(v-1)
        if v%W<W-1: p.append(v+1)
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


def f(s):
    r=[]
    for j in range(W):
        if s[j]=="#": r.append(inf)
        elif s[j]==".": r.append(0)
    return r

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

cost = [[float("inf") for i in range(H*W)] for i in range(H*W)] 
for i in range(H*W):
    for j in range(H*W):
        if x[i//W][i%W]==inf or x[j//W][j%W]==inf: continue
        if abs(i-j)==W: cost[i][j],cost[j][i]=1,1
        elif i-j==1 and i%W!=0: cost[i][j],cost[j][i]=1,1
        elif j-i==1 and j%W!=0: cost[i][j],cost[j][i]=1,1

ans=0
for i in range(H):
    for j in range(W):
        if x[i][j]==0: ans+=1

ans-=dijkstra(0,H*W,cost)[H*W-1]+1
print(ans if ans>=0 else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
inf=10**10

def dijkstra(s,n,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


def f(s):
    r=[]
    for j in range(W):
        if s[j]=="#": r.append(inf)
        elif s[j]==".": r.append(0)
    return r

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

cost = [[float("inf") for i in range(H*W)] for i in range(H*W)] 
for i in range(H*W):
    for j in range(H*W):
        if x[i//W][i%W]==inf or x[j//W][j%W]==inf: continue
        if abs(i-j)==W: cost[i][j],cost[j][i]=1,1
        elif i-j==1 and i%W!=0: cost[i][j],cost[j][i]=1,1
        elif j-i==1 and j%W!=0: cost[i][j],cost[j][i]=1,1

ans=0
for i in range(H):
    for j in range(W):
        if x[i][j]==0: ans+=1

ans-=dijkstra(0,H*W,cost)[H*W-1]+1
print(ans if ans>=0 else -1)

Submission status: Time Limit Exceeded

Solution code:
#ABC088-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w=IL()
G=[S() for i in range(h)]
used=[[False for i in range(w)] for j in range(h)]
q=[[0,0,1]]
pos=False
while len(q)>0:
    gy,gx,dis=q.pop(0)
    if gy==h-1 and gx==w-1:
        pos=True
        break
    if not used[gy][gx]:
        if gy!=0:
            if G[gy-1][gx]=="." and not used[gy-1][gx]:
                q.append([gy-1,gx,dis+1])
        if gx!=0:
            if G[gy][gx-1]=="." and not used[gy][gx-1]:
                q.append([gy,gx-1,dis+1])
        if gy!=h-1:
            if G[gy+1][gx]=="." and not used[gy+1][gx]:
                q.append([gy+1,gx,dis+1])
        if gx!=w-1:
            if G[gy][gx+1]=="." and not used[gy][gx+1]:
                q.append([gy,gx+1,dis+1])
if pos:
    ans=0
    for i in range(h):
        ans+=G[i].count(".")
    print(ans-dis)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int, input().split())
S=[input() for i in range(H)]
s=[[0]*W for h in range(H)]
b=0
for h in range(H):
    for w in range(W):
        if S[h][w]=='#':
            s[h][w]=-1
            b+=1
q=[]
i=1
q.append((0,0))
import sys
while (H-1,W-1) not in q:
    q2=[]
    for h,w in q:
        s[h][w]=i
        if h>0 and s[h-1][w]==0:
            q2.append((h-1,w))
        if h<H-1 and s[h+1][w]==0:
            q2.append((h+1,w))
        if w>0 and s[h][w-1]==0:
            q2.append((h,w-1))
        if w<W-1 and s[h][w+1]==0:
            q2.append((h,w+1))
    if len(q)==0:
        break
    q=q2
    i+=1
if len(q)==0:
    print(-1)
else:
    print(H*W-i-b)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int, input().split())
S=[input() for i in range(H)]
s=[[0]*W for h in range(H)]
b=0
for h in range(H):
    for w in range(W):
        if S[h][w]=='#':
            s[h][w]=-1
            b+=1
q=[]
i=1
q.append((0,0))
while (H-1,W-1) not in q:
    q2=[]
    for h,w in q:
        s[h][w]=i
        if h>0 and s[h-1][w]==0:
            q2.append((h-1,w))
        if h<H-1 and s[h+1][w]==0:
            q2.append((h+1,w))
        if w>0 and s[h][w-1]==0:
            q2.append((h,w-1))
        if w<W-1 and s[h][w+1]==0:
            q2.append((h,w+1))
    q=q2
    i+=1
print(H*W-i-b)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
for _ in range(H):
    s = input()
    S.append(s)
    
import copy
maze = copy.deepcopy(S)

import queue

INT_MAX = 2**63-1
stayed = [[INT_MAX] * W for _ in range(H)]

def bfs():
    gole = (W-1, H-1)
    q = queue.Queue()
    q.put((
        0, # current x
        0, # current y
        0, # count
    ))

    while q:
        cur_x, cur_y, cnt = q.get()
        if (cur_x, cur_y) == gole:
            return cnt
        
        next_pos = [
            (cur_x, cur_y-1),
            (cur_x, cur_y+1),
            (cur_x-1, cur_y),
            (cur_x+1, cur_y)
        ]
        
        for x, y in next_pos:
            if x == -1 or y == -1 or x == W or y == H:
                continue
            if S[y][x] == '#':
                continue
            if stayed[y][x] > cnt+1:
                stayed[y][x] = cnt+1
                q.put((x, y, cnt+1))
    return -1
            

shortest_path_len = bfs()

if shortest_path_len != -1:
    cnt_dot = sum([s.count('.') for s in maze])


    ans = cnt_dot - shortest_path_len - 1
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
for _ in range(H):
    s = input()
    S.append(s)
    
import copy
maze = copy.deepcopy(S)

import queue

INT_MAX = 2**63-1
stayed = [[INT_MAX] * W for _ in range(H)]

def bfs():
    gole = (W-1, H-1)
    q = queue.Queue()
    q.put((
        0, # current x
        0, # current y
        0, # count
    ))

    while q:
        cur_x, cur_y, cnt = q.get()
        if (cur_x, cur_y) == gole:
            return cnt
        
        next_pos = [
            (cur_x, cur_y-1),
            (cur_x, cur_y+1),
            (cur_x-1, cur_y),
            (cur_x+1, cur_y)
        ]
        
        for x, y in next_pos:
            if x == -1 or y == -1 or x == W or y == H:
                continue
            if S[y][x] == '#':
                continue
            if stayed[y][x] > cnt+1:
                stayed[y][x] = cnt+1
                q.put((x, y, cnt+1))
            

shortest_path_len = bfs()

cnt_dot = sum([s.count('.') for s in maze])


#print(shortest_path_len)
#print(cnt_dot)

ans = cnt_dot - shortest_path_len - 1
print(ans)
#print(stayed)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
# C = [list(input()) for _ in range(H)]
C = []
pre = 0
for i in range(H):
    c = list(input())
    pre += c.count("#")
    C.append(c)

current_list = [(0, 0)]
count = 1
 
while C[H-1][W-1] == '.' or count >= 3000:
    count += 1
    next_list = []
    for y,x in current_list:
        for i,j in ((1,0),(0,1),):
            if x+j < W and y+i < H:
                if C[y+i][x+j] == '.':
                    C[y+i][x+j] = count
                    next_list.append((y+i,x+j))
    current_list = list(set(next_list))
if count >= 3000:
    print(-1)
else:
    print(H*W-pre-count)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
# C = [list(input()) for _ in range(H)]
C = []
pre = 0
for i in range(H):
    c = list(input())
    pre += c.count("#")
    C.append(c)

current_list = [(0, 0)]
count = 1
 
while C[H-1][W-1] == '.':
    count += 1
    next_list = []
    for y,x in current_list:
        for i,j in ((1,0),(0,1),):
            if x+j < W and y+i < H:
                if C[y+i][x+j] == '.':
                    C[y+i][x+j] = count
                    next_list.append((y+i,x+j))
    current_list = list(set(next_list))
print(H*W-pre-count)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
# C = [list(input()) for _ in range(H)]
C = []
pre = 0
for i in range(H):
    c = list(input())
    pre += c.count("#")
    C.append(c)

list = [(0, 0)]
count = 1
 
while C[H-1][W-1] == '.':
    count += 1
    next_list = []
    for y,x in list:
        for i,j in ((1,0),(0,1),):
            if x+j < W and y+i < H:
                if C[y+i][x+j] == '.':
                    C[y+i][x+j] = count
                    next_list.append((y+i,x+j))
    list = next_list
print(H*W-pre-count)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

#入力
H, W = map(int, input().split())

lst = []
for i in range(H):
    lst += [list(input())]

count = 0 #白色のマスの総数
for i in range(H):
    for j in range(W):
        if lst[i][j] == '.':
            count += 1

sx, sy = 1, 1 #スタート位置
gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs(x, y):
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(x)
    q.put(y)
    d[x][y] = 0

    while True:
        px = q.get()
        py = q.get()
        if px == gx-1 and py == gy-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[gx-1][gy-1]

a = bfs(sx-1, sy-1)

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

#sx, sy = 1, 1 #スタート位置
#gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = Queue()
    INF = 10 ** 3
    d = [[INF]* W for _ in range(H)]
    q.put(0)
    q.put(0)
    d[0][0] = 0

    while True:
        px = q.get()
        py = q.get()
        if px == H-1 and py == W-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[H-1][W-1]

a = bfs()

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

#入力
H, W = map(int, input().split())

lst = []
for i in range(H):
    lst += [list(input())]

count = 0 #白色のマスの総数
for i in range(H):
    for j in range(W):
        if lst[i][j] == '.':
            count += 1

sx, sy = 1, 1 #スタート位置
gx, gy = H, W #ゴール位置

move = [[1, 0], [0,1], [-1, 0], [0, -1]]

def bfs(x, y):
    q = Queue()
    INF = 10 ** 3
    d = [[INF]* W for _ in range(H)]
    q.put(x)
    q.put(y)
    d[x][y] = 0

    while True:
        px = q.get()
        py = q.get()
        if px == gx-1 and py == gy-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[gx-1][gy-1]

a = bfs(sx-1, sy-1)

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

#入力
H, W = map(int, input().split())

lst = []
for i in range(H):
    lst += [list(input())]

count = 0 #白色のマスの総数
for i in range(H):
    for j in range(W):
        if lst[i][j] == '.':
            count += 1

sx, sy = 1, 1 #スタート位置
gx, gy = H, W #ゴール位置

move = [[1, 0], [0,1], [-1, 0], [0, -1]]

def bfs(x, y):
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(x)
    q.put(y)
    d[x][y] = 0

    while True:
        px = q.get()
        py = q.get()
        if px == gx-1 and py == gy-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[gx-1][gy-1]

a = bfs(sx-1, sy-1)

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

sx, sy = 1, 1 #スタート位置
gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs(x, y):
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(x)
    q.put(y)
    d[x][y] = 0

    while True:
        px = q.get()
        py = q.get()
        if px == gx-1 and py == gy-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[gx-1][gy-1]

a = bfs(sx-1, sy-1)

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

#入力
H, W = map(int, input().split())

lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
for i in range(H):
    row = input()
    for j in range(W):
        lst[i][j] = row[j]
        if row[j] == '.':
            count += 1

 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

sx, sy = 1, 1 #スタート位置
gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs(x, y):
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(x)
    q.put(y)
    d[x][y] = 0

    while True:
        px = q.get()
        py = q.get()
        if px == gx-1 and py == gy-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[gx-1][gy-1]

a = bfs(sx-1, sy-1)

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

#入力
H, W = map(int, input().split())

lst = []
for i in range(H):
    lst += [list(input())]

count = 0 #白色のマスの総数
for i in range(H):
    for j in range(W):
        if lst[i][j] == '.':
            count += 1

sx, sy = 1, 1 #スタート位置
gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs(x, y):
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(x)
    q.put(y)
    d[x][y] = 0

    while True:
        px = q.get()
        py = q.get()
        if px == gx-1 and py == gy-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.put(nx)
                    q.put(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[gx-1][gy-1]

a = bfs(sx-1, sy-1)

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

Submission status: Time Limit Exceeded

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

import sys
import heapq
import copy
import itertools

inf = float('inf')
a = '.'
b = '#'

class Graph_dijkstra(object):
    def __init__(self, V: "List[int]", E: "Set[Tuple[Tuple, Tuple]]", L: "Dict[Tuple[Tuple, Tuple], int]"):
        self.V = V
        self.E = E
        self.L = L
        self.adjacent = self.init_adjacent() # type: Dict[int: List[int]]
        self.shortest_path = self.init_shortest_path() # type: Dict[FrozenSet[int, int], int]
    
    def init_adjacent(self):
        ret = {v: [] for v in self.V}
        for e in self.E:
            ret[e[0]].append(e[1])
        return ret
    
    def init_shortest_path(self):
        ret = {(s, g): inf for s, g in itertools.permutations(self.V, 2)}
        for v in self.V:
            ret[(v, v)] = 0
        return ret
    
    def dijkstra(self, s: int):
        D = {v: inf for v in self.V}
        D[s] = 0
        prev = {v: None for v in self.V}
        Q = [(0, s)]

        while len(Q) > 0:
            du, u = heapq.heappop(Q)
            for v in self.adjacent[u]:
                e = (u, v)
                alt = du + self.L[e]
                if alt < D[v]:
                    D[v] = alt
                    prev[v] = u
                    heapq.heappush(Q, (D[v], v))

        for v in self.V:
            self.shortest_path[(s, v)] = D[v]

    def find_shortest_path(self, s: int, g:int):
        d = self.shortest_path[(s, g)]
        if d < inf:
            return d
        self.dijkstra(s)
        return self.shortest_path[(s, g)]


def solve(H, W, s):
    V = []
    E = set()
    L = dict()
    direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    field = [[b for w in range(W+2)] for h in range(H+2)]
    white_count = 0
    for h in range(H):
        field[1+h][1:W+1] = s[h]
    for h in range(H):
        for w in range(W):
            if field[1+h][1+w] == b:
                continue
            V.append((1+h, 1+w))
            white_count += 1
            for d in direction:
                if field[1+h+d[0]][1+w+d[1]] == b:
                    continue
                e = ((1+h, 1+w), (1+h+d[0], 1+w+d[1]))
                E.add(e)
                L[e] = 1
    G = Graph_dijkstra(V, E, L)
    path_length = G.find_shortest_path((1, 1), (H, W))
    if path_length == inf:
        print(-1)
    else:
        print(white_count - (path_length + 1))
    return

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [[c for c in next(tokens)] for _ in range(H)]  # type: "List[str]"
    solve(H, W, s)
    pass

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def bfs(startx: int, starty: int) -> set:
    dxdy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    queue = deque()
    queue.appendleft((startx, starty, 0))
    reached = set()
    while queue:
        d = queue.pop()
        if d[0] == W - 1 and d[1] == H - 1:
            return d[2]
        for a in dxdy:
            x = d[0] + a[0]
            y = d[1] + a[1]
            if (x, y) not in reached and 0 <= x < W and 0 <= y < H and maze[y][x] != '#':
                queue.appendleft((x, y, d[2] + 1))
                reached.add(d[:2])
    return -1


d = bfs(0, 0)
if d == -1:
    print(-1)
    exit()
cnt = 0
for c in maze:
    cnt += c.count('#')
print(H * W - cnt - d - 1)

Submission status: Time Limit Exceeded

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

inmap = [input() for _ in range(H)]

q = queue.Queue(10)
q.put((0,0,1))

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

res = 0

visited = set([(0,0)])

while not q.empty():
    x,y,cnt=q.get(False)
    # print(x,y)
    if x+1 == W and y+1 == H:
        res = cnt
        break
    for dx, dy in cood:
        if x+dx >= 0 and x+dx < W and y+dy >= 0 and y+dy < H:
            # print(visited)
            if inmap[y+dy][x+dx] != '#' and not (x+dx, y+dy) in visited:
                q.put((x+dx, y+dy, cnt+1))
                visited.add((x+dx, y+dy))

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

# print((W-1, H-1) in visited)
if res == 0:
    print(-1)
else:
    print(H*W - black - res)

Submission status: Time Limit Exceeded

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

inmap = [input() for _ in range(H)]

q = queue.Queue(10)
q.put((0,0,1))

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

res = 0

visited = set([(0,0)])

while not q.empty():
    x,y,cnt=q.get(False)
    # print(x,y)
    if x+1 == W and y+1 == H:
        res = cnt
        break
    for dx, dy in cood:
        if x+dx >= 0 and x+dx < W and y+dy >= 0 and y+dy < H:
            # print(visited)
            if inmap[y+dy][x+dx] != '#' and not (x+dx, y+dy) in visited:
                q.put((x+dx, y+dy, cnt+1))
                visited.add((x+dx, y+dy))

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

# print((W-1, H-1) in visited)
if res == 0:
    print(-1)
else:
    print(H*W - black - res)

Submission status: Time Limit Exceeded

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

inmap = [input() for _ in range(H)]

q = queue.Queue(10)
q.put((0,0,1))

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

res = 0

visited = set([(0,0)])

while not q.empty():
    x,y,cnt=q.get()
    # print(x,y)
    if x+1 == W and y+1 == H:
        res = cnt
        break
    for dx, dy in cood:
        if x+dx >= 0 and x+dx < W and y+dy >= 0 and y+dy < H:
            # print(visited)
            if inmap[y+dy][x+dx] != '#' and not (x+dx, y+dy) in visited:
                q.put((x+dx, y+dy, cnt+1))
                visited.add((x+dx, y+dy))

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

# print((W-1, H-1) in visited)
if res == 0:
    print(-1)
else:
    print(H*W - black - res)

Submission status: Time Limit Exceeded

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

M=[]

w_count=0

for i in range(H):
    s=input()
    m=[]
    for j in range(W):
        if s[j]=='.':
            m.append(0)
            w_count+=1
        else:
            m.append(1)
    M.append(m)

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

for i in range(H):
    for j in range(W):
        if M[i][j]==0:
            if i!=H-1:
                if M[i+1][j]==0:
                    path[i][j].append([i+1,j])
                    path[i+1][j].append([i,j])
            if j!=W-1:
                if M[i][j+1]==0:
                    path[i][j].append([i,j+1])
                    path[i][j+1].append([i,j])

M_path = [[10**27 for j in range(W)] for i in range(H)]
M_checked = [[False for j in range(W)] for i in range(H)]
M_path[0][0]=0

from collections import deque

Q=deque([[0,0]])
M_checked[0][0]=True
while len(Q)>0:
    i,j=Q.pop()
    mp = M_path[i][j]
    for p in path[i][j]:
        if not M_checked[p[0]][p[1]]:
            M_checked[i][j]=True
            Q.appendleft(p)
            if mp+1 < M_path[p[0]][p[1]]:
                M_path[p[0]][p[1]] = mp+1

if M_path[H-1][W-1]<10**27:
    print(w_count-(M_path[H-1][W-1]+1))
else:
    print(-1)

Submission status: Time Limit Exceeded

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

M=[]

w_count=0

for i in range(H):
    s=input()
    m=[]
    for j in range(W):
        if s[j]=='.':
            m.append(0)
            w_count+=1
        else:
            m.append(1)
    M.append(m)

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

for i in range(H):
    for j in range(W):
        if M[i][j]==0:
            if i!=H-1:
                if M[i+1][j]==0:
                    path[i][j].append([i+1,j])
                    path[i+1][j].append([i,j])
            if j!=W-1:
                if M[i][j+1]==0:
                    path[i][j].append([i,j+1])
                    path[i][j+1].append([i,j])

M_path = [[10**27 for j in range(W)] for i in range(H)]
M_checked = [[False for j in range(W)] for i in range(H)]
M_path[0][0]=0

from collections import deque

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

while len(Q)>0:
    i,j=Q.pop()
    M_checked[i][j]=True
    mp = M_path[i][j]
    for p in path[i][j]:
        if not M_checked[p[0]][p[1]]:
            Q.appendleft(p)
            if mp+1 < M_path[p[0]][p[1]]:
                M_path[p[0]][p[1]] = mp+1

if M_path[H-1][W-1]<10**27:
    print(w_count-(M_path[H-1][W-1]+1))
else:
    print(-1)