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. 	return W;
  29. }
  30. /**/
  31. 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) {
  32. 	static std::array<int, 4> XP = { 0,1,0,-1 };
  33. 	static std::array<int, 4> YP = { 1,0,-1,0 };
  34. 	static std::uintmax_t C = 0;
  35.  
  36. 	auto X1 = std::get<0>(Now);
  37. 	auto Y1 = std::get<1>(Now);
  38. 	auto X2 = std::max<int>(std::get<0>(Last), 0);
  39. 	auto Y2 = std::max<int>(std::get<1>(Last), 0);
  40. 	if ((X1 == X2) && (Y1 == Y2)) {
  41. 		if (Min >= Wait) {
  42. 			FP.push_back({ X1,Y1 });
  43. 			Min = Wait;
  44. 			C++;	
  45. 			FPR = FP;
  46. 		}
  47. 	}
  48.  
  49. 	if (Min <= Wait) {
  50. 		return false;
  51. 	}
  52. 	FP.push_back({ std::get<0>(Now),std::get<1>(Now) });
  53. 	for (std::size_t i = 0; i < 4; i++) {
  54. 		if (std::get<0>(Now) + XP[i] < 0) { continue; };
  55. 		if (std::get<1>(Now) + YP[i] < 0) { continue; };
  56. 		if (std::get<0>(Now) + XP[i] >= M.front().size() ) { continue; }
  57. 		if (std::get<1>(Now) + YP[i] >= M.size()) { continue; }
  58. 		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]); });
  59.  
  60. 		if (it != FP.end()) { continue; }
  61.  
  62.  
  63. 		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);
  64.  
  65.  
  66.  
  67. 	}
  68. 	FP.pop_back();
  69.  
  70. 	return true;
  71.  
  72.  
  73.  
  74. }
  75.  
  76. std::tuple<std::uintmax_t,FootPrint> SearchPath(const MapType& M, const Point& Fst, const Point& Last) {
  77. 	std::intmax_t Min = PoorSearch(M, Fst, Last);
  78. 	FootPrint fp;
  79. 	FootPrint FPR;
  80. 	//fp.push_back({ 0,0 });
  81. 	//ESS::Locate(std::get<0>(Fst)+Pa, std::get<1>(Fst)+Pa);
  82. 	//std::cout << '*';
  83. 	SearchPath_r(M, fp, Fst, Last, 0, Min,FPR);
  84.  
  85. 	return { Min,FPR };
  86.  
  87. }
  88.  
  89. typedef std::tuple<Point, std::int64_t,std::uintmax_t,std::uintmax_t> FootData;//pos,dir,weight,now_weight
  90. typedef std::vector<FootData> FootPrint2;
  91.  
  92. std::tuple<std::uintmax_t, FootPrint2> SearchPathL(const MapType& M, const Point& Fst, const Point& Last) {
  93. 	static std::array<int, 4> XP = { 0,1,0,-1 };
  94. 	static std::array<int, 4> YP = { 1,0,-1,0 };
  95. 	std::uintmax_t MinWeight = PoorSearch(M, Fst, Last);
  96. 	std::uintmax_t Weight = 0;
  97.  
  98. 	FootPrint2 FP;
  99. 	FootPrint2 R;
  100.  
  101. 	FP.push_back({ Fst,0,0,0 });
  102.  
  103. 	while(FP.size()){
  104. 	//for (std::get<1>(FP.back()); std::get<1>(FP.back()) < 4; std::get<1>(FP.back())++) {
  105. 		auto i = std::get<1>(FP.back())++;
  106. 		if (i == 3) {
  107. 			FP.pop_back();
  108. 			continue;
  109. 		}
  110. 		auto& o = FP.back();
  111. 		auto& P = std::get<0>(o);
  112. 		Weight = std::get<3>(o);
  113.  
  114. 		auto X = std::get<0>(P) + XP[i];
  115. 		auto Y = std::get<1>(P) + YP[i];
  116.  
  117. 		if (X < 0) { continue; }
  118. 		if (Y < 0) { continue; }
  119. 		if (X >= M.front().size()) { continue; }
  120. 		if (Y >= M.size()) { continue; }
  121.  
  122. 		auto it = std::find_if(FP.begin(), FP.end(), [&](auto& o) {return (std::get<0>(std::get<0>(o)) == X) && (std::get<1>(std::get<0>(o)) == Y); });
  123. 		if (it != FP.end()) { continue; }
  124.  
  125.  
  126. 		if (X == std::get<0>(Last) && Y == std::get<1>(Last)) {
  127. 			if (Weight <= MinWeight) {
  128. 				FP.push_back({ { X,Y }, i, M[Y][X], Weight + M[Y][X] });
  129. 				R = FP;
  130. 				MinWeight = Weight;
  131.  
  132. 			}
  133. 			//FP.pop_back();
  134. 			continue;
  135. 		}
  136. 		else {
  137.  
  138. 			if (Weight + M[Y][X] >= MinWeight) {
  139. 				if(i==3)FP.pop_back();
  140. 				continue;
  141. 			}
  142. 			else {
  143. 				Weight += M[Y][X];
  144. 			}
  145. 		}
  146. 		FP.push_back({ { X,Y },0, M[Y][X], Weight });
  147. 	}
  148.  
  149. 	return { MinWeight,R };
  150. }
  151.  
  152. MapType MakeVector() {
  153. 	MapType M{
  154. 		{0,2,9,5,3,9,4,1,3 },
  155. 		{7,1,5,4,6,7,9,8,8 },
  156. 		{8,3,4,1,1,2,9,4,6 },
  157. 		{2,3,7,1,6,5,4,2,6 },
  158. 		{4,7,3,8,5,7,3,6,0 },
  159. 	};
  160.  
  161. 	return M;
  162. }
  163.  
  164. int main() {
  165. 	MapType M = MakeVector();
  166. 	FootPrint FP;
  167. 	FootPrint2 FP2;
  168. 	std::uintmax_t R;
  169.  
  170. 	//std::tie(R,FP) = SearchPath(M, { 0,0 }, { 8,4 });
  171. 	std::tie(R,FP2) = SearchPathL(M, { 0,0 }, { 8,4 });
  172.  
  173. 	std::cout << R << std::endl;
  174.  
  175. 	for (auto& o : FP2) {
  176. 		//std::cout << std::get<0>(o) << ',' << std::get<1>(o) << ',' << M[std::get<1>(o)][std::get<0>(o)] << std::endl;
  177. 		std::cout << std::get<0>(std::get<0>(o)) << ',' << std::get<1>(std::get<0>(o)) << ',' << M[std::get<1>(std::get<0>(o))][std::get<0>(std::get<0>(o))] << std::endl;
  178. 	}
  179.  
  180. 	return 0;
  181. }
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
8,4,0
https://ideone.com/lOmm7w
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!