Overfencing

from collections import deque

def setio(name):
    # Overwrites input/print functions to file io
    global input, print
    fIn = open(f"{name}.in", "r")
    fOut = open(f"{name}.out", "w")
    input = fIn.readline
    print = lambda i: fOut.write(str(i)+"\n")

setio("maze1")

# Load map
w, h = map(int, input().split())
m = [input() for line in range(2*h+1)]

# Get edges
edges = set() # Here, edges means the empty spaces between walls
for i in range(2*h+1):
    for j in range(2*w+1):
        if i % 2 == 0 and j % 2 == 1: # Looking for horizontal edges
            if m[i][j] == " ":
                edges.add((i, j))
        elif i % 2 == 1 and j % 2 == 0: # Looking for vertical edges
            if m[i][j] == " ":
                edges.add((i, j))

# Get exits
exits = []
for i in range(2*h+1):
    if m[i][0] == " ":
        exits.append((i, -1))
    if m[i][2*w] == " ":
        exits.append((i, 2*w + 1))
for j in range(2*w+1):
    if m[0][j] == " ":
        exits.append((-1, j))
    if m[2*h][j] == " ":
        exits.append((2*h + 1, j))

# Run BFS
q = deque([(i, j, 0) for i, j in exits])
visited = set(exits)
res = 0
while q:
    i, j, d = q.popleft()
    res = max(res, d)
    for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):
        if (i+di, j+dj) in edges and (i+di * 2, j+dj * 2) not in visited:
            q.append((i+di*2, j+dj*2, d + 1))
            visited.add((i+di*2, j+dj*2))
print(res)