def vaiCavalo( origem, destino ):
   casasTestadas = [[False]*8 for i in range(8)]
   passos = [origem+[0]]
 
   while True:
      proximosPassos = []
      for passo in passos:
         for movimento in [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]:
            x,y = passo[0]+movimento[0], passo[1]+movimento[1]
            if [x,y] == destino:
               return passo[2]+1
            if 0 <= x < 8 and 0 <= y < 8 and not casasTestadas[x][y]:
               proximosPassos.append([x,y,passo[2]+1])
               casasTestadas[x][y] = True
      passos = proximosPassos
 
print("Passos dados: ", vaiCavalo([1,1],[1,2]))
 
 

ZGVmIHZhaUNhdmFsbyggb3JpZ2VtLCBkZXN0aW5vICk6CiAgIGNhc2FzVGVzdGFkYXMgPSBbW0ZhbHNlXSo4IGZvciBpIGluIHJhbmdlKDgpXQogICBwYXNzb3MgPSBbb3JpZ2VtK1swXV0KCiAgIHdoaWxlIFRydWU6CiAgICAgIHByb3hpbW9zUGFzc29zID0gW10KICAgICAgZm9yIHBhc3NvIGluIHBhc3NvczoKICAgICAgICAgZm9yIG1vdmltZW50byBpbiBbWy0xLC0yXSxbLTIsLTFdLFstMiwxXSxbLTEsMl0sWzEsMl0sWzIsMV0sWzIsLTFdLFsxLC0yXV06CiAgICAgICAgICAgIHgseSA9IHBhc3NvWzBdK21vdmltZW50b1swXSwgcGFzc29bMV0rbW92aW1lbnRvWzFdCiAgICAgICAgICAgIGlmIFt4LHldID09IGRlc3Rpbm86CiAgICAgICAgICAgICAgIHJldHVybiBwYXNzb1syXSsxCiAgICAgICAgICAgIGlmIDAgPD0geCA8IDggYW5kIDAgPD0geSA8IDggYW5kIG5vdCBjYXNhc1Rlc3RhZGFzW3hdW3ldOgogICAgICAgICAgICAgICBwcm94aW1vc1Bhc3Nvcy5hcHBlbmQoW3gseSxwYXNzb1syXSsxXSkKICAgICAgICAgICAgICAgY2FzYXNUZXN0YWRhc1t4XVt5XSA9IFRydWUKICAgICAgcGFzc29zID0gcHJveGltb3NQYXNzb3MKCnByaW50KCJQYXNzb3MgZGFkb3M6ICIsIHZhaUNhdmFsbyhbMSwxXSxbMSwyXSkpCiAgIAkJCg==