Advertisement
Guest User

Untitled

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