fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <string>
  5. #include <algorithm>
  6.  
  7. struct Info {
  8. 	std::string sfen;
  9. };
  10. struct SearchInfo {
  11. 	SearchInfo(std::string& S, std::size_t I) :sfen(S), Index(I) {}
  12. 	std::string sfen="0";
  13. 	std::size_t Index=0;
  14. };
  15. //typedef std::map<std::string, std::vector<Info>> Tree;
  16. typedef std::vector<std::string> GraphData;
  17. typedef std::map<std::string, GraphData> Graph;
  18. typedef std::vector<SearchInfo> SI;
  19.  
  20. Graph MakeTree() {
  21. 	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"}} };
  22. 	return R;
  23. }
  24. SI Search(Graph& G, std::string Start, std::string End,std::size_t DepthLim) {
  25.  
  26. 	if (DepthLim == 1) return SI();
  27.  
  28. 	std::string Now = Start;
  29. 	std::size_t Si = 1;
  30. 	SI S{ {Start,0}, };
  31. 	while (Now != End) {
  32. 		if (G[Now].size() == S.back().Index) {
  33. 			S.pop_back();
  34. 			if (S.size() == 0) return SI();
  35. 			Now = S.back().sfen;
  36. 			continue;
  37. 		}
  38. 		Now = G[Now][S.back().Index++];
  39. 		if (S.end() != std::find_if(S.begin(), S.end(), [&](SearchInfo& o) {return o.sfen == Now; })) continue;
  40. 		S.push_back({Now,0});
  41. 		if (S.size() > DepthLim) {
  42. 			S.pop_back();
  43. 			if (S.size() == 0) return SI();
  44.  
  45. 		}
  46. 	}
  47.  
  48. 	SI si = Search(G, Start, End, S.size() - 1);
  49. 	if (si.size() != 0&& si.size()<S.size()) S = si;
  50.  
  51. 	return S;
  52. }
  53.  
  54. int main() {
  55. 	Graph G = MakeTree();
  56. 	SI S;
  57. 	S = Search(G, "0", "8",99);
  58.  
  59. 	for (auto&o : S) {
  60. 		std::cout << o.sfen << std::endl;
  61. 	}
  62.  
  63. 	return 0;
  64. }
  65.  
Success #stdin #stdout 0s 3476KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
0
1
6
7
8
https://ideone.com/GxnWsH
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!