Challenge_3_3.py

'''
Prepare the Bunnies' Escape
===========================

You're awfully close to destroying the LAMBCHOP doomsday device and freeing Commander Lambda's bunny prisoners, but once they're free of the prison blocks, the bunnies are going to need to escape Lambda's space station via the escape pods as quickly as possible. Unfortunately, the halls of the space station are a maze of corridors and dead ends that will be a deathtrap for the escaping bunnies. Fortunately, Commander Lambda has put you in charge of a remodeling project that will give you the opportunity to make things a little easier for the bunnies. Unfortunately (again), you can't just remove all obstacles between the bunnies and the escape pods - at most you can remove one wall per escape pod path, both to maintain structural integrity of the station and to avoid arousing Commander Lambda's suspicions. 

You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left (0,0) and the door into an escape pod is at the bottom right (w-1,h-1). 

Write a function solution(map) that generates the length of the shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed.

Languages
=========

To provide a Python solution, edit solution.py
To provide a Java solution, edit Solution.java

Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.

-- Python cases --
Input:
solution.solution([[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]])
Output:
    7

Input:
solution.solution([[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]])
Output:
    11

-- Java cases --
Input:
Solution.solution({{0, 1, 1, 0}, {0, 0, 0, 1}, {1, 1, 0, 0}, {1, 1, 1, 0}})
Output:
    7

Input:
Solution.solution({{0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 0}, {0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1}, {0, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0}})
Output:
    11

'''

# Solution

def bfs(l):
    target =  len(l)-1
    queue=[]
    st=0
    end=0
    queue.append(0)
    level=[]
    i=0
    while i<len(l):
        level.append(-1)
        i=i+1
    level[0]=1
    while st<=end:
        a = queue[st]
        st = st+1
        j=0
        while j<len(l[a]):
            if level[l[a][j]]!=-1:
                j=j+1
            else:
                level[l[a][j]] = level[a]+1
                queue.append(l[a][j])
                end = end+1
                j=j+1
    if level[target]==-1:
        return (len(l)+100)
    else:
        return level[target]
                
            
            

def finder(map):
    a = len(map)
    b = len(map[0])
    l=[]
    i=0
    while i<a:
        j=0
        while j<b:
            l.append([])
            if map[i][j]==1:
                j=j+1
                continue
            else:
                if i!=0:
                    if map[i-1][j]==0:
                        l[i*b+j].append((i-1)*b+j)
                if i!=a-1:
                    if map[i+1][j]==0:
                        l[i*b+j].append((i+1)*b+j)
                if j!=0:
                    if map[i][j-1]==0:
                        l[i*b+j].append((i*b)+j-1)
                if j!=b-1:
                    if map[i][j+1]==0:
                        l[i*b+j].append(i*b+j+1)
                j=j+1
        i=i+1
    #print(len(l))
    ans = bfs(l)
    return ans
    


def solution(map):
    a = len(map)
    b = len(map[0])
    ans = min(a*b,finder(map))
    i=0
    while i<a:
        j=0
        while j<b:
            if map[i][j]==0:
                j=j+1
                continue
            else:
                map[i][j]=0
                ans = min(ans,finder(map))
                map[i][j]=1
                j=j+1
                if ans==a+b-1:
                    return ans
        i=i+1
        
    return ans
    
    
    
    

## testing
    
    
print(solution([[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]]))
print(solution([[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]))