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,raw_input().split())
 
arr = [raw_input() for i in range(h)]
 
ans = 0 
for i in range(h):
	ans += arr[i].count("#")
 
 
distance = [[float("inf") for i in range(w)] for j in range(h)]
 
distance[0][0] = 0
 
queue = []
queue.append([0,0,0])
 
direct = [[0,-1],[1,0],[0,1],[-1,0]]
 
while len(queue) != 0 :
	
	y,x,cost = queue.pop(0)
	distance[y][x] = cost
	
	for i in range(4):
		dy = y + direct[i][0]
		dx = x + direct[i][1]
 
		if (-1 < dy < h) and (-1 < dx < w) and arr[dy][dx] != '#' and distance[dy][dx] == float("inf"):
			queue.append([dy,dx,cost+1])
 
print h*w - ans -distance[h-1][w-1] -1 if distance[h-1][w-1] != float("inf") else -1

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

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

dcount = -1
for h in range(H):
    for w in range(W):
        if C[h][w] == '.':
            dcount += 1

INF = 10 ** 6
D = [[INF] * W for i in range(H)]
D[0][0] = 0
q = Queue()
q.put((0, 0))

while q.qsize() > 0:
    h, w = q.get()
    if (h, w) == (H-1, W-1):
        break
    C[h][w] = '#'
    for dh, dw in zip((-1, 1, 0, 0), (0, 0, -1, 1)):
        if 0 <= h+dh < H and 0 <= w+dw < W and C[h+dh][w+dw] == '.':
            D[h+dh][w+dw] = D[h][w] + 1
            q.put((h+dh, w+dw))

print(dcount - D[H-1][W-1] if D[H-1][W-1] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:

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

arr = [raw_input() for i in range(h)]

ans = 0 
for i in range(h):
	ans += arr[i].count("#")


distance = [[float("inf") for i in range(w)] for j in range(h)]

distance[0][0] = 0

queue = []
queue.append([0,0,0])

direct = [[0,-1],[1,0],[0,1],[-1,0]]

while len(queue) != 0 :
	
	y,x,cost = queue.pop(0)
	distance[y][x] = cost
	
	for i in range(4):
		dy = y + direct[i][0]
		dx = x + direct[i][1]

		if (-1 < dy < h) and (-1 < dx < w) and arr[dy][dx] != '#' and distance[dy][dx] == float("inf"):
			queue.append([dy,dx,cost+1])

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

Submission status: Time Limit Exceeded

Solution code:

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

arr = [raw_input() for i in range(h)]

ans = 0 
for i in range(h):
	ans += arr[i].count("#")


distance = [[float("inf") for i in range(w)] for j in range(h)]

distance[0][0] = 0

queue = []
queue.append([0,0,0])

direct = [[0,-1],[1,0],[0,1],[-1,0]]

while len(queue) != 0 :
	
	t = queue.pop(0)
	distance[t[0]][t[1]] = t[2]
	
	if t[0] == h-1 and t[1] == w-1:
		print h*w - ans - t[2] -1
		quit()
	
	for i in range(4):
		dy = t[0] + direct[i][0]
		dx = t[1] + direct[i][1]

		if -1 < dy and dy < h and -1 < dx and dx < w and arr[dy][dx] != '#' and distance[dy][dx] > t[2] + 1 :
			queue.append([dy,dx,t[2]+1])

print -1

Submission status: Time Limit Exceeded

Solution code:
import Queue
h,w = map(int,raw_input().split())

arr = [list(raw_input()) for i in range(h)]

ans = 0 
for i in range(h):
	ans += arr[i].count("#")


distance = [[float("inf") for i in range(w)] for j in range(h)]

distance[0][0] = 0

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

direct = [[0,-1],[1,0],[0,1],[-1,0]]

while not queue.empty() :
	
	t = queue.get()
	distance[t[0]][t[1]] = t[2]
	
	if t[0] == h-1 and t[1] == w-1:
		print h*w - ans - t[2] -1
		quit()
	
	for i in range(4):
		dy = t[0] + direct[i][0]
		dx = t[1] + direct[i][1]

		if -1 < dy and dy < h and -1 < dx and dx < w and arr[dy][dx] != '#' and distance[dy][dx] > t[2] + 1 :
			queue.put([dy,dx,t[2]+1])

print -1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

inp = []
for h in range(H):
    inp.append(input())

field = []
field.append(["#" for _ in range(W+2)])
for h in range(H):
    field.append(["#"] + list(inp[h]) + ["#"])    
field.append(["#" for _ in range(W+2)])


def bfs():
    que = deque([])
    next_h = [1,0,-1, 0]
    next_w = [0,1, 0,-1]
    
    que.append([0,1,1])
    
    while len(que) != 0:
        dist,h,w = que.popleft()
        field[h][w] = str(dist)
        
        for i in range(4):
            if field[h+next_h[i]][w+next_w[i]] == ".":
                que.append([dist+1, h+next_h[i], w+next_w[i]])
            
    return field[H][W]
    

points = 0
for field_row in field:
    for point in field_row:
        if point == ".":
            points += 1


min_dist = bfs()

if min_dist == '.':
    print(-1)
else:
    print(points - int(min_dist) - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter
def count(mapper):
    c=0
    for i in range(len(mapper)):
        c+=Counter(mapper[i])['#']
    return c

h,w = map(int,input().split())
map1=[["#" for _ in range(w+2)]]
for i in range(h):
    map1.append(["#"]+list(input())+["#"])
map1.append(["#" for _ in range(w+2)])
dis = float("inf")
q = deque()
q.append([1,1,1])
num_sharp =count(map1)-2*(h+w)-4
map1[1][1]='#'
while len(q)>0:
    a = q.popleft()
    if a[0]==h and a[1]==w:
        dis = a[2]
        break
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
            if map1[a[0]+i[0]][a[1]+i[1]]=='.':
                q.append([a[0]+i[0],a[1]+i[1],a[2]+1])
    map1[a[0]][a[1]]='#'

if dis == float("inf"):
    print(-1)
else:
    print(h*w-num_sharp-dis)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter
def count(mapper):
    c=0
    for i in range(len(mapper)):
        c+=Counter(mapper[i])['#']
    return c

h,w = map(int,input().split())
map1=[["#" for _ in range(w+2)]]
for i in range(h):
    map1.append(["#"]+list(input())+["#"])
map1.append(["#" for _ in range(w+2)])
dis = float("inf")
q = deque()
q.append([1,1,1])
num_sharp =count(map1)-2*(h+w)-4
map1[1][1]='#'
while len(q)>0:
    a = q.popleft()
    if a[0]==h and a[1]==w:
        dis = a[2]
    for i in [[1,0],[-1,0],[0,1],[0,-1]]:
            if map1[a[0]+i[0]][a[1]+i[1]]=='.':
                q.append([a[0]+i[0],a[1]+i[1],a[2]+1])
    map1[a[0]][a[1]]='#'

if dis == float("inf"):
    print(-1)
else:
    print(h*w-num_sharp-dis)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
H,W=map(int,input().split())
S =[]
kuro=0
for i in range(H):
    s = list(input())
    for j in s:
        if j=='#':
            kuro +=1
    S.append(s)

visit=[[False]*W for i in range(H)]
dist=[[]]
kei=deque()
kei.append((0,0,1))
X =[-1,0,1,0]
Y=[0,-1,0,1]
while kei:
    y,x,d=kei.popleft()
    visit[y][x]=True
    if y==H-1 and x==W-1:
        print(H*W-d-kuro)
        sys.exit()
    for i in range(4):
        nx = x +X[i]
        ny = y +Y[i]
        if (0<=nx< W) and (0<=ny<H) and S[ny][nx]=='.':
            if not visit[ny][nx]:
                kei.append((ny,nx,d+1))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[inf] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([inf] * (W + 2))
s.append(["#"] * (W + 2))
D.append([inf] * (W + 2))
visited = [[False] * (W + 2) for i in range(H + 2)]


def BFS():  # 幅優先探索(inf=>キュー=>訪問)
    global D
    D[1][1] = 1
    q = deque()
    q.append((1, 1))
    while len(q) != 0:
        p = q.popleft()
        visited[p[0]][p[1]] = True
        if p == (H, W):  # ゴールを訪問したら全部終わってなくても打ち切る
            return white_num - D[H][W]
        for e in [(p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0], p[1] - 1)]:
            if s[e[0]][e[1]] == "." and not visited[e[0]][e[1]]:
                D[e[0]][e[1]] = D[p[0]][p[1]] + 1
                q.append(e)
    return -1


print(BFS())

# for i in range(1, H + 1):
#    print(" ".join(list(map(str, D[i][1:-1]))))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[inf] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([inf] * (W + 2))
s.append(["#"] * (W + 2))
D.append([inf] * (W + 2))
visited = [[False] * (W + 2) for i in range(H + 2)]


def BFS():  # 幅優先探索(inf=>キュー=>訪問)
    global D
    D[1][1] = 1
    q = deque()
    q.append((1, 1))
    while len(q) != 0:
        p = q.popleft()
        visited[p[0]][p[1]] = True
        if p == (H, W):  # ゴールを訪問したら全部終わってなくても打ち切る
            return D[H][W]
        for e in [(p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0], p[1] - 1)]:
            if s[e[0]][e[1]] == "." and not visited[e[0]][e[1]]:
                D[e[0]][e[1]] = min(D[p[0]][p[1]] + 1, D[e[0]][e[1]])
                q.append(e)
    return D[H][W]


white_min = BFS()

# for i in range(1, H + 1):
#    print(" ".join(list(map(str, D[i][1:-1]))))

if white_min == inf:
    print(-1)
else:
    print(white_num - white_min)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
inf = float("inf")
s = [["#"] * (W + 2)]
D = [[inf] * (W + 2)]
white_num = 0
for i in range(H):
    main = list(input())
    white_num += len([e for e in main if e == "."])
    s.append(["#"] + main + ["#"])
    D.append([inf] * (W + 2))
s.append(["#"] * (W + 2))
D.append([inf] * (W + 2))
visited = [[False] * (W + 2) for i in range(H + 2)]


def BFS():  # 幅優先探索
    global D
    D[1][1] = 0
    q = deque()
    q.append((1, 1))
    while len(q) != 0:
        p = q.popleft()
        visited[p[0]][p[1]] = True
        for e in [(p[0] + 1, p[1]), (p[0], p[1] + 1), (p[0] - 1, p[1]), (p[0], p[1] - 1)]:
            if s[e[0]][e[1]] == "." and not visited[e[0]][e[1]]:
                D[e[0]][e[1]] = min(D[p[0]][p[1]] + 1, D[e[0]][e[1]])
                q.append(e)
    return D[H][W]


white_min = BFS() + 1

# for i in range(1, H + 1):
#    print(" ".join(list(map(str, D[i][1:-1]))))

if white_min == inf:
    print(-1)
else:
    print(white_num - white_min)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
counter = 0
space = [[-1 for i in range(w+2)]]
for i in range(1,h+1):
    r = input()
    s = list("#"+r+"#")
    counter += r.count("#")
    space.append([])
    for j,moji in enumerate(s):
        if moji == ".":
            space[i].append(0)
        elif moji =="#":
            space[i].append(-1)
space.append([-1 for i in range(w+2)])

sx,sy = 1,1
ex,ey = h,w

watch_space = [[sx,sy]]
decided_space = [[sx,sy]]

while(True):
    tmp = list()
    for [i,j] in watch_space:
        if [i-1,j] not in decided_space and space[i-1][j] == 0:
            space[i-1][j] = space[i][j]+ 1
            decided_space.append([i-1,j])
            tmp.append([i-1,j])
        if [i+1,j] not in decided_space and space[i+1][j] == 0:
            space[i+1][j] = space[i][j]+ 1
            decided_space.append([i+1,j])
            tmp.append([i+1,j])
        if [i,j+1] not in decided_space and space[i][j+1] == 0:
            space[i][j+1] = space[i][j]+ 1
            decided_space.append([i,j+1])
            tmp.append([i,j+1])
        if [i,j-1] not in decided_space and space[i][j-1] == 0:
            space[i][j-1] = space[i][j]+ 1
            decided_space.append([i,j-1])
            tmp.append([i,j-1])
    watch_space = tmp
    if [ex,ey] in decided_space:
        break

ans = (w*h)-(space[ex][ey]+1) - counter
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
s = [list(input()) for i in range(H)]
num_of_point = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            num_of_point += 1
 
counter = 0
position = [[0,0]]
while True:
    counter += 1
    new_position =[]
    for i,j in position:
        for i_,j_ in [[-1,0],[1,0],[0,1],[0,-1]]:
            i_new = i+i_
            j_new = j+j_
            if i_new >=0 and i_new <= H-1 and j_new >= 0 and j_new <= W-1:
                if s[i_new][j_new] == '.':
                    new_position.append([i_new,j_new])
                    s[i_new][j_new] = counter
    if [H-1,W-1] in new_position:
        break
    position = new_position
 
print(num_of_point-counter-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
s = [list(input()) for i in range(H)]
num_of_point = 0
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            num_of_point += 1

counter = 0
position = [[0,0]]
while True:
    counter += 1
    new_position =[]
    for i,j in position:
        for i_,j_ in [[-1,0],[0,1],[0,1],[1,0]]:
            i_new = i+i_
            j_new = j+j_
            if i_new >=0 and i_new <= H-1 and j_new >= 0 and j_new <= W-1:
                if s[i_new][j_new] == '.':
                    new_position.append([i_new,j_new])
                    s[i_new][j_new] = counter
    if [H-1,W-1] in new_position:
        break
    position = new_position

print(num_of_point-counter-1)

Submission status: Time Limit Exceeded

Solution code:
h,w = [int(i) for i in input().split()]
ss = ['!' for i in range(w + 2)]
s = [ss]

for i in range(h):
    s.append(['!'] + [j for j in input()] + ['!'])
    
s.append(ss)
    
minroot = []
q = [[[1,1]]]
dx,dy=[1,0,-1,0],[0,1,0,-1]


while len(q) > 0:
    path = q.pop(0)
    p = path[len(path) - 1]
    if p == [h,w]:
        minroot = path
        break
    else:
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if s[nx][ny] == '.' and [nx,ny] not in path:
                 new_path = path[:]
                 new_path.append([nx,ny])
                 q.append(new_path)
        

if minroot == []:
    print(-1)
else:
    whitecount = 0
    for i in range(1,h + 1):
        whitecount += s[i].count('.')
    
    print(whitecount - len(minroot))

Submission status: Time Limit Exceeded

Solution code:
h,w = [int(i) for i in input().split()]
s = []
s.append(['!' for i in range(w + 2)])

for i in range(h):
    s.append(['!'] + [j for j in input()] + ['!'])
    
s.append(['!' for i in range(w + 2)])
    
minroot = []
q = [[[1,1]]]
dx,dy=[1,0,-1,0],[0,1,0,-1]


while len(q) > 0:
    path = q.pop(0)
    p = path[len(path) - 1]
    if p == [h,w]:
        minroot = path
        break
    else:
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if s[nx][ny] == '.' and [nx,ny] not in path:
                 new_path = path[:]
                 new_path.append([nx,ny])
                 q.append(new_path)
        

if minroot == []:
    print(-1)
else:
    whitecount = 0
    for i in range(1,h + 1):
        whitecount += s[i].count('.')
    
    print(whitecount - len(minroot))

Submission status: Time Limit Exceeded

Solution code:
def list_2d(h,w,v):
    return [[ v for i in range(w)] for j in range(h)]
 
whitecount = 0
h,w = [int(i) for i in input().split()]
s = list_2d(h + 2,w + 2,'!')

for i in range(0,h):
    ss = [j for j in input()] 
    for k in range(0,w):
        s[i + 1][k + 1] = ss[k]
        if ss[k] == '.':
            whitecount += 1

minroot = []
q = []
q.append([[1,1]])
dx,dy=[1,0,-1,0],[0,1,0,-1]


while len(q) > 0:
    path = q.pop(0)
    p = path[len(path) - 1]
    if p == [h,w]:
        minroot = path
        break
    else:
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if s[nx][ny] == '.' and [nx,ny] not in path:
                 new_path = path[:]
                 new_path.append([nx,ny])
                 q.append(new_path)
        

if minroot == []:
    print(-1)
else:
    print(whitecount - len(minroot))

Submission status: Time Limit Exceeded

Solution code:
def list_2d(h,w,v):
    return [[ v for i in range(w)] for j in range(h)]
 
whitecount = 0
h,w = [int(i) for i in input().split()]
s = list_2d(h + 2,w + 2,'!')

for i in range(0,h):
    ss = [j for j in input()] 
    for k in range(0,w):
        s[i + 1][k + 1] = ss[k]
        if ss[k] == '.':
            whitecount += 1

minroot = []
q = []
q.append([[1,1]])


while len(q) > 0:
    path = q.pop(0)
    p = path[len(path) - 1]
    if p == [h,w]:
        minroot = path
        break
    else:
        x = p[0]
        y = p[1]
        if s[x + 1][y] == '.' and [x + 1,y] not in path:
             new_path = path[:]
             new_path.append([x + 1,y])
             q.append(new_path)
        if s[x][y + 1] == '.' and [x,y + 1] not in path:
             new_path = path[:]
             new_path.append([x,y + 1])
             q.append(new_path)
        if s[x - 1][y] == '.' and [x - 1,y] not in path:
             new_path = path[:]
             new_path.append([x - 1,y])
             q.append(new_path)
        if s[x][y - 1] == '.' and [x,y - 1] not in path:
             new_path = path[:]
             new_path.append([x,y - 1])
             q.append(new_path)

if minroot == []:
    print(-1)
else:
    print(whitecount - len(minroot))

Submission status: Time Limit Exceeded

Solution code:
def list_1d(d,v):
    return [ v for i in range(d)]
 
def bf_search(start,goal,adjacent):
    q = [[start]]
    while len(q) > 0:
        # dequeue
        path = q.pop(0)
        n = path[len(path) - 1]
        if n == goal:
            return path
            break
        else:
            for x in adjacent[n]:
                if x not in path:
                    new_path = path[:]
                    new_path.append(x)
                    # enqueue
                    q.append(new_path)
    
    return -1
 
 
whitecount = 0
h,w = [int(i) for i in input().split()]
s = list_1d(h,[])
p = []
 
for i in range(0,h):
    ss = [j for j in input()] 
    s[i] = ss
    for k in range(0,w):
        if ss[k] == '.':
            p.append([i,k])
            whitecount += 1
 
a = []
 
for i in range(0,whitecount):
    b = []
    if [p[i][0]+1,p[i][1]] in p:
        b.append(p.index([p[i][0]+1,p[i][1]]))
    if [p[i][0],p[i][1]+1] in p:
        b.append(p.index([p[i][0],p[i][1]+1]))
    if [p[i][0]-1,p[i][1]] in p:
        b.append(p.index([p[i][0]-1,p[i][1]]))
    if [p[i][0],p[i][1]-1] in p:
        b.append(p.index([p[i][0],p[i][1]-1]))
    a.append(b)
 
c = bf_search(0,whitecount-1,a)
 
if c == -1:
    print(-1)
else:
    print(whitecount - len(c))

Submission status: Time Limit Exceeded

Solution code:
def list_1d(d,v):
    return [ v for i in range(d)]

def bf_search(start,goal,adjacent):
    q = [[start]]
    while len(q) > 0:
        # dequeue
        path = q.pop(0)
        n = path[len(path) - 1]
        if n == goal:
            return path
            break
        else:
            for x in adjacent[n]:
                if x not in path:
                    new_path = path[:]
                    new_path.append(x)
                    # enqueue
                    q.append(new_path)
    
    return -1


whitecount = 0
h,w = [int(i) for i in input().split()]
s = list_1d(h,[])
p = []

for i in range(0,h):
    ss = [j for j in input()] 
    s[i] = ss
    for k in range(0,w):
        if ss[k] == '.':
            p.append([i,k])
            whitecount += 1

a = []

for i in range(0,whitecount):
    b = []
    if [p[i][0]+1,p[i][1]] in p:
        b.append(p.index([p[i][0]+1,p[i][1]]))
    if [p[i][0],p[i][1]+1] in p:
        b.append(p.index([p[i][0],p[i][1]+1]))
    if [p[i][0]-1,p[i][1]] in p:
        b.append(p.index([p[i][0]-1,p[i][1]]))
    if [p[i][0],p[i][1]-1] in p:
        b.append(p.index([p[i][0],p[i][1]-1]))
    a.append(b)
 
c = bf_search(0,whitecount-1,a)

if c == -1:
    print(-1)
else:
    print(whitecount - len(c))

Submission status: Time Limit Exceeded

Solution code:
def list_1d(d,v):
    return [ v for i in range(d)]


whitecount = 0
h,w = [int(i) for i in input().split()]
s = list_1d(h,[])

for i in range(0,h):
    ss = [j for j in input()] 
    s[i] = ss
    for k in range(0,w):
        if ss[k] == '.':
            whitecount += 1

a = 0
b = 0
check = 0


while not(a == h - 1 and b == w - 1):
    if a < h - 1 and s[a+1][b] == '.':
        a += 1
    elif b < w - 1 and s[a][b+1] == '.':
        b += 1
    elif a > 0 and s[a-1][b] == '.':
        a -= 1
        check += 1
    elif b > 0 and s[a][b-1] == '.':
        b -= 1
        check += 1
    else:
        break

if not(a == h - 1 and b == w - 1):
    print(-1)
else:
    print(whitecount-h-w-check+1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
s = [input() for _ in range(H)]
dic = [[1, 0], [0, 1], [-1, 0], [0, -1]]
queue = [[0, 0, 0]]
distances = [[float('inf') for i in range(W)] for j in range(H)]
distances[0][0] = 0
ans = H * W
black = 0
for ss in s:
    black += ss.count('#')
while len(queue) > 0:
    n = queue.pop()
    for d in dic:               
        nx = n[0] + d[0]
        ny = n[1] + d[1]
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue 
        if nx == W-1 and ny == H-1:
            ans = min(distances[n[1]][n[0]] + 1, ans)
        elif s[ny][nx] == "." and distances[ny][nx] > distances[n[1]][n[0]] + 1:
            distances[ny][nx] = distances[n[1]][n[0]] + 1
            queue.append([nx, ny])
print(-1 if ans == H*W else H*W - (ans+1) - black)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())

smap = [list(input()) for _ in range(h)]
cmap = [[float('inf') for _ in range(w)] for _ in range(h)]
queue = [(0,0)]
l = [(1,0), (-1,0), (0,1), (0,-1)]

initial_whites = 0

for x in smap:
    for y in x:
        if y == '.':
            initial_whites += 1

cmap[0][0] = 0

while queue:
    v = queue.pop(0)
    smap[v[0]][v[1]] = '#'
    for x in l:
        y = (v[0]+x[0], v[1]+x[1])
        if 0 <= y[0] <= h-1 and 0 <= y[1] <= w-1:
            if smap[y[0]][y[1]] == '.':
                cmap[y[0]][y[1]] = cmap[v[0]][v[1]] + 1
                queue.append(y)
            else:
                pass
        else:
            pass


if cmap[h-1][w-1] == float('inf'):
    print(-1)
else:
    print(initial_whites - cmap[h-1][w-1] - 1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
maze = []
distances = []
n_aisle = 0
for i in range(H):
    row = input()
    maze.append(row)
    distances.append([100000000 for i in range(W)])
    n_aisle += row.count('.')

distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop()
    for dy, dx in directions:
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if maze[y + dy][x + dx] == '.':
            if distances[y + dy][x + dx] > distances[y][x] + 1:
                distances[y + dy][x + dx] = distances[y][x] + 1
                queue.append((y + dy, x + dx))

if distances[H - 1][W - 1] == 100000000:
    print(-1)
else:
    print(n_aisle - distances[H - 1][W - 1] - 1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
maze = []
distances = []
n_aisle = H * W
for i in range(H):
    row = [c == '#' for c in input()]
    maze.append(row)
    distances.append([100000000 for i in range(W)])
    n_aisle -= sum(row)

distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop()
    for dy, dx in directions:
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if not maze[y + dy][x + dx]:
            if distances[y + dy][x + dx] > distances[y][x] + 1:
                distances[y + dy][x + dx] = distances[y][x] + 1
                queue.append((y + dy, x + dx))

if distances[H - 1][W - 1] == 100000000 or maze[0][0] or maze[H - 1][W - 1]:
    print(-1)
else:
    print(n_aisle - distances[H - 1][W - 1] - 1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
maze = [[c == '#' for c in input()] for _ in range(H)]
distances = [[100000000 for i in range(W)] for j in range(H)]
distances[0][0] = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

queue = [(0, 0)]
while len(queue) > 0:
    y, x = queue.pop()
    for dy, dx in directions:
        if y + dy < 0 or y + dy >= H or x + dx < 0 or x + dx >= W:
            continue
        if not maze[y + dy][x + dx]:
            if distances[y + dy][x + dx] > distances[y][x] + 1:
                distances[y + dy][x + dx] = distances[y][x] + 1
                queue.append((y + dy, x + dx))

if distances[H - 1][W - 1] == 100000000 or maze[0][0] or maze[H - 1][W - 1]:
    print(-1)
else:
    print(H * W - sum([sum(row) for row in maze]) - distances[H - 1][W - 1] - 1)

Submission status: Time Limit Exceeded

Solution code:
import time
from collections import deque
now=time.time()
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    used.add((x,y))
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
    if time.time()-now > 1800:
        print(-1)
        exit()
print(f if f==-1 else(h*w-f-bcount))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    used.add((x,y))
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =0
for i in maplis:
    bcount+=i.count("#")


def check(x,y,c):
    f=(x<0 or x>w-1 or y<0 or y>h-1)
    f=(f or maplis[y][x]=="#")
    f=(f or (x,y) in used)
    if not f:
        que.append((x,y,c+1))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    used.add((x,y))
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([[0,0,1]])
used={(0,0)}
bcount =0
for i in maplis:
    bcount+=i.count("#")


def check(x,y,c):
    f=(x<0 or x>w-1 or y<0 or y>h-1)
    f=(f or maplis[y][x]=="#")
    f=(f or (x,y) in used)
    if not f:
        que.append([x,y,c+1])

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    used.add((x,y))
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=[[0,0,1]]
used={(0,0)}
bcount =0
for i in maplis:
    bcount+=i.count("#")


def check(x,y,c):
    f=(x<0 or x>w-1 or y<0 or y>h-1)
    f=(f or maplis[y][x]=="#")
    f=(f or (x,y) in used)
    if not f:
        que.append([x,y,c+1])

f=-1
while que:
    x,y,c=que.pop(0)
    if x==w-1 and y==h-1:
        f=c
        break
    used.add((x,y))
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=[[0,0,1]]
used=[[0,0]]
bcount =0
for i in maplis:
    bcount+=i.count("#")


def check(x,y,c):
    f=(x<0 or x>w-1 or y<0 or y>h-1)
    f=(f or maplis[y][x]=="#")
    f=(f or [x,y] in used)
    if not f:
        que.append([x,y,c+1])

f=-1
while que:
    x,y,c=que.pop(0)
    if x==w-1 and y==h-1:
        f=c
        break
    used.append([x,y])
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=[[0,0,1]]
used=[[0,0]]
bcount =0
for i in maplis:
    bcount+=i.count("#")


def check(x,y,c):
    f=(x<0 or x>w-1 or y<0 or y>h-1)
    f=(f or maplis[y][x]=="#")
    f=(f or [x,y] in used)
    if not f:
        que.append([x,y,c+1])

f=-1
while que:
    x,y,c=que.pop(0)
    if x==w-1 and y==h-1:
        f=c
    used.append([x,y])
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))