fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdint>
  4. #include <tuple> 
  5. #include <algorithm>
  6. #include <array>
  7.  
  8.  
  9. typedef std::vector<std::vector<std::uint64_t>> MapType;
  10. typedef std::tuple<std::int64_t, std::int64_t> Point;
  11. typedef std::vector<Point> FootPrint;
  12.  
  13. int Pa = 2;
  14.  
  15. std::uintmax_t PoorSearch(const MapType& M, const Point& Fst, const Point& Last) {
  16.  
  17. 	std::uintmax_t W = 0;
  18. 	std::int64_t i = 0;
  19. 	std::size_t j = 0;
  20. 	for (j= std::get<1>(Fst);j != std::get<1>(Last); j += (std::get<1>(Fst) - std::get<1>(Last)) ? 1 : -1) {
  21. 		W += M[j][std::get<0>(Fst)];
  22. 	}
  23.  
  24. 	for (i = std::get<0>(Fst); i != std::get<0>(Last); i += (std::get<0>(Fst) - std::get<0>(Last)) ? 1 : -1) {
  25. 		W += M[j-1][i];
  26. 	}
  27.  
  28.  
  29.  
  30. 	return W;
  31. }
  32. /**/
  33. bool SearchPath_r(const MapType& M, FootPrint FP, const Point& Now, const Point& Last, const std::uintmax_t& Wait, std::intmax_t& Min,FootPrint& FPR) {
  34. 	static std::array<int, 4> XP = { 0,1,0,-1 };
  35. 	static std::array<int, 4> YP = { 1,0,-1,0 };
  36. 	static std::uintmax_t C = 0;
  37.  
  38. 	auto X1 = std::get<0>(Now);
  39. 	auto Y1 = std::get<1>(Now);
  40. 	auto X2 = std::max<int>(std::get<0>(Last)-1, 0);
  41. 	auto Y2 = std::max<int>(std::get<1>(Last)-1, 0);
  42. 	if ((X1 == X2) && (Y1 == Y2)) {
  43. 		if (Min >= Wait) {
  44. 			Min = Wait;
  45. 			C++;	
  46. 			FPR = FP;
  47. 			//ESS::Locate(15, 0);
  48. 			//std::cout << C;
  49. 		}
  50. 		//ESS::Locate(std::get<0>(Now)+Pa, std::get<1>(Now)+Pa);
  51. 		//std::cout << ' ';
  52. 		return true;
  53. 	}
  54.  
  55. 	if (Min <= Wait) {
  56. 		//ESS::Locate(std::get<0>(Now)+Pa, std::get<1>(Now)+Pa);
  57. 		//std::cout << ' ';
  58. 		return false;
  59. 	}
  60. 	//ESS::Locate(std::get<0>(Now)+Pa, std::get<1>(Now)+Pa);
  61. 	//std::cout << '*' ;
  62. 	FP.push_back({ std::get<0>(Now),std::get<1>(Now) });
  63. 	for (std::size_t i = 0; i < 4; i++) {
  64. 		if (std::get<0>(Now) + XP[i] < 0) { continue; };
  65. 		if (std::get<1>(Now) + YP[i] < 0) { continue; };
  66. 		if (std::get<0>(Now) + XP[i] >= M.front().size() ) { continue; }
  67. 		if (std::get<1>(Now) + YP[i] >= M.size()) { continue; }
  68. 		auto it = std::find_if(FP.begin(), FP.end(), [&](auto& o) {return (std::get<0>(o) == std::get<0>(Now) + XP[i]) && (std::get<1>(o) == std::get<1>(Now) + YP[i]); });
  69.  
  70. 		if (it != FP.end()) { continue; }
  71.  
  72.  
  73. 		SearchPath_r(M, FP,{ std::get<0>(Now) + XP[i],std::get<1>(Now) + YP[i] }, Last, Wait + M[std::get<1>(Now) + YP[i]][std::get<0>(Now) + XP[i]], Min,FPR);
  74.  
  75.  
  76.  
  77. 	}
  78. 	FP.pop_back();
  79. 	//ESS::Locate(std::get<0>(Now)+Pa, std::get<1>(Now)+Pa);
  80. 	//std::cout << ' ';
  81. 	return true;
  82.  
  83.  
  84.  
  85. }
  86.  
  87. std::tuple<std::uintmax_t,FootPrint> SearchPath(const MapType& M, const Point& Fst, const Point& Last) {
  88. 	std::intmax_t Min = PoorSearch(M, Fst, Last);
  89. 	FootPrint fp;
  90. 	FootPrint FPR;
  91. 	//fp.push_back({ 0,0 });
  92. 	//ESS::Locate(std::get<0>(Fst)+Pa, std::get<1>(Fst)+Pa);
  93. 	//std::cout << '*';
  94. 	SearchPath_r(M, fp, Fst, Last, 0, Min,FPR);
  95.  
  96. 	return { Min,FPR };
  97.  
  98. }
  99.  
  100.  
  101. MapType MakeVector() {
  102. 	MapType M{
  103. 		{0,2,9,5,3,9,4,1,3 },
  104. 		{7,1,5,4,6,7,9,8,8 },
  105. 		{8,3,4,1,1,2,9,4,6 },
  106. 		{2,3,7,1,6,5,4,2,6 },
  107. 		{4,7,3,8,5,7,3,6,0 },
  108. 	};
  109.  
  110. 	return M;
  111. }
  112.  
  113. int main() {
  114. 	MapType M = MakeVector();
  115. 	FootPrint FP;
  116. 	std::uintmax_t R;
  117. 	std::tie(R,FP) = SearchPath(M, { 0,0 }, { 9,5 });
  118. 	//ESS::Locate(0, 10);
  119. 	std::cout << R << std::endl;
  120. 	for (auto& o : FP) {
  121.  
  122. 		std::cout << std::get<0>(o) << ',' << std::get<1>(o) << ',' << M[std::get<1>(o)][std::get<0>(o)] << std::endl;
  123. 	}
  124.  
  125. 	return 0;
  126. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
Standard input is empty
stdout 
31
0,0,0
1,0,2
1,1,1
1,2,3
2,2,4
3,2,1
4,2,1
5,2,2
5,3,5
6,3,4
7,3,2
7,4,6
https://ideone.com/PQwu2U
language:
C++14 (gcc 8.3)
created:
4 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!