#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
struct Info {
std::string sfen;
};
struct SearchInfo {
SearchInfo(std::string& S, std::size_t I) :sfen(S), Index(I) {}
std::string sfen="0";
std::size_t Index=0;
};
//typedef std::map<std::string, std::vector<Info>> Tree;
typedef std::vector<std::string> GraphData;
typedef std::map<std::string, GraphData> Graph;
typedef std::vector<SearchInfo> SI;
Graph MakeTree() {
Graph R{ {"0",{"1","3","5"}},{"1",{"0","4","6"}}, {"2",{"4","5","6"}},{"3",{"0","5","7"}}, {"4",{"1","3","7"}},{"5",{"2","0","3"}}, {"6",{"1","2","7"}},{"7",{"6","3","8"}},{"8",{"7"}} };
return R;
}
SI Search(Graph& G, std::string Start, std::string End,std::size_t DepthLim) {
if (DepthLim == 1) return SI();
std::string Now = Start;
std::size_t Si = 1;
SI S{ {Start,0}, };
while (Now != End) {
if (G[Now].size() == S.back().Index) {
S.pop_back();
if (S.size() == 0) return SI();
Now = S.back().sfen;
continue;
}
Now = G[Now][S.back().Index++];
if (S.end() != std::find_if(S.begin(), S.end(), [&](SearchInfo& o) {return o.sfen == Now; })) continue;
S.push_back({Now,0});
if (S.size() > DepthLim) {
S.pop_back();
if (S.size() == 0) return SI();
}
}
SI si = Search(G, Start, End, S.size() - 1);
if (si.size() != 0&& si.size()<S.size()) S = si;
return S;
}
int main() {
Graph G = MakeTree();
SI S;
S = Search(G, "0", "8",99);
for (auto&o : S) {
std::cout << o.sfen << std::endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKc3RydWN0IEluZm8gewoJc3RkOjpzdHJpbmcgc2ZlbjsKfTsKc3RydWN0IFNlYXJjaEluZm8gewoJU2VhcmNoSW5mbyhzdGQ6OnN0cmluZyYgUywgc3RkOjpzaXplX3QgSSkgOnNmZW4oUyksIEluZGV4KEkpIHt9CglzdGQ6OnN0cmluZyBzZmVuPSIwIjsKCXN0ZDo6c2l6ZV90IEluZGV4PTA7Cn07Ci8vdHlwZWRlZiBzdGQ6Om1hcDxzdGQ6OnN0cmluZywgc3RkOjp2ZWN0b3I8SW5mbz4+IFRyZWU7CnR5cGVkZWYgc3RkOjp2ZWN0b3I8c3RkOjpzdHJpbmc+IEdyYXBoRGF0YTsKdHlwZWRlZiBzdGQ6Om1hcDxzdGQ6OnN0cmluZywgR3JhcGhEYXRhPiBHcmFwaDsKdHlwZWRlZiBzdGQ6OnZlY3RvcjxTZWFyY2hJbmZvPiBTSTsKCkdyYXBoIE1ha2VUcmVlKCkgewoJR3JhcGggUnsgeyIwIix7IjEiLCIzIiwiNSJ9fSx7IjEiLHsiMCIsIjQiLCI2In19LCB7IjIiLHsiNCIsIjUiLCI2In19LHsiMyIseyIwIiwiNSIsIjcifX0sIHsiNCIseyIxIiwiMyIsIjcifX0seyI1Iix7IjIiLCIwIiwiMyJ9fSwgeyI2Iix7IjEiLCIyIiwiNyJ9fSx7IjciLHsiNiIsIjMiLCI4In19LHsiOCIseyI3In19IH07CglyZXR1cm4gUjsKfQpTSSBTZWFyY2goR3JhcGgmIEcsIHN0ZDo6c3RyaW5nIFN0YXJ0LCBzdGQ6OnN0cmluZyBFbmQsc3RkOjpzaXplX3QgRGVwdGhMaW0pIHsKCglpZiAoRGVwdGhMaW0gPT0gMSkgcmV0dXJuIFNJKCk7CgoJc3RkOjpzdHJpbmcgTm93ID0gU3RhcnQ7CglzdGQ6OnNpemVfdCBTaSA9IDE7CglTSSBTeyB7U3RhcnQsMH0sIH07Cgl3aGlsZSAoTm93ICE9IEVuZCkgewoJCWlmIChHW05vd10uc2l6ZSgpID09IFMuYmFjaygpLkluZGV4KSB7CgkJCVMucG9wX2JhY2soKTsKCQkJaWYgKFMuc2l6ZSgpID09IDApIHJldHVybiBTSSgpOwoJCQlOb3cgPSBTLmJhY2soKS5zZmVuOwoJCQljb250aW51ZTsKCQl9CgkJTm93ID0gR1tOb3ddW1MuYmFjaygpLkluZGV4KytdOwoJCWlmIChTLmVuZCgpICE9IHN0ZDo6ZmluZF9pZihTLmJlZ2luKCksIFMuZW5kKCksIFsmXShTZWFyY2hJbmZvJiBvKSB7cmV0dXJuIG8uc2ZlbiA9PSBOb3c7IH0pKSBjb250aW51ZTsKCQlTLnB1c2hfYmFjayh7Tm93LDB9KTsKCQlpZiAoUy5zaXplKCkgPiBEZXB0aExpbSkgewoJCQlTLnBvcF9iYWNrKCk7CgkJCWlmIChTLnNpemUoKSA9PSAwKSByZXR1cm4gU0koKTsKCgkJfQoJfQoKCVNJIHNpID0gU2VhcmNoKEcsIFN0YXJ0LCBFbmQsIFMuc2l6ZSgpIC0gMSk7CglpZiAoc2kuc2l6ZSgpICE9IDAmJiBzaS5zaXplKCk8Uy5zaXplKCkpIFMgPSBzaTsKCglyZXR1cm4gUzsKfQoKaW50IG1haW4oKSB7CglHcmFwaCBHID0gTWFrZVRyZWUoKTsKCVNJIFM7CglTID0gU2VhcmNoKEcsICIwIiwgIjgiLDk5KTsKCglmb3IgKGF1dG8mbyA6IFMpIHsKCQlzdGQ6OmNvdXQgPDwgby5zZmVuIDw8IHN0ZDo6ZW5kbDsKCX0KCglyZXR1cm4gMDsKfQo=