foobar.py

from collections import deque

inf = float('inf')

def nodes_f(map):
    counter = 2
    nodes = []
    nodesCoords = {}
    start = None
    end = None
    coordsNodes = {}

    for x, row in enumerate(map):
        for y, column in enumerate(row):
            if x == 0 and y == 0:
                start = counter
            
            if x == (len(map) -1) and y == (len(map[x]) -1):
                end = counter

            if column != 1 and column != '*':
                nodes.append(counter)
                nodesCoords[counter] = (x, y)
                coordsNodes[(x, y)] = counter
            else:
                if column == '*':
                    nodes.append('*')
                    nodesCoords['*'] = (x, y)
                    coordsNodes[(x, y)] = '*'
            counter += 1

    return nodes, nodesCoords, start, end, coordsNodes


def neighbours(map, height, width, x, y, coordsNodes, walls):
    for i in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
        nx, ny = x + i[0], y + i[1]
        if 0 <= nx < height and 0 <= ny < width:
            if map[nx][ny] != 1:
                yield (coordsNodes[(nx, ny)], 1)
            else:
                walls.append((nx, ny))

def dijsktra(map, nodes, nodesCoords, height, width, start, end, coordsNodes):
    # distances
    distances = {node: inf for node in nodes}
    distances[start] = 0
    # previous
    previous_nodes = {
        node: inf for node in nodes
    }

    walls = []

    while nodes:
        current_node = min(nodes, key=lambda v: distances[v])

        if distances[current_node] == inf:
            break

        for neighbour, cost in neighbours(map, height, width, nodesCoords[current_node][0], nodesCoords[current_node][1], coordsNodes, walls):
            alternative_route = distances[current_node] + cost

            if alternative_route < distances[neighbour]:
                distances[neighbour] = alternative_route
                previous_nodes[neighbour] = current_node

        nodes.remove(current_node)

    current_node = end
    shortest_path = deque()
    while previous_nodes[current_node] is not inf:
        shortest_path.appendleft(current_node)
        current_node = previous_nodes[current_node]
    if shortest_path:
        shortest_path.appendleft(current_node)

    return len(shortest_path), walls

def try_other_maps(map, walls, height, width, coordsNodes):
    for wall in walls:
        connectionsCount = 0
        for neighbour, _ in neighbours(map, height, width, wall[0], wall[1], coordsNodes, []):
            if neighbour != 1:
                connectionsCount += 1
            
        if connectionsCount > 1:
            map[wall[0]][wall[1]] = '*'
            yield map
            map[wall[0]][wall[1]] = 1

def solution(map):
    height = len(map)
    width = len(map[0])

    nodes, nodesCoords, start, end, coordsNodes = nodes_f(map)
    dijsktraResult, walls = dijsktra(
        map, nodes, nodesCoords, height, width, start, end, coordsNodes)
    
    for anotherMap in try_other_maps(map, walls, height, width, coordsNodes):
        nodes, nodesCoords, _, _, coordsNodes = nodes_f(anotherMap)
        anotherResult, _ = dijsktra(anotherMap, nodes, nodesCoords, height, width, start, end, coordsNodes)
        if dijsktraResult == 0 and anotherResult != 0:
            dijsktraResult = anotherResult
        elif anotherResult == 0 and dijsktraResult != 0:
            continue
        elif dijsktraResult != 0 and anotherResult != 0:
            dijsktraResult = min(dijsktraResult, anotherResult)
        else:
            continue
            
    return dijsktraResult