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:
H, W = map(int,input().split())
maze = [[] for i in range(H)]
for i in range(H):
  maze[i] = list(input())
maze = [['#']*(W+2)]+maze+[['#']*(W+2)]
for i in range(1,H+1):
  maze[i] = ['#']+maze[i]+['#']
def Distance(maze, start, goal, distance):
  visited = set()
  frontier = set()
  visited.add(start)
  frontier.add(start)
  while goal not in visited:
    distance += 1
    newfrontier = set()
    for y,x in frontier:
      for gy,gx in [[y,x-1],[y-1,x],[y,x+1],[y+1,x]]:
        if (gy,gx) not in visited and maze[gy][gx] == '.':
          visited.add((gy,gx))
          newfrontier.add((gy,gx))
    frontier = newfrontier
  return distance
k = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if maze[i][j] == '#':
            k += 1
print(H*W-Distance(maze, (1,1), (H,W), 0)-1-k)

Submission status: Time Limit Exceeded

Solution code:
import queue

h, w = map(int, input().split())
s = '#'*(w+2)
for _ in range(h):
    s += '#' + input() + '#'
s += '#'*(w+2)

def bfs():
    step = [0]*(w+2)*(h+2)
    step[w+2+1] = 1
    q = queue.Queue()
    q.put(w+3)
    while q:
        x = q.get()
        for i in (1, -1, w+2, -w-2):
            if s[x+i] == '#':
                continue
            if x+i == (w+2)*(h+1) - 2:
                step[x+i] = step[x] + 1
                return step[x+i]
            if step[x+i] == 0:
                step[x+i] = step[x] + 1
                q.put(x+i)
    print(-1)
    exit()

count = 0
for j in range((w+2)*(h+2)):
    if s[j] == '.':
        count += 1

print(count - bfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)]
d=[[1,0],[-1,0],[0,1],[0,-1]]
bcnt=0
for i in range(h):
    bcnt+=s[i].count('#')
dist=[[1000]*w for _ in range(h)]
chk=[[0]*w for _ in range(h)]
r=deque()
r.append([0,0])
dist[0][0]=0
while r:
    x,y=r.popleft()
    chk[y][x]=1
    for dx,dy in d:
        nx=x+dx
        ny=y+dy
        nd=dist[y][x]
        if nx>=0 and nx<=w-1 and ny>=0 and ny<=h-1:
            if chk[ny][nx]==1 or s[ny][nx]=='#':
                continue
            dist[ny][nx]=min(dist[ny][nx],nd+1)
            r.append([nx,ny])
if dist[h-1][w-1]==1000:
    print(-1)
else:
    print(h*w-dist[h-1][w-1]-1-bcnt)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

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

for tate in s:
  for yoko in tate:
    if yoko=="#":
      black += 1

def search(y,x,H,W,s,zumi):
  child=[]
      
  if y<H-1:
    if s[y+1][x]==".":
      if [y+1,x] not in zumi:
        child.append([y+1,x])
  if 0<y:
    if s[y-1][x]==".":
      if [y-1,x] not in zumi:
        child.append([y-1,x])
  if 0<x:
    if s[y][x-1]==".":
      if [y,x-1] not in zumi:
        child.append([y,x-1])
  if x<W-1:
    if s[y][x+1]==".":
      if [y,x+1] not in zumi:
        child.append([y,x+1])
  return child

def dfs(y,x,cnt,H,W,s,zumi):
  node_to_visit=search(y,x,H,W,s,zumi)
  zumi=deepcopy(node_to_visit)
  flag=True
  
  while flag:
    cnt += 1
    tmp=[]
    tmp2=[]
    #print(node_to_visit)
    zumi += node_to_visit
    for next_point in node_to_visit:
      t=next_point[0] #y。たて
      u=next_point[1] #x。よこ
      tmp=search(t,u,H,W,s,zumi)
      tmp2 += tmp
    node_to_visit=deepcopy(tmp2)
    if [H-1,W-1] in node_to_visit:
      white=cnt
      flag=False
      break     
  ans=H*W-white-black-2
  #print(white,black,ans)
  print(ans)

zumi=[]
dfs(0,0,0,H,W,s,zumi)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = list(map(int, input().split(' ')))
FIELD = list()
for _ in range(H):
    FIELD.append(input())
removal_cell_flag = [[1 if FIELD[h][w] == '.' else 0 for w in range(W)] for h in range(H)]
sh, sw = 0, 0  # start
gh, gw = H - 1, W - 1  # goal
# We can get the maximum score
# when we change colors of cells which are not on the shortest path.
frontier = deque()
ch, cw = sh, sw
frontier.append((ch, cw))
explored_flag = [[0 for _ in range(W)] for _ in range(H)]
parent_table = [[None for _ in range(W)] for _ in range(H)]
while len(frontier) > 0:
    ch, cw = frontier.popleft()  # current
    if ch == gh and cw == gw:  # reach goal
        break
    explored_flag[ch][cw] = 1
    for dh, dw in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = ch + dh, cw + dw  # next
        if (nh < 0) or (H - 1 < nh) or (nw < 0) or (W - 1 < nw):
            continue
        if FIELD[nh][nw] == '#':
            continue
        if explored_flag[nh][nw] == 1:
            continue
        parent_table[nh][nw] = (ch, cw)
        frontier.append((nh, nw))
if ch != gh and cw != gw:
    print(-1)
    exit(0)
while True:
    removal_cell_flag[ch][cw] = 0
    if parent_table[ch][cw] is None:
        break
    ch, cw = parent_table[ch][cw]
print(sum([sum(row) for row in removal_cell_flag]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = list(map(int, input().split(' ')))
FIELD = list()
for _ in range(H):
    FIELD.append(input())
removal_cell_flag = [[1 if FIELD[h][w] == '.' else 0 for w in range(W)] for h in range(H)]
class Node:
    def __init__(self, h, w):
        self.h = h
        self.w = w
        self.parent = None
sh, sw = 0, 0  # start
gh, gw = H - 1, W - 1  # goal
# We can get the maximum score
# when we change colors of cells which are not on the shortest path.
frontier = deque()
frontier.append(Node(sh, sw))
explored_flag = [[0 for _ in range(W)] for _ in range(H)]
node = None
while len(frontier) > 0:
    node = frontier.popleft()
    if node.h == gh and node.w == gw:  # reach goal
        break
    explored_flag[node.h][node.w] = 1
    for dh, dw in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = node.h + dh, node.w + dw  # next
        if (nh < 0) or (H - 1 < nh) or (nw < 0) or (W - 1 < nw):
            continue
        if FIELD[nh][nw] == '#':
            continue
        if explored_flag[nh][nw] == 1:
            continue
        next_node = Node(nh, nw)
        next_node.parent = node
        frontier.append(next_node)
if node.h != gh and node.w != gw:
    print(-1)
    exit(0)
while True:
    removal_cell_flag[node.h][node.w] = 0
    if node.parent is None:
        break
    node = node.parent
print(sum([sum(row) for row in removal_cell_flag]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int,input().split())
cou = 0
ma = []
for i in range(h):
    kar = list(input())
    cou += kar.count("#")
    ma.append(kar)


ans = [[-1 for i in range(w)] for j in range(h)]
ans[0][0] = 1
q = deque([(0,0)])
xy = [(1,0),(-1,0),(0,1),(0,-1)]

while q:
    x , y = q.popleft()
    ma[x][y] = "#"
    for i in range(4):
        nx = x + xy[i][0]
        ny = y + xy[i][1]
        if 0 <= nx <= h-1 and 0 <= ny <= w-1:
            if ma[nx][ny] == ".":
                q.append((nx,ny))
                ans[nx][ny] = ans[x][y] + 1
                ma[nx][ny] == "#"
        if nx == h-1 and ny == w-1:
            break

if ans[h-1][w-1] == -1:
    print(-1)
else:
    print(h*w - cou - ans[h-1][w-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int,input().split())
cou = 0
ma = []
for i in range(h):
    kar = list(input())
    cou += kar.count("#")
    ma.append(kar)


ans = [[-1 for i in range(w)] for j in range(h)]
ans[0][0] = 1
q = deque([(0,0)])
xy = [(1,0),(-1,0),(0,1),(0,-1)]

while q:
    x , y = q.popleft()
    ma[x][y] = "#"
    for i in range(4):
        nx = x + xy[i][0]
        ny = y + xy[i][1]
        if 0 <= nx <= h-1 and 0 <= ny <= w-1:
            if ma[nx][ny] == ".":
                q.append((nx,ny))
                ans[nx][ny] = ans[x][y] + 1
        if nx == h-1 and ny == w-1:
            break

if ans[h-1][w-1] == -1:
    print(-1)
else:
    print(h*w - cou - ans[h-1][w-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int,input().split())
ma = [["#"]*(w+2)]
cou = 0
for i in range(h):
    kar = ["#"]
    kar.extend(list(input()))
    cou += kar.count("#") - 1
    kar.append("#")
    ma.append(kar)
ma.append(["#"]*(w+2))

ans = [[-1 for i in range(w+2)] for j in range(h+2)]
ans[1][1] = 1
q = deque([(1,1)])
xy = [(1,0),(-1,0),(0,1),(0,-1)]

while q:
    x , y = q.popleft()
    ma[x][y] = "#"
    for i in range(4):
        nx = x + xy[i][0]
        ny = y + xy[i][1]
        if ma[nx][ny] == ".":
            q.append((nx,ny))
            ans[nx][ny] = ans[x][y] + 1
        if nx == h and ny == w:
            break

if ans[h][w] == -1:
    print(-1)
else:
    print(h*w - cou - ans[h][w])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int,input().split())
ma = [["#"]*(w+2)]
cou = 0
for i in range(h):
    kar = ["#"]
    kar.extend(list(input()))
    cou += kar.count(".")
    kar.append("#")
    ma.append(kar)
ma.append(["#"]*(w+2))

ans = [[-1 for i in range(w+2)] for j in range(h+2)]
ans[1][1] = 1
q = deque([(1,1)])
xy = [(1,0),(-1,0),(0,1),(0,-1)]

while q:
    x , y = q.popleft()
    ma[x][y] = "#"
    for i in range(4):
        nx = x + xy[i][0]
        ny = y + xy[i][1]
        if ma[nx][ny] == ".":
            q.append((nx,ny))
            ans[nx][ny] = ans[x][y] + 1
        if nx == h and ny == w:
            break

if ans[h][w] == -1:
    print(-1)
else:
    print(cou - ans[h][w])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int,input().split())
ma = [["#"]*(w+2)]
cou = 0
for i in range(h):
    kar = ["#"]
    kar.extend(list(input()))
    cou += kar.count(".")
    kar.append("#")
    ma.append(kar)
ma.append(["#"]*(w+2))

ans = [[-1 for i in range(w+2)] for j in range(h+2)]
ans[1][1] = 1
q = deque([(1,1)])

while q:
    x , y = q.popleft()
    ma[x][y] = "#"
    if ma[x-1][y] == ".":
        q.append((x-1,y))
        ans[x-1][y] = ans[x][y] + 1
    if ma[x+1][y] == ".":
        q.append((x+1,y))
        ans[x+1][y] = ans[x][y] + 1        
    if ma[x][y-1] == ".":
        q.append((x,y-1))
        ans[x][y-1] = ans[x][y] + 1        
    if ma[x][y+1] == ".":
        q.append((x,y+1))
        ans[x][y+1] = ans[x][y] + 1

if ans[h][w] == -1:
    print(-1)
else:
    print(cou - ans[h][w])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h , w = map(int,input().split())
ma = [["#"]*(w+2)]
cou = 0
for i in range(h):
    kar = ["#"]
    kar.extend(list(input()))
    cou += kar.count(".")
    kar.append("#")
    ma.append(kar)
ma.append(["#"]*(w+2))

ans = [[-1 for i in range(w+2)] for j in range(h+2)]
ans[1][1] = 1
q = deque([(1,1)])

while q:
    x , y = q.popleft()
    ma[x][y] = "#"
    if ma[x-1][y] == ".":
        q.append((x-1,y))
        ans[x-1][y] = ans[x][y] + 1
    if ma[x+1][y] == ".":
        q.append((x+1,y))
        ans[x+1][y] = ans[x][y] + 1        
    if ma[x][y-1] == ".":
        q.append((x,y-1))
        ans[x][y-1] = ans[x][y] + 1        
    if ma[x][y+1] == ".":
        q.append((x,y+1))
        ans[x][y+1] = ans[x][y] + 1

if ans[h][w] == -1:
    print(-1)
else:
    print(cou - ans[h][w])

Submission status: Time Limit Exceeded

Solution code:
import sys
h,w=map(int,input().split())
cmap=[input() for _ in range(h)]

whitesum=0
for each in cmap:
    whitesum += each.count(".")

def nextpoint(y,x):
    global cmap
    tmp=[]
    returnlist=[]
    cmap[y]=cmap[y][:x] + "#" + cmap[y][x+1:]

    if y == 0:
        tmp.append([y+1,x])
    elif y == h-1:
        tmp.append([y-1,x])
    else:
        tmp.extend([[y-1,x],[y+1,x]])

    if x == 0:
        tmp.append([y,x+1])
    elif x == w-1:
        tmp.append([y,x-1])
    else:
        tmp.extend([[y,x+1],[y,x-1]])

    for l in tmp:
        if cmap[l[0]][l[1]] == ".":
            returnlist.append(l)

    return returnlist

start=[0,0]
seen=[start]
todo=[]
todo.extend(nextpoint(start[0],start[1]))

i=2
finishflag=True

while finishflag:
    nextlist=[]

    for nep in todo:
        if nep == [h-1,w-1]:
            print(whitesum-i)
            sys.exit()
        else:
            nextlist.extend(nextpoint(nep[0],nep[1]))
    todo=[]
    todo.extend(nextlist)

    if todo == []:
        finishflag = False

    i += 1

print("-1")

Submission status: Time Limit Exceeded

Solution code:
import sys
h,w=map(int,input().split())
cmap=[input() for _ in range(h)]

whitesum=0
for each in cmap:
    whitesum += each.count(".")

def nextpoint(y,x):
    global cmap
    tmp=[]
    returnlist=[]
    cmap[y]=cmap[y][:x] + "#" + cmap[y][x+1:]

    if y == 0:
        tmp.append([y+1,x])
    elif y == h-1:
        tmp.append([y-1,x])
    else:
        tmp.extend([[y-1,x],[y+1,x]])

    if x == 0:
        tmp.append([y,x+1])
    elif x == w-1:
        tmp.append([y,x-1])
    else:
        tmp.extend([[y,x+1],[y,x-1]])

    for l in tmp:
        if cmap[l[0]][l[1]] == ".":
            returnlist.append(l)

    return returnlist

start=[0,0]
seen=[start]
todo=[]
todo.extend(nextpoint(start[0],start[1]))

i=2

while todo != []:
    nextlist=[]

    for nep in todo:
        if nep == [h-1,w-1]:
            print(whitesum-i)
            sys.exit()
        else:
            nextlist.extend(nextpoint(nep[0],nep[1]))
    todo=[]
    todo.extend(nextlist)

    i += 1

print("-1")

Submission status: Time Limit Exceeded

Solution code:
import sys
h,w=map(int,input().split())
cmap=[input() for _ in range(h)]

whitesum=0
for each in cmap:
    whitesum += each.count(".")

def nextpoint(y,x):
    global cmap
    tmp=[]
    returnlist=[]
    cmap[y]=cmap[y][:x] + "#" + cmap[y][x+1:]

    if y == 0:
        tmp.append([y+1,x])
    elif y == h-1:
        tmp.append([y-1,x])
    else:
        tmp.extend([[y-1,x],[y+1,x]])

    if x == 0:
        tmp.append([y,x+1])
    elif x == w-1:
        tmp.append([y,x-1])
    else:
        tmp.extend([[y,x+1],[y,x-1]])

    for l in tmp:
        if cmap[l[0]][l[1]] == ".":
            returnlist.append(l)

    return returnlist

start=[0,0]
seen=[start]
todo=[]
todo.extend(nextpoint(start[0],start[1]))

i=2

while todo != []:
    nextlist=[]

    for nep in todo:
        if nep == [h-1,w-1]:
            print(whitesum-i)
            sys.exit()
        else:
            nextlist.extend(nextpoint(nep[0],nep[1]))
    todo=[]
    for rep in nextlist:
        todo.append(rep)

    i += 1

print("-1")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = H * W - cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

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


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

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

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

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


print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
s = [input() for i in range(h)]
q = [(0, 0)]
g = (h - 1, w - 1)
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
inf = float('inf')
dist = [[inf] * w for _ in range(h)]
dist[0][0] = 0
cnt = 0
while 1:
    qq = []
    cnt += 1
    for y, x in q:
        for dy, dx in test:
            yy, xx = y + dy, x + dx
            if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1:
                continue
            if s[yy][xx] == '#' or dist[yy][xx] != inf:
                continue
            dist[yy][xx] = cnt
            qq.append((yy, xx))
    q = qq
    if g in q:
        break
    if q:
        continue
    else:
        print(-1)
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            cnt += 1
print(h * w - cnt - 1)

Submission status: Time Limit Exceeded

Solution code:
H,W = [int(i) for i in input().split(' ')]

MAP = []
SUM = 0 
for i in range(H):
    tmp = list(input())
    SUM += tmp.count('#')
    MAP.append(tmp)

# print(MAP,SUM)

S = [[0,0]]

while True:
    tmp = []
    for s in S:
        if not s[1] == W -1:
            if MAP[s[0]][s[1]+1] == '.':
                a = [s[0], s[1]+1]
                tmp.append(a)
        
        if not s[0] == H -1:
            if MAP[s[0]+1][s[1]] == '.':
                a = [s[0]+1, s[1]]
                tmp.append(a)
    S = tmp
    if len(s) == 0:
        print(-1)
        exit()

    if [H-1,W-1] in S:
        move = H + W - 1
        print(H*W - move - SUM)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import numpy as np

sys.setrecursionlimit(10**9)

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

# 最短距離で行って通ったところ以外を黒マスにする
# . : 0, # : 1
S = np.zeros((H + 2, W + 2), dtype='int')
S[0, :] = 1
S[-1, :] = 1
S[:, 0] = 1
S[:, -1] = 1

cost = np.zeros((H + 2, W + 2), dtype='int')
cost[:, :] = -1

subset = S[1:-1, 1:-1]
for h in range(H):
    s = list(input())
    subset[h:] = np.array([0 if i == '.' else 1 for i in s], dtype='i')

q = deque()
qq = deque()
q.append((1, 1))

i = 0
while len(q) > 0:
    while len(q) > 0:
        x, y = q.popleft()
        cost[x, y] = i
        if x == H and y == W:
            break
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx = x + dx
            ny = y + dy
            if S[nx, ny] == 0 and cost[nx, ny] == -1:
                qq.append((nx, ny))
    q = qq
    qq = deque()
    i += 1

if cost[H, W] == -1:
    print(-1)
    exit()

ans = (H + 2) * (W + 2) - (S == 1).sum() - cost[H, W] - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import numpy as np

sys.setrecursionlimit(10**9)

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

# 最短距離で行って通ったところ以外を黒マスにする
# . : 0, # : 1
S = np.zeros((H + 2, W + 2), dtype='int')
S[0, :] = 1
S[-1, :] = 1
S[:, 0] = 1
S[:, -1] = 1

cost = np.zeros((H + 2, W + 2), dtype='int')
cost[:, :] = -1

subset = S[1:-1, 1:-1]
for h in range(H):
    s = list(input())
    subset[h:] = np.array([0 if i == '.' else 1 for i in s], dtype='i')

q = deque()
qq = deque()
q.append((1, 1))

i = 0
while len(q) > 0:
    while len(q) > 0:
        x, y = q.popleft()
        cost[x, y] = i
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx = x + dx
            ny = y + dy
            if S[nx, ny] == 0 and cost[nx, ny] == -1:
                qq.append((nx, ny))
    q = qq
    qq = deque()
    i += 1

if cost[H, W] == -1:
    print(-1)
    exit()

ans = (H + 2) * (W + 2) - (S == 1).sum() - cost[H, W] - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
maze=[["#" for i in range(2+w)]]
for _ in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    maze.append(x)
    
maze.append(["#" for i in range(2+w)])

#maze[i][j]=(i,j)番目の様子がどうなっているか。"#"の時地雷、"."の時oke

from collections import deque

d=deque()
d.append((1,1))





visited=[[False for i in range(w+2)] for j in range(h+2)]

dis=0
visited[1][1]=True

while visited[h][w]==False:
    e=deque()
    dis+=1
    while d:
    	x=d.popleft()
    	X,Y=x[0],x[1]
    	if visited[X-1][Y]==False and maze[X-1][Y]==".":
        	visited[X-1][Y]=True
        	e.append((X-1,Y))
    	if visited[X+1][Y]==False and maze[X+1][Y]==".":
        	visited[X+1][Y]=True
        	e.append((X+1,Y))
    	if visited[X][Y-1]==False and maze[X][Y-1]==".":
        	visited[X][Y-1]=True
        	e.append((X,Y-1))
    	if visited[X][Y+1]==False and maze[X][Y+1]==".":
        	visited[X][Y+1]=True
        	e.append((X,Y+1))
    if e:
      d=e
      e=deque()

    
dis=dis+1

cnt=0

#全体の白い領域を見る
for i in range(h+2):
    for j in range(2+w):
        if maze[i][j]==".":
            cnt+=1
        
        
print(cnt-dis)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
maze=[["#" for i in range(2+w)]]
for _ in range(h):
    x=list(input())
    x.insert(0,"#")
    x.append("#")
    maze.append(x)
    
maze.append(["#" for i in range(2+w)])

#maze[i][j]=(i,j)番目の様子がどうなっているか。"#"の時地雷、"."の時oke

from collections import deque

d=deque()
d.append((1,1))





visited=[[False for i in range(w+2)] for j in range(h+2)]

dis=0
visited[1][1]=True

while visited[h][w]==False:
    e=deque()
    dis+=1
    while d:

    	x=d.popleft()

    
    
    	X,Y=x[0],x[1]
    	if visited[X-1][Y]==False and maze[X-1][Y]==".":
        	visited[X-1][Y]=True
        	e.append((X-1,Y))
    	if visited[X+1][Y]==False and maze[X+1][Y]==".":
        	visited[X+1][Y]=True
        	e.append((X+1,Y))
    	if visited[X][Y-1]==False and maze[X][Y-1]==".":
        	visited[X][Y-1]=True
        	e.append((X,Y-1))
    	if visited[X][Y+1]==False and maze[X][Y+1]==".":
        	visited[X][Y+1]=True
        	e.append((X,Y+1))
    if e:
      d=e
      e=deque()

    
dis=dis+1




cnt=0

#全体の白い領域を見る
for i in range(h+2):
    for j in range(2+w):
        if maze[i][j]==".":
            cnt+=1
        
        
print(cnt-dis)

Submission status: Time Limit Exceeded

Solution code:
import sys
#大きすぎるとダメ
sys.setrecursionlimit(2504)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
#大きすぎるとダメ
sys.setrecursionlimit(2503)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
#大きすぎるとダメ
h,w=map(int,input().split())
sys.setrecursionlimit(h*w+10)
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
#大きすぎるとダメ
sys.setrecursionlimit(2505)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
#大きすぎるとダメ
sys.setrecursionlimit(2510)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
#大きすぎるとダメ
sys.setrecursionlimit(2520)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
#大きすぎるとダメ
sys.setrecursionlimit(2530)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
#大きすぎるとダメ
sys.setrecursionlimit(2550)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)