python
s = (1, 1)
t = (5, 5)
prev = [[0] * m] * n
dis = [[-1] * m] * n
dis[s[0]][s[1]] = 0
q = [s]
it = 0
dx_ls = [0, 1, 0, -1]
dy_ls = [1, 0, -1, 0]
while it < len(q):
now = q[it]
if now == t:
break
it += 1
for dx, dy in zip(dx_ls, dy_ls):
xx = now[0] + dx
yy = now[1] + dy
if d[xx][yy] is not obstacle and dis[xx][yy] == -1:
dis[xx][yy] = dis[now[0]][now[1]] + 1
prev[xx][yy] = now
q.append((xx, yy))
if dis[t[0]][t[1]] == -1:
print("Dest is not reachable!")
exit(1)
now = t
history = []
while now != s:
history.append(now)
now = prev[now[0]][now[1]]
history.append(s)
history = history[::-1]
print("Step: {}".format(dis[t[0]][t[1]]))
for p in history:
print("({}, {})".format(p[0], p[1]))