Advertisement
Guest User

Untitled

a guest
Dec 4th, 2016
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. using namespace std;
  5.  
  6. const long long inf = 1000000000;
  7.  
  8. class roll {
  9. int up, left, front;
  10.  
  11. public:
  12. roll (int x=inf, int y=inf, int z=inf) {
  13. up = x;
  14. left = y;
  15. front = z;
  16. }
  17.  
  18. void roll_right() {
  19. int temp = up;
  20. up = left;
  21. left = 7 - temp;
  22. }
  23.  
  24. void roll_front() {
  25. int temp = up;
  26. up = front;
  27. front = 7 - temp;
  28. }
  29.  
  30. int get_up() {
  31. return up;
  32. }
  33.  
  34. int get_left() {
  35. return left;
  36. }
  37.  
  38. int get_front() {
  39. return front;
  40. }
  41. };
  42.  
  43.  
  44. bool is_good(int k)
  45. {
  46. int x = k / 100;
  47. int y = k / 10 % 10;
  48. int z = k % 10;
  49. return (x > 0 && y > 0 && z > 0 &&
  50. x < 7 && y < 7 && z < 7 &&
  51. x != y && y != z && x != z &&
  52. x != 7 - y && x != 7 - z && y != 7 - z);
  53. }
  54.  
  55. bool can_right(roll a, roll b)
  56. {
  57. roll temp = a;
  58. temp.roll_right();
  59. return (temp.get_up() == b.get_up() &&
  60. temp.get_front() == b.get_front() &&
  61. temp.get_left() == b.get_left());
  62. }
  63.  
  64. bool can_front(roll a, roll b)
  65. {
  66. roll temp = a;
  67. temp.roll_front();
  68. return (temp.get_up() == b.get_up() &&
  69. temp.get_front() == b.get_front() &&
  70. temp.get_left() == b.get_left());
  71. }
  72.  
  73.  
  74. const int M = 655;
  75. long long h, w, u, l, f;
  76. long long d[1000][1000][48];
  77. long long s, q, temp, k;
  78.  
  79. int main()
  80. {
  81. cin >> w >> h >> u >> l >> f;
  82.  
  83. vector < int > edge_right(M), edge_front(M);
  84. edge_right.clear();
  85. edge_front.clear();
  86. roll temp1, temp2;
  87. vector < int > good;
  88. int rev_good[M];
  89. int count = 0;
  90.  
  91. for (int i = 0; i < M; i++)
  92. if (is_good(i)) {
  93. good.push_back(i);
  94. rev_good[i] = count;
  95. count++;
  96. }
  97.  
  98. for (size_t i = 0; i < good.size(); i++) {
  99. int x = good[i];
  100. temp1 = roll(x / 100, x / 10 % 10, x % 10);
  101. for (size_t j = 0; j < good.size(); j++) {
  102. int y = good[j];
  103. temp2 = roll(y / 100, y / 10 % 10, y % 10);
  104. if (can_right(temp1, temp2))
  105. edge_right[y] = x;
  106. if (can_front(temp1, temp2))
  107. edge_front[y] = x;
  108. }
  109. }
  110.  
  111. d[0][0][rev_good[u * 100 + l * 10 + f]] = u;
  112.  
  113.  
  114. for (int i = 0; i < h; i++) {
  115. for (int j = 0; j < w; j++) {
  116. for (int l = 0; l < 48; l++)
  117. if (d[i][j][l] == 0)
  118. d[i][j][l] = inf;
  119. if (i == 0 && j == 0)
  120. continue;
  121. for (size_t l = 0; l < good.size(); l++) {
  122. k = good[l];
  123.  
  124. temp = d[i][j][rev_good[k]];
  125.  
  126. s = edge_right[k];
  127. if (j > 0 && s > 0 && d[i][j - 1][rev_good[s]] != 0) {
  128. q = d[i][j - 1][rev_good[s]] + k / 100;
  129. d[i][j][rev_good[k]] = min(d[i][j][rev_good[k]], q);
  130. }
  131.  
  132. s = edge_front[k];
  133. if (i > 0 && s > 0 && d[i - 1][j][rev_good[s]] != 0) {
  134. q = d[i - 1][j][rev_good[s]] + k / 100;
  135. d[i][j][rev_good[k]] = min(d[i][j][rev_good[k]], q);
  136. }
  137. }
  138. }
  139. }
  140.  
  141. long long ans = inf;
  142.  
  143. for (int i = 0; i < 48; i++)
  144. ans = min(ans, d[h - 1][w - 1][i]);
  145.  
  146. cout << ans;
  147.  
  148. return 0;
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement