fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits>
  4.  
  5. enum class Operator{
  6. 	None,
  7. 	Plus,
  8. 	Minus,
  9. 	Multi,
  10. 	Div,
  11. 	Mod,
  12. 	Wall,
  13. 	Max,
  14. };
  15.  
  16. static const int Top = 0;
  17. static const int Right = 1;
  18. static const int Bottom = 2;
  19. static const int Left = 3;
  20.  
  21. struct Wall{
  22. 	Operator Op;
  23. 	double Value;
  24. 	bool IsWalked;
  25. };
  26.  
  27. struct Floor{
  28.  
  29. 	union{
  30. 		struct{
  31. 			int Top;
  32. 			int Right;
  33. 			int Bottom;
  34. 			int Left;
  35. 		};
  36. 		int Dir[4];
  37. 	};
  38. 	Floor(int Top_, int Right_, int Bottom_, int Left_){
  39. 		Dir[0] = Top_;
  40. 		Dir[1] = Right_; 
  41. 		Dir[2] = Bottom_;
  42. 		Dir[3] = Left_;
  43. 	}
  44. };
  45.  
  46. struct FootPrint;
  47. typedef std::pair<std::vector<std::vector<Floor>>,std::vector<Wall>> Map;
  48. typedef std::vector<FootPrint> Stack;
  49.  
  50. struct Point{
  51. 	int X, Y;
  52. };
  53.  
  54.  
  55. struct FootPrint{
  56. 	Point Pos;
  57. 	int From, To;
  58. 	int Score;
  59. 	//Stack MB;
  60. };
  61.  
  62. Point Direction[4]{{ 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 }};
  63.  
  64. static const int Width = 7;
  65. static const int Height = 7;
  66.  
  67. Map MakeData(){
  68. 	std::vector<Wall> WallData = {
  69. 		{ Operator::Minus, 2, false }, { Operator::Plus, 5, false }, { Operator::Minus, 1, false }, { Operator::Plus, 3, false }, { Operator::Plus, 2, false }, { Operator::Minus, 1, false },///
  70. 		{ Operator::Plus, 1, false }, { Operator::Plus, 3, false }, { Operator::Plus, 2, false }, { Operator::Minus, 1, false }, { Operator::Plus, 2, false }, { Operator::Minus, 1, false }, { Operator::Plus, 3, false },///
  71. 		{ Operator::Plus, 1, false }, { Operator::Plus, 4, false }, { Operator::Multi, 2, false }, { Operator::Minus, 1, false }, { Operator::Plus, 4, false }, { Operator::Minus, 2, false },///
  72. 		{ Operator::Plus, 4, false }, { Operator::Plus, 2, false }, { Operator::Plus, 1, false }, { Operator::Plus, 3, false }, { Operator::Plus, 3, false }, { Operator::Plus, 5, false }, { Operator::Minus, 1, false },///
  73. 		{ Operator::Plus, 3, false }, { Operator::Plus, 2, false }, { Operator::Minus, 1, false }, { Operator::Plus, 4, false }, { Operator::Plus, 1, false }, { Operator::Multi, 3, false },///
  74. 		{ Operator::Minus, 2, false }, { Operator::Minus, 1, false }, { Operator::Minus, 1, false }, { Operator::Plus, 5, false }, { Operator::Minus, 1, false }, { Operator::Minus, 2, false }, { Operator::Plus, 2, false },///
  75. 		{ Operator::Plus, 4, false }, { Operator::Minus, 1, false }, { Operator::Plus, 3, false }, { Operator::Minus, 2, false }, { Operator::Plus, 5, false }, { Operator::Plus, 1, false },///
  76. 		{ Operator::Plus, 3, false }, { Operator::Plus, 5, false }, { Operator::Plus, 4, false }, { Operator::Minus, 1, false }, { Operator::Plus, 2, false }, { Operator::Plus, 2, false }, { Operator::Plus, 1, false },///
  77. 		{ Operator::Minus, 2, false }, { Operator::Multi, 3, false }, { Operator::Plus, 1, false }, { Operator::Plus, 2, false }, { Operator::Minus, 1, false }, { Operator::Plus, 3, false },///
  78. 		{ Operator::Minus, 1, false }, { Operator::Plus, 1, false }, { Operator::Minus, 2, false }, { Operator::Plus, 4, false }, { Operator::Plus, 4, false }, { Operator::Plus, 1, false }, { Operator::Minus, 2, false },///
  79. 		{ Operator::Plus, 5, false }, { Operator::Plus, 1, false }, { Operator::Plus, 3, false }, { Operator::Minus, 1, false }, { Operator::Multi, 2, false }, { Operator::Plus, 4, false },///
  80. 		{ Operator::Plus, 1, false }, { Operator::Plus, 2, false }, { Operator::Plus, 2, false }, { Operator::Minus, 2, false }, { Operator::Plus, 1, false }, { Operator::Plus, 5, false }, { Operator::Plus, 3, false },///
  81. 		{ Operator::Plus, 3, false }, { Operator::Minus, 1, false }, { Operator::Plus, 2, false }, { Operator::Plus, 4, false }, { Operator::Minus, 2, false }, { Operator::Plus, 1, false },///
  82. 	};
  83. 	std::vector<std::vector<Floor>> FloorData = {//これは自動生成できそうだけど、わからん。脳弱になるー。うぎゃーーーー！！！上下幅は7*7で13。
  84. 		{ { -1, 0, 6, -1 }, { -1, 1, 7, 0 }, { -1, 2, 8, 1 }, { -1, 3, 9, 2 }, { -1, 4, 10, 3 }, { -1, 5, 11, 4 }, { -1, -1, 12, 5 }, },
  85. 		{ { 6, 13, 19, -1 }, { 7, 14, 20, 13 }, { 8, 15, 21, 14 }, { 9, 16, 22, 15 }, { 10, 17, 23, 16 }, { 11, 18, 24, 17 }, { 12, -1, 25, 18 }, },
  86. 		{ { 19, 26, 32, -1 }, { 20, 27, 33, 26 }, { 21, 28, 34, 27 }, { 22, 29, 35, 28 }, { 23, 30, 36, 29 }, { 24, 31, 37, 30 }, { 25, -1, 38, 31 }, },
  87. 		{ { 32, 39, 45, -1 }, { 33, 40, 46, 39 }, { 34, 41, 47, 40 }, { 35, 42, 48, 41 }, { 36, 43, 49, 42 }, { 37, 44, 50, 43 }, { 38, -1, 51, 44 } },
  88. 		{ { 45, 52, 58, -1 }, { 46, 53, 59, 52 }, { 47, 54, 60, 53 }, { 48, 55, 61, 54 }, { 49, 56, 62, 55 }, { 50, 57, 63, 56 }, { 51, -1, 64, 57 }, },
  89. 		{ { 58, 65, 71, -1 }, { 59, 66, 72, 65 }, { 60, 67, 73, 66 }, { 61, 68, 74, 67 }, { 62, 69, 75, 68 }, { 63, 70, 76, 69 }, {64,-1,77,70}, },
  90. 		{ { 71, 78, -1, -1 }, { 72, 79, -1, 78 }, { 73, 80, -1, 79 }, { 74, 81, -1, 80 }, { 75, 82, -1, 81 }, { 76, 83, -1, 82 }, {77,-1,-1,83}, },
  91. 	};
  92.  
  93. 	return std::make_pair(FloorData,WallData);
  94. }
  95.  
  96. bool ShowMap(Map& M,bool ViewType = true ){
  97. 	bool F2 = false;
  98.  
  99. 	for (auto& oo : M.first){
  100. 		if (ViewType == true){
  101. 			std::cout << "  ";
  102. 			for (auto& o : oo){
  103. 				if (o.Dir[Right] == -1)continue;
  104. 				if (M.second[o.Dir[Right]].Op == Operator::Plus) std::cout << '+';
  105. 				if (M.second[o.Dir[Right]].Op == Operator::Minus) std::cout << '-';
  106. 				if (M.second[o.Dir[Right]].Op == Operator::Multi) std::cout << '*';
  107. 				if (M.second[o.Dir[Right]].Op == Operator::Div) std::cout << '/';
  108. 				std::cout << M.second[o.Dir[Right]].Value << "  ";
  109. 			}
  110. 			std::cout << std::endl;
  111. 			for (auto& o : oo){
  112. 				if (o.Dir[Bottom] == -1)continue;
  113. 				if (M.second[o.Dir[Bottom]].Op == Operator::Plus) std::cout << '+';
  114. 				if (M.second[o.Dir[Bottom]].Op == Operator::Minus) std::cout << '-';
  115. 				if (M.second[o.Dir[Bottom]].Op == Operator::Multi) std::cout << '*';
  116. 				if (M.second[o.Dir[Bottom]].Op == Operator::Div) std::cout << '/';
  117. 				std::cout << M.second[o.Dir[Bottom]].Value << "  ";
  118. 			}
  119. 			std::cout << std::endl;
  120. 		}
  121. 		else{
  122. 			for (auto& o : oo){
  123. 				if (o.Dir[Top] == -1)continue;
  124. 				F2 = true;
  125. 				if (M.second[o.Dir[Top]].Op == Operator::Plus) std::cout << '+';
  126. 				if (M.second[o.Dir[Top]].Op == Operator::Minus) std::cout << '-';
  127. 				if (M.second[o.Dir[Top]].Op == Operator::Multi) std::cout << '*';
  128. 				if (M.second[o.Dir[Top]].Op == Operator::Div) std::cout << '/';
  129. 				std::cout << M.second[o.Dir[Top]].Value << "  ";
  130. 			}
  131. 			if(F2 == true) std::cout << std::endl;
  132. 			for (auto& o : oo){
  133. 				if (o.Dir[Left] == -1)continue;
  134. 				std::cout << "  ";
  135. 				if (M.second[o.Dir[Left]].Op == Operator::Plus) std::cout << '+';
  136. 				if (M.second[o.Dir[Left]].Op == Operator::Minus) std::cout << '-';
  137. 				if (M.second[o.Dir[Left]].Op == Operator::Multi) std::cout << '*';
  138. 				if (M.second[o.Dir[Left]].Op == Operator::Div) std::cout << '/';
  139. 				std::cout << M.second[o.Dir[Left]].Value;
  140. 			}
  141. 			std::cout << std::endl;
  142.  
  143.  
  144. 		}
  145. 	}
  146.  
  147. 	return 0;
  148. }
  149.  
  150. bool Find(Stack& ST,Point P,int D){
  151.  
  152. 	for (auto& o : ST){
  153. 		if ((o.Pos.X == P.X) && (o.Pos.Y == P.Y) && ((o.From == D) || (o.To == D))) return true;
  154. 	}
  155.  
  156. 	return false;
  157. }
  158.  
  159. int CalcScore(Operator Op, int SA, int SB){
  160. 	switch (Op)
  161. 	{
  162. 		case Operator::Plus:
  163. 			return SA + SB;
  164. 		case Operator::Minus:
  165. 			return SA - SB;
  166. 		case Operator::Multi:
  167. 			return SA*SB;
  168. 		case Operator::Div:
  169. 			return SA / SB;
  170. 		case Operator::Mod:
  171. 			return SA%SB;
  172. 		default:
  173. 			break;
  174. 	}
  175. 	return std::numeric_limits<int>::min() / 16;
  176. }
  177.  
  178. int From(Point A, Point B){
  179.  
  180. 	Point To{ A.X - B.X, A.Y - B.Y };
  181.  
  182.  
  183. 	for (int i = 0; i < 4; i++){
  184. 		if (Direction[i].X == To.X && Direction[i].Y == To.Y) return (i + 2) % 4;
  185. 	}
  186.  
  187. 	return -1;
  188.  
  189. }
  190.  
  191.  
  192. bool IsMove(Point P, Point L){
  193. 	if (P.X < 0) return false;
  194. 	if (P.Y < 0) return false;
  195. 	if (P.X < L.X) return false;
  196. 	if (P.Y < L.Y) return false;
  197.  
  198. 	return true;
  199. }
  200.  
  201. bool Search(Map& M,Stack& S,int& Score,const Point& Start,const Point& End){
  202. 	Point Now = Start;
  203. 	Stack ST;
  204. 	Stack MST;
  205. 	int MaxScore = 0;
  206. 	int ScoreT = Score;
  207. 	int Dir = 0;
  208. 	FootPrint FP{ Now, -1, Dir, Score };
  209.  
  210.  
  211. 	while (!((Now.X == End.X) && (Now.Y == End.Y))){
  212. 	//while (true){
  213.  
  214. 		if (ST.size() >= 1){
  215. 			FP.From = From(Now, ST[ST.size() - 1].Pos);
  216. 		}
  217. 		ST.push_back(FP);
  218.  
  219. 		if (IsMove({ Now.X + Direction[Dir].X, Now.Y + Direction[Dir].Y }, { Width, Height })){
  220. 			Dir++;
  221. 			L1:
  222. 			if (Dir == 4){
  223. 				ST.pop_back();
  224. 				Dir = ST.back().To+1;
  225. 			}
  226. 			if (Dir == 4) goto L1;
  227. 			if (ST.size() == 0){
  228. 				S = MST;
  229. 				Score = MaxScore;
  230. 				return true;
  231. 			}
  232. 			Dir %= 4;
  233. 			continue;
  234. 		}
  235. 		if (Find(ST, { Now.X + Direction[Dir].X, Now.Y + Direction[Dir].Y }, Dir) == true){
  236. 			Dir++;
  237. 			L2:
  238. 			if (Dir == 4){
  239. 				ST.pop_back();
  240. 				Dir = ST.back().To+1;
  241. 			}
  242. 			if (Dir == 4) goto L2;
  243. 			if (ST.size() == 0){
  244. 				S = MST;
  245. 				Score = MaxScore;
  246. 				return true;
  247. 			}
  248. 			Dir %= 4;
  249. 			continue;
  250. 		}
  251. 		Point PT{ Now.X + Direction[Dir].X, Now.Y + Direction[Dir].Y };
  252. 		Operator Op = M.second[M.first[PT.Y][PT.X].Dir[Dir]].Op;
  253. 		int V = M.second[M.first[PT.Y][PT.X].Dir[Dir]].Value;
  254. 		ScoreT = CalcScore(Op, V, ScoreT);
  255.  
  256. 		FP.Pos = PT;
  257. 		FP.Score = ScoreT;
  258. 		FP.To=Dir
  259.  
  260. 	}
  261.  
  262.  
  263. }
  264.  
  265.  
  266. int main(){
  267.  
  268. 	auto M = MakeData();
  269. 	ShowMap(M);
  270. 	std::cout << std::endl;
  271. 	ShowMap(M, false);
  272. 	return 0;
  273.  
  274. }
  275.  
  276.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘bool Search(Map&, Stack&, int&, const Point&, const Point&)’:
prog.cpp:260:2: error: expected ‘;’ before ‘}’ token
  }
  ^
prog.cpp:263:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
stdout
copy 
Standard output is empty
https://ideone.com/pVs5KO
language:
C++14 (gcc 8.3)
created:
10 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!