fork(5) download
copy 
  1. #include <ctime>
  2. #include <vector>
  3. #include <cstdio>
  4.  
  5. struct PMatrix {
  6. 	int nsize;					// Size of Matrix = nsize * nsize.
  7. 	int psize;					// PSize = path length.
  8. 	std::vector<int> data;		// Values of cells.
  9. 	std::vector<bool> mark;		// Mark means cell already visited.
  10.  
  11. 	std::vector<int> seq;		// Workspace for Path
  12. 	std::vector<int> bestseq;	// Best-known path so far.
  13.  
  14. 	int BestVal;				// Value of best-known path so far.
  15.  
  16. 	int si, sj;					// Starting coordinates.
  17.  
  18. 	// Coordinates are linearized for easier movement. Element (i, j) = Element(ij), with ij = i * n + j.
  19. 	int l(int i, int j) const { return i*nsize + j; }
  20. 	// Movement: Up/Down changes i, Left/Right changes j. Provides wrap-around.
  21. 	int up(int i, int j) const { return l((i+1)%nsize, j); }
  22. 	int dw(int i, int j) const { return l((i-1 + nsize)%nsize, j); }
  23. 	int ri(int i, int j) const { return l(i, (j+1)%nsize); }
  24. 	int le(int i, int j) const { return l(i, (j-1+nsize)%nsize); }
  25.  
  26. 	// Easy accessors.
  27. 	int e(int ij) const { return data[ij]; }
  28. 	int m(int ij) const { return mark[ij]; }
  29. 	// On visit: set node, branch, unset.
  30. 	void set(int ij) { mark[ij] = true; }
  31. 	void unset(int ij) { mark[ij] = false; }
  32. 	// Checks if node ij is visitable: value is not zero & unmarked (unvisited in current branch).
  33. 	bool c(int ij) const { return ((bool)e(ij) && !mark[ij]); }
  34.  
  35. 	// Initialize, set starting point.
  36. 	PMatrix(int n, int k, int i, int j) : nsize(n), psize(k+1), data(nsize*nsize), mark(nsize*nsize, false), seq(psize), bestseq(psize), BestVal(0), si(i), sj(j) {
  37. 		seq[0] = l(i, j);
  38. 		set(l(i, j));
  39. 	}
  40.  
  41. 	// Calculates total value of current finished path.
  42. 	int cvalue() {
  43. 		int v = 0;
  44. 		for (unsigned i = 0; i < seq.size(); ++i) {
  45. 			int ij = seq[i];
  46. 			v += e(ij);
  47. 		}
  48. 		return v;
  49. 	}
  50.  
  51. 	// Print path and value.
  52. 	void PrintBest() {
  53. 		int v = 0;
  54. 		for (unsigned i = 0; i < bestseq.size(); ++i) {
  55. 			int ij = bestseq[i];
  56. 			v += e(ij);
  57. 			printf("Visit (%d, %d) for value %d.\n", ij/nsize, ij%nsize, e(ij));
  58. 		}
  59. 		printf("Total value: %d\n", v);
  60. 	}
  61.  
  62. 	// Solve recursively: choose step k starting from (ci, cj).
  63. 	void Solve(int k, int ci, int cj) {
  64. 		// Full path constructed: check and end.
  65. 		if (k == psize) {
  66. 			// Calculate Value
  67. 			int val = cvalue();
  68. 			// If Val > BestVal, Save(); 
  69. 			if (val > BestVal) {
  70. 				BestVal = val;
  71. 				std::copy(seq.begin(), seq.end(), bestseq.begin());
  72. 			}
  73. 		}
  74. 		// Otherwise, set and branch. Bounds can be added.
  75. 		else /*if ((psize-k) * MaxElementValue > BestVal)*/ {
  76.  
  77. 			// Try 4 moves and branch.
  78. 			if (c(up(ci, cj))) {
  79. 				seq[k] = up(ci, cj);
  80. 				set(up(ci, cj));
  81. 				Solve(k+1, (ci + 1)%nsize, cj);
  82. 				unset(up(ci, cj));
  83. 			}
  84. 			if (c(dw(ci, cj))) {
  85. 				seq[k] = dw(ci, cj);
  86. 				set(dw(ci, cj));
  87. 				Solve(k+1, (ci + -1 + nsize)%nsize, cj);
  88. 				unset(dw(ci, cj));
  89. 			}
  90. 			if (c(ri(ci, cj))) {
  91. 				seq[k] = ri(ci, cj);
  92. 				set(ri(ci, cj));
  93. 				Solve(k+1, ci, (cj + 1)%nsize);
  94. 				unset(ri(ci, cj));
  95. 			}
  96. 			if (c(le(ci, cj))) {
  97. 				seq[k] = le(ci, cj);
  98. 				set(le(ci, cj));
  99. 				Solve(k+1, ci, (cj - 1 + nsize)%nsize);
  100. 				unset(le(ci, cj));
  101. 			}
  102. 		}
  103. 		return;
  104. 	}
  105.  
  106.  
  107. };
  108.  
  109. int main() {
  110.  
  111. 	PMatrix p(5, 20, 2, 2);
  112. 	int vals[5*5] = {  9,  1,  3,  1,  9,  6,  3,  2,  4,  1,  0,  7,  0, 7,  7,  5,  4,  9,  4,  9,  7,  9,  1,  5,  5};
  113. 	for (int ij = 0; ij < 5*5; ++ij) {
  114. 		p.data[ij] = vals[ij];
  115. 	}
  116. 	clock_t a(clock());
  117. 	p.Solve(1, 2, 2);
  118. 	clock_t e(clock());
  119. 	p.PrintBest();
  120. 	printf("Number of ticks: %u.\n", (e-a));
  121. 	return 0;
  122. }
Success #stdin #stdout 0.42s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Visit (2, 2) for value 0.
Visit (3, 2) for value 9.
Visit (4, 2) for value 1.
Visit (0, 2) for value 3.
Visit (1, 2) for value 2.
Visit (1, 3) for value 4.
Visit (2, 3) for value 7.
Visit (3, 3) for value 4.
Visit (4, 3) for value 5.
Visit (4, 4) for value 5.
Visit (0, 4) for value 9.
Visit (0, 0) for value 9.
Visit (1, 0) for value 6.
Visit (1, 1) for value 3.
Visit (2, 1) for value 7.
Visit (3, 1) for value 4.
Visit (4, 1) for value 9.
Visit (4, 0) for value 7.
Visit (3, 0) for value 5.
Visit (3, 4) for value 9.
Visit (2, 4) for value 7.
Total value: 115
Number of ticks: 420000.
https://ideone.com/5kOyxq
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!