Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- const int inf = 10000000;
- class roll {
- int up, left, front;
- public:
- roll (int x=inf, int y=inf, int z=inf) {
- up = x;
- left = y;
- front = z;
- }
- void roll_right() {
- int temp = up;
- up = left;
- left = 7 - temp;
- }
- void roll_front() {
- int temp = up;
- up = 7 - front;
- front = temp;
- }
- int get_up() {
- return up;
- }
- int get_left() {
- return left;
- }
- int get_front() {
- return front;
- }
- };
- bool is_good(int k)
- {
- int x = k / 100;
- int y = k / 10 % 10;
- int z = k % 10;
- return (x > 0 && y > 0 && z > 0 &&
- x < 7 && y < 7 && z < 7 &&
- x != y && y != z && x != z &&
- x != 7 - y && x != 7 - z && y != 7 - z);
- }
- bool can_right(roll a, roll b)
- {
- roll temp = a;
- temp.roll_right();
- return (temp.get_up() == b.get_up() &&
- temp.get_front() == b.get_front() &&
- temp.get_left() == b.get_left());
- }
- bool can_front(roll a, roll b)
- {
- roll temp = a;
- temp.roll_front();
- return (temp.get_up() == b.get_up() &&
- temp.get_front() == b.get_front() &&
- temp.get_left() == b.get_left());
- }
- const int M = 655;
- long long h, w, u, l, f;
- long long d[1000][1000][48];
- long long s, q, temp, k;
- int main()
- {
- cin >> w >> h >> u >> l >> f;
- vector < int > edge_right(M), edge_front(M);
- edge_right.clear();
- edge_front.clear();
- roll temp1, temp2;
- vector < int > good;
- int rev_good[M];
- int count = 0;
- for (int i = 0; i < M; i++)
- if (is_good(i)) {
- good.push_back(i);
- rev_good[i] = count;
- count++;
- }
- for (size_t i = 0; i < good.size(); i++) {
- int x = good[i];
- temp1 = roll(x / 100, x / 10 % 10, x % 10);
- for (size_t j = 0; j < good.size(); j++) {
- int y = good[j];
- temp2 = roll(y / 100, y / 10 % 10, y % 10);
- if (can_right(temp1, temp2))
- edge_right[y] = x;
- if (can_front(temp1, temp2))
- edge_front[y] = x;
- }
- }
- d[0][0][rev_good[u * 100 + l * 10 + f]] = u;
- for (int i = 0; i < h; i++) {
- for (int j = 0; j < w; j++) {
- if (i == 0 && j == 0)
- continue;
- for (size_t l = 0; l < good.size(); l++) {
- k = good[l];
- temp = d[i][j][rev_good[k]];
- d[i][j][rev_good[k]] = (temp == 0 ? inf : temp);
- s = edge_right[k];
- if (j > 0 && s > 0 && d[i][j - 1][rev_good[s]] != 0) {
- q = d[i][j - 1][rev_good[s]] + k / 100;
- d[i][j][rev_good[k]] = min(d[i][j][rev_good[k]], q);
- }
- s = edge_front[k];
- if (i > 0 && s > 0 && d[i - 1][j][rev_good[s]] != 0) {
- q = d[i - 1][j][rev_good[s]] + k / 100;
- d[i][j][rev_good[k]] = min(d[i][j][rev_good[k]], q);
- }
- }
- }
- }
- long long ans = inf;
- for (int i = 0; i < 48; i++)
- ans = min(ans, d[h - 1][w - 1][i]);
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement