BFS to solve shortest path in maze

BFS.py

#!/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