svineet / BFS.py

Last active July 13, 2014


    
    View BFS.py 
  
  
      BFS.py
    
    
        Raw
      
    
    File suppressed. Click to show.
  
  
            1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            13
            14
            15
            16
            17
            18
            19
            20
            21
            22
            23
            24
            25
            26
            27
            28
            29
            30
            31
            32
            33
            34
            35
            36
            37
            38
            39
            40
            41
            42
          
          
            #!/usr/bin/env python
 
adj = {}
 
m = """012
345
678
"""
 
# Contruct adj list
# Can move 4 directions from each vertex if it is inside grid
for i in xrange(0, 3):
    for j in xrange(0, 3):
        adj[(i, j)] = []
        if i-1>=0: adj[(i, j)].append((i-1, j))
        if i+1<3: adj[(i, j)].append((i+1, j))
        if j-1>=0: adj[(i, j)].append((i, j-1))
        if j+1<3: adj[(i, j)].append((i, j+1))
 
 
frontier = [(0, 0)]
end_pos = (2, 2)  # shortest path endpoint
 
steps = 1
next_ = []
done = False
while frontier is not [] and not done:
    next_ = []
 
    for v in frontier:
        for destination in adj[v]:
            if destination==end_pos:
                ans = steps
                done = True
                break
            next_.append(destination)
        if done: break
 
    frontier = next_
    steps += 1
 
print ans