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 queue

H, W = list(map(int, input().split()))
ans = H * W
L = []
for i in range(H):
	s = list(input())
	ans -= s.count("#")
	L.append(s)

length = [[float("inf") for i in range(W)] for j in range(H)]
length[0][0] = 0

def breadth(H, W, q, L, length, goal):
	while True:
		m = q.get()
		x = m[0]
		y = m[1]
		if [x, y] == goal:
			break

		if y - 1 >= 0:
			if length[y - 1][x] > length[y][x] + 1:
				if L[y - 1][x] == ".":
					length[y - 1][x] = length[y][x] + 1
					q.put([x, y - 1])
		if y + 1 <= H - 1:
			if length[y + 1][x] > length[y][x] + 1:
				if L[y + 1][x] == ".":
					length[y + 1][x] = length[y][x] + 1
					q.put([x, y + 1])
		if x - 1 >= 0:
			if length[y][x - 1] > length[y][x] + 1:
				if L[y][x - 1] == ".":
					length[y][x - 1] = length[y][x] + 1
					q.put([x - 1, y])
		if x + 1 <= W - 1:
			if length[y][x + 1] > length[y][x] + 1:
				if L[y][x + 1] == ".":
					length[y][x + 1] = length[y][x] + 1
					q.put([x + 1, y])
	return length[-1][-1]

q = queue.Queue()
q.put([0, 0])
goal = [W - 1, H - 1]
goal_len = breadth(H, W, q, L, length, goal)

if length[H - 1][W - 1] == float("inf"):
	print(-1)
else:
	print(ans - goal_len - 1)

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
Sn = [["#" for j in range(W+2)] for i in range(H+2)]
num_w = 0
for i in range(H):
  h = list(str(sys.stdin.readline().rstrip()))
  Sn[i+1] = ["#"] + h + ["#"]
  num_w += h.count(".")

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
while(Cn[H][W] == sys.maxsize):
  for i in range(H):
    for j in range(W):
      if Sn[i+1][j+1] == "#":
        continue
      else:
        Cn[i+1][j+1] = min(Cn[i+1][j+1],Cn[i+2][j+1]+1,Cn[i+1][j+2]+1,Cn[i][j+1]+1,Cn[i+1][j]+1)

  for j in range(W,-1,-1):
    for i in range(H,-1,-1):
      if Sn[i+1][j+1] == "#":
        continue
      else:
        Cn[i+1][j+1] = min(Cn[i+1][j+1],Cn[i+2][j+1]+1,Cn[i+1][j+2]+1,Cn[i][j+1]+1,Cn[i+1][j]+1)


print(num_w - Cn[H][W] - 1)

Submission status: Time Limit Exceeded

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


H,W = map(int, input().split())
Sn = [["#" for j in range(W+2)] for i in range(H+2)]
num_w = 0
for i in range(H):
  h = list(str(input()))
  Sn[i+1] = ["#"] + h + ["#"]
  num_w += h.count(".")

Cn = [[sys.maxsize for j in range(W+2)] for i in range(H+2)]
Cn[1][1] = 0
while(Cn[H][W] == sys.maxsize):
  for i in range(H):
    for j in range(W):
      if Sn[i+1][j+1] == "#":
        continue
      else:
        Cn[i+1][j+1] = min(Cn[i+1][j+1],Cn[i+2][j+1]+1,Cn[i+1][j+2]+1,Cn[i][j+1]+1,Cn[i+1][j]+1)

print(num_w - Cn[H][W] - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
s=[["#"]*(w+2)]+[["#"]+list(input())+["#"]for i in range(h)]+[["#"]*(w+2)]
p=[[1,1]]
d=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]==".":
            d+=1
s[1][1]="#"
k=0
while [h,w] not in p:
    k+=1
    g=[]
    for i in range(len(p)):
        x,y=p[i][0],p[i][1]
        if s[x-1][y]==".":
            s[x-1][y]="Q"
            g.append([x-1,y])
        if s[x+1][y]==".":
            s[x+1][y]="Q"
            g.append([x+1,y])
        if s[x][y+1]==".":
            s[x][y+1]="Q"
            g.append([x,y+1])
        if s[x][y-1]==".":
            s[x][y-1]="Q"
            g.append([x,y-1])
    else:
        p=g
print(d-k-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

H, W = map(int, input().split())
##計算の都合、 通路(.)を正の整数、壁(#)を-1に変換する
Mij = [[0] * W for _ in range(H)]
space_count = 0
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == ".":
            space_count += 1
            Mij[i][j] = 100000
        else:
            Mij[i][j] = -1

dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]

def search(i, j, step):
    if i == H - 1 and j == W - 1:
        return step

    best = None
    for d in dirs:
        i2 = i + d[0]
        j2 = j + d[1]
        if 0 <= i2 < H and 0 <= j2 < W:
            if step + 1 < Mij[i2][j2]:
                Mij[i2][j2] = step
                r = search(i2, j2, step + 1)
                if not r:
                    continue
                if not best or best > r:
                    best = r
    return best

total_steps = search(0, 0, 1)
if total_steps is None:
    print(-1)
else:
    print(space_count - total_steps)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt_wall = 0
for y in range(H):
    for x in range(W):
        if maze[y][x]=="#":
            cnt_wall += 1
            
q = deque([(0,0,1)]) # y,x,step
visited = [[False]*W for _ in range(H)]
visited[0][0] = True

while q:
    y,x,step = q.popleft()
    #print(y,x,step)
    if (y,x)==(H-1,W-1):
        print(H*W - cnt_wall - step)
        break
    visited[y][x] = True
    for dy,dx in zip([0,0,1,-1], [1,-1,0,0]):
        if not(0<=y+dy<H and 0<=x+dx<W):
            continue
        if visited[y+dy][x+dx] or maze[y+dy][x+dx]=="#":
            continue
        q.append((y+dy, x+dx, step+1))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

nesw = [[0, 1], [0, -1], [1, 0], [-1, 0]]
height, width = map(int, input().split(" "))
root = []
black = 0
for i in range(height):
    temp = [n for n in input()]
    root.append(temp)
    black += temp.count("#")
start_y, start_x = 0, 0
end_y, end_x = height - 1, width - 1

queue = [(start_y, start_x)]
used_white = 1
flag = 0
while True:
    new_queue = []
    used_white += 1
    for q in queue:
        h, w = q
        for t in nesw:
            new_h, new_w = h + t[0], w + t[1]
            if 0 <= new_h < height and 0 <= new_w < width:
                if new_h == end_y and new_w == end_x:
                    flag = 1
                    break
                elif root[new_h][new_w] != "#":
                    root[new_h][new_w] = "#"
                    new_queue.append((new_h, new_w))
    if flag:
        break
    queue = new_queue

print(height * width - black - used_white)

Submission status: Time Limit Exceeded

Solution code:
import sys

def wfs(queue, S, step, goal):
    next_queue = []
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.append([i+1, j])
        if S[i-1][j] == '.':
            next_queue.append([i-1, j])
        if S[i][j+1] == '.':
            next_queue.append([i, j+1])
        if S[i][j-1] == '.':
            next_queue.append([i, j-1])

    if len(next_queue) == 0:
        return -1
    else:
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    init = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        init += sum([c == '#' for c in s])
        S.append(['#'] + s + ['#'])
    S = [['#'] * (W+2)] + S + [['#'] * (W+2)]
    minstep = wfs([[1,1]], S, 0, [H, W])
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - init)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def wfs(queue, S, step, goal):
    next_queue = []
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.append([i+1, j])
        if S[i-1][j] == '.':
            next_queue.append([i-1, j])
        if S[i][j+1] == '.':
            next_queue.append([i, j+1])
        if S[i][j-1] == '.':
            next_queue.append([i, j-1])

    if len(next_queue) == 0:
        return -1
    else:
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    init = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        init += s.count('#')
        S.append(['#'] + s + ['#'])
    S = [['#'] * (W+2)] + S + [['#'] * (W+2)]
    minstep = wfs([[1,1]], S, 0, [H, W])
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - init)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    q = deque()
    q.append((0, 0, 1))
    sp = -1
    while len(q):
        i, j, path = q.popleft()
        if i == H-1 and j == W-1:
            sp = path
            break
        if S[i][j] != '.' and S[i][j] < path:
            continue
        S[i][j] = path
        for d in dirs:
            ni, nj = i+d[0], j+d[1]
            if ni >= 0 and nj >= 0 and ni < H and nj < W and S[ni][nj] != '#':
                if S[ni][nj] == '.' or path+1 < S[ni][nj]:
                    q.append((ni, nj, path+1))
    if sp == -1:
        print(sp)
    else:
        ans = 0
        for i in range(H):
            for j in range(W):
                if S[i][j] != '#':
                    ans += 1
        print(ans - sp)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    q = deque()
    q.append((0, 0, 1))
    sp = -1
    while len(q):
        i, j, path = q.popleft()
        if i == H-1 and j == W-1:
            sp = path
            break
        if S[i][j] != '.' and S[i][j] < path:
            continue
        S[i][j] = path
        for d in dirs:
            ni, nj = i+d[0], j+d[1]
            if ni >= 0 and nj >= 0 and ni < H and nj < W and S[ni][nj] != '#':
                q.append((ni, nj, path+1))
    if sp == -1:
        print(sp)
    else:
        ans = 0
        for i in range(H):
            for j in range(W):
                if S[i][j] != '#':
                    ans += 1
        print(ans - sp)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int,input().split())
_input = []
for i in range(H):
    row = list(map(str,input().split()))
    _input.append(list(row[0]))

sy,sx = 0,0
gy,gx = H-1,W-1

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

dyx=((1,0),(-1,0),(0,1),(0,-1))

counted_map = [[-1]*W for _ in range(H)]
counted_map[sy][sx] = 0

reach = False

while queue:
    y,x = queue.popleft()

    if (y,x) == (gy,gx):
        reach = True
        break

    for dy,dx in dyx:
        ny = y + dy
        nx = x + dx

        if ny < 0 or nx < 0 or ny >= H or nx >= W:
            continue

        # 空きマスかつ未訪問
        if _input[ny][nx] == '.' and counted_map[ny][nx] == -1:
            counted_map[ny][nx] = counted_map[y][x] + 1
            queue.append((ny,nx))

if not reach:
    print(-1)
    exit()

y,x = gy,gx
move_num = counted_map[gy][gx]
while move_num != 0:
    _input[y][x] = 'o'
    for dy,dx in dyx:
        ny = y + dy
        nx = x + dx

        if ny < 0 or nx < 0 or ny >= H or nx >= W:
            continue
        
        if _input[ny][nx] == '.':
            tmp_dist = counted_map[ny][nx]
            if tmp_dist < move_num:
                move_num = tmp_dist
                next_y,next_x = ny,nx
    
    y,x = next_y,next_x

_input[sy][sx] = 'o'

res = 0

for raw in _input:
    for i in raw:
        if i == '.':
            res += 1

print(res)

Submission status: Time Limit Exceeded

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

from collections import deque

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

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

F = []
nW = 0
for _ in range(H):
    F.append(list(input()))
    nW += sum([1 for s in F[-1] if s == '.'])

ans = -1
q = deque()
q.append((0, 0, 1))
while q:
    y, x, count = q.popleft()
    F[y][x] = 'V' # Visited
    if y == H - 1 and x == W - 1:
        ans = nW - count
    for n in neig:
        ny, nx = y + n[0], x + n[1]
        if 0 <= ny < H and 0 <= nx < W:
            if F[ny][nx] == '.':
                q.append((ny, nx, count + 1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


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

# search for kuro
kuro = 0
for row in masu:
    for s in row:
        if s == '#':
            kuro += 1


# search for minimum dist by bfs
que = deque([(0, 0, 0)])
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = [[False for _ in range(W)] for _ in range(H)]

# print(len(visited[0]), len(visited))

while (que):
    i, j, cost = que.popleft()
    visited[j][i] = True
    if (j == H - 1) and (i == W - 1):
        break

    for movex, movey in move:
        tmpx, tmpy = i + movex, j + movey
        # visited[tmpy][tmpx] = True

        # if (tmpx < 0) or(tmpx >= W) or (tmpy < 0) or (tmpy >= H):
        if not(tmpx in range(W)) or not(tmpy in range(H)):
            continue

        if (masu[tmpy][tmpx] == '.') and not(visited[tmpy][tmpx]):
            que.append((i + movex, j + movey, cost + 1))
else:
    print(-1)
    exit()
# print(sum(visited[4]))
print(H * W - kuro - cost - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


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

# search for kuro
kuro = 0
for row in masu:
    for s in row:
        if s == '#':
            kuro += 1


# search for minimum dist by bfs
que = deque([(0, 0, 0)])
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = [[False for _ in range(W)] for _ in range(H)]

# print(len(visited[0]), len(visited))

while (que):
    i, j, cost = que.popleft()
    visited[j][i] = True
    if (j == H - 1) and (i == W - 1):
        break

    for movex, movey in move:
        tmpx, tmpy = i + movex, j + movey
        if (tmpx < 0) or(tmpx >= W) or (tmpy < 0) or (tmpy >= H):
            continue

        if (masu[tmpy][tmpx] == '.') and not(visited[tmpy][tmpx]):
            que.append((i + movex, j + movey, cost + 1))
else:
    print(-1)
    exit()

print(H * W - kuro - cost - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())
grid = [[0]*W for _ in range(H)]

cnt = 0
for i in range(H):
    l = input()
    for j in range(W):
        grid[i][j] = l[j]
        if l[j] == '.':
            cnt += 1


# 動的計画法 dp[i][j]->grid[i][j]に行くための最短距離
dp = [[float('inf')]*W for _ in range(H)]


def dfs(i, j, dist):
    if 0 <= i < H and 0 <= j < W:
        if grid[i][j] != '#':
            if dp[i][j] < dist:
                return
            else:
                dp[i][j] = dist

                new_dist = dist+1
                dfs(i+1, j, new_dist)
                dfs(i-1, j, new_dist)
                dfs(i, j+1, new_dist)
                dfs(i, j-1, new_dist)


def solve():
    dfs(0, 0, 1)
    min_dist = dp[H-1][W-1]
    if min_dist == float('inf'):
        return -1
    else:
        return cnt - min_dist


print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())
grid = []

cnt = 0
for _ in range(H):
    l = input()
    cnt += l.count('.')
    grid.append([v for v in l])

# 動的計画法 dp[i][j]->grid[i][j]に行くための最短距離
dp = [[float('inf')]*W for _ in range(H)]


def dfs(i, j, dist):
    if 0 <= i < H and 0 <= j < W:
        if grid[i][j] != '#':
            if dp[i][j] < dist:
                return
            else:
                dp[i][j] = dist

                new_dist = dist+1
                dfs(i+1, j, new_dist)
                dfs(i-1, j, new_dist)
                dfs(i, j+1, new_dist)
                dfs(i, j-1, new_dist)


def solve():
    dfs(0, 0, 1)
    min_dist = dp[H-1][W-1]
    if min_dist == float('inf'):
        return -1
    else:
        return cnt - min_dist


print(solve())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float('inf')

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

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

s = []
total_white_count = 0
for _ in range(H):
    t = tuple(map(lambda x: 1 if x == '.' else 0, list(input())))
    s.append(t)
    total_white_count += sum(t)
p = [[INF for _ in range(W)] for _ in range(H)]

ans = -1

dq = deque()
dq.append((0, 0, 1))
while dq:
    r, c, d = dq.pop()

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float('inf')

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

H, W = map(int, input().split())
s = [input() for _ in range(H)]
p = [[INF for _ in range(W)] for _ in range(H)]

ans = -1

dq = deque()
dq.append((0, 0, 1))
while dq:
    r, c, d = dq.pop()
    if r == H - 1 and c == W - 1:
        ans = sum(s[r].count('.') for r in range(H)) - d
        break

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

flag=False
if S[0][0]=='.' and S[-1][-1]=='.':
    que = path(0,0)
else:
    que = []
f[0][0]=1

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

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

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = [['#' for _ in range(w + 2)]]
s = s + [['#'] + list(input()) + ['#'] for _ in range(h)]
s = s + [['#' for _ in range(w + 2)]]
n_white = 0
for i in range(1, h + 1):
    n_white += s[i].count('.')
q = [[1, 1]]
a = []
d = 1
while(True):
    qq = []
    for i in range(len(q)):
        x = q[i][0]
        y = q[i][1]
        if s[x][y - 1] == '.' and [x, y - 1] not in a:
            qq.append([x, y - 1])
        if s[x - 1][y] == '.' and [x - 1, y] not in a:
            qq.append([x - 1, y])
        if s[x + 1][y] == '.' and [x + 1, y] not in a:
            qq.append([x + 1, y])
        if s[x][y + 1] == '.' and [x, y + 1] not in a:
            qq.append([x, y + 1])
    d += 1
    if [h, w] in qq:
        break
    elif qq == []:
        print(-1)
        exit()
    a = a + qq
    q = qq
print(n_white - d)

Submission status: Time Limit Exceeded

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

black = 0
for g in G:
    black += g.count("#")


que = deque()
que.append([0, 0, 0])
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while que:
    nh, nw, cost = que.pop()
    G[nh][nw] = cost
    if G[H - 1][W - 1] != ".":
        print(H * W - black - int(G[H - 1][W - 1]) - 1)
        break

    for dh, dw in direction:
        if (0 <= nh + dh < H) & (0 <= nw + dw < W):
            if G[nh + dh][nw + dw] == ".":
                que.appendleft((nh + dh, nw + dw, cost + 1))
else:
    print(-1)

Submission status: Time Limit Exceeded

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

black = 0
for g in G:
    black += g.count("#")


que = deque()
que.append([0, 0, 0])
direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while que:
    nh, nw, cost = que.pop()
    G[nh][nw] = cost
    if (nh == H - 1) & (nw == W - 1):
        print(H * W - black - int(G[H - 1][W - 1]) - 1)
        break

    for dh, dw in direction:
        if (0 <= nh + dh < H) & (0 <= nw + dw < W):
            if G[nh + dh][nw + dw] == ".":
                que.appendleft((nh + dh, nw + dw, cost + 1))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def AppendQue(now, depth, que, past_visit, maze):
    Next = ((now[0] - 1, now[1]), (now[0], now[1] - 1),
            (now[0] + 1, now[1]), (now[0], now[1] + 1))
    for h, w in Next:
        if min(h, w) < 0:
            continue
        elif h >= H or w >= W:
            continue
        elif (h, w) in past_visit:
            continue
        elif maze[h][w] == "#":
            continue

        que.append(((h, w), depth + 1))


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

maze = []
black = 0
for i in range(H):
    maze.append(input())
    black += maze[i].count("#")

if maze[0][0] == "#" or maze[H - 1][W - 1] == "#":
    print(-1)
    exit()

que = []
now = (0, 0)
depth = 1
que.append((now, depth))
past_visit = set()
while True:
    if len(que) == 0:
        print(-1)
        exit()
    (now, depth), que = que[0], que[1:]
    if now == (H - 1, W - 1):
        break
    past_visit.add(now)
    AppendQue(now, depth, que, past_visit, maze)

print(H * W - black - depth)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W = inpl()

white = 0
maze = [['#']*(W+2)]
for i in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(['#'] + li + ['#'])
maze.append(['#']*(W+2))

def check(x,y,n):
	if x==W and y==H:
		print(white-n)
		sys.exit()
	elif maze[y][x] == '.':
		q.put([x-1,y,n+1])
		q.put([x+1,y,n+1])
		q.put([x,y-1,n+1])
		q.put([x,y+1,n+1])
	else:
		return

q = queue.Queue()
q.put([1,1,1])
while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W = inpl()

white = 0
MAP = [['#']*(W+2)]
for i in range(H):
	li = list(input())
	white += li.count('.')
	MAP.append(['#'] + li + ['#'])
MAP.append(['#']*(W+2))

memo = [[INF for x in range(W+2)] for y in range(H+2)]

def check(x,y,n):
	if MAP[y][x] == '#':
		return
	elif x==W and y==H:
		print(white-n)
		sys.exit()
	else:
		memo[y][x] = n
		q.put([x-1,y,n+1])
		q.put([x+1,y,n+1])
		q.put([x,y-1,n+1])
		q.put([x,y+1,n+1])
		return



q = queue.Queue()
q.put([1,1,1])
while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W = inpl()

white = 0
MAP = [['#']*(W+2)]
for i in range(H):
	li = list(input())
	white += li.count('.')
	MAP.append(['#'] + li + ['#'])
MAP.append(['#']*(W+2))

memo = [[INF for x in range(W+2)] for y in range(H+2)]
q = queue.Queue()
q.put([1,1,1])

def check(x,y,n):
	if memo[y][x] < n or MAP[y][x] == '#':
		return
	elif x==W and y==H:
		print(white-n)
		sys.exit()
	else:
		memo[y][x] = n
		q.put([x-1,y,n+1])
		q.put([x+1,y,n+1])
		q.put([x,y-1,n+1])
		q.put([x,y+1,n+1])


while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

H,W = inpl()

MAP = [['#']*(W+2)]
for i in range(H):
	MAP.append(['#'] + list(input()) + ['#'])
MAP.append(['#']*(W+2))

memo = [[INF for x in range(W+2)] for y in range(H+2)]
q = queue.Queue()
q.put([1,1,1])

def check(x,y,n):
	if memo[y][x] < n or MAP[y][x] == '#':
		return
	else:
		memo[y][x] = n
		q.put([x-1,y,n+1])
		q.put([x+1,y,n+1])
		q.put([x,y-1,n+1])
		q.put([x,y+1,n+1])


while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

if memo[H][W] == INF:
	print(-1)
else:
	black = 0
	for y in range(1,H+1):
		for x in range(1,W+1):
			if MAP[y][x] == '#':
				black += 1
	print(H*W-black-memo[H][W])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

def bfs():
    dist = [[0 for _ in range(W)] for _ in range(H)]
    routes = deque()
    routes.append((0, 0)) 

    while len(routes) > 0:
        x, y = routes.popleft()
        for move in moves:
            cx, cy = x + move[0], y + move[1]
            if cx < 0 or cy < 0 or cx >= W or cy >= H or c[cy][cx] == '#':
                continue
            if cx == W-1 and cy == H-1: 
                return sum([line.count('.')for line in c]) - dist[y][x] - 2 
            routes.append((cx, cy))
            dist[cy][cx] = dist[y][x] + 1 
    return -1

print(bfs())