ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1016. Cube on the Walk

WA3 xelp
Posted by Tbilisi SU: Giorgi Saghinadze (GVS) 16 Sep 2009 21:49
please give me test case, where my prog files, I've tested it on my friend's AC code and did not find mistake
thanks.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#define VI vector<int>
using namespace std;

map< VI , int > mp[10][10];

int p[4][6] =
{
    {2 , 4 , 1 , 3 , 0 , 5}, // forw
    {4 , 2 , 0 , 3 , 1 , 5},//backw
    {0 , 1 , 5 , 2 , 3 , 4}, // left
    {0 , 1 , 3 , 4 , 5 , 2} // right
};

int t[4][2] =
{{0,1},{0,-1},{-1,0},{1 , 0}};
string s1 , s2;
int xst , yst , xfin , yfin , i , j , n , m , a[10] , st , fin , x , y , ans = 1000000000 , nom , xx , yy;
struct str
{
    int x  , y;
    vector<int> v;
    str(){
        x = y = 0;
    }
    str(int _x , int _y , vector<int> _v)
    {
        x = _x;
        y = _y;
        v = _v;
    }
};

bool operator < (str a , str b)
{
    return a.x < b.x || a.x == b.x && a.y < b.y || a.x == b.x && a.y == b.y && a.v < b.v;
}

bool operator == (str a , str b)
{
    return a.x == b.x && a.y == b.y && a.v == b.v;
}

set<pair<int , str> > stt;
map<str , str> par;
void findans(str n)
{
    if (n.x == xst && n.y == yst && mp[n.x][n.y][n.v] == a[4]); else
        findans(par[n]);

    cout<<char(n.x + 'a' - 1)<<char(n.y + '0')<<" ";
}

int main()
{
    cin>>s1>>s2;
    xst = s1[0] - 'a' + 1;
    yst = s1[1] - '0';
    xfin = s2[0] - 'a' + 1;
    yfin = s2[1] - '0';
    for (i = 0; i < 6; i++)
        cin>>a[i];

    if (s1 == s2)
    {
        cout<<a[4]<<" "<<s1;
        return 0;
    }

    vector<int> v(a , a + 6);

    vector<int> sle = v;
    sort(sle.begin() , sle.end());
    do
    {
        for (i = 1; i <= 8; i++)
            for (j = 1; j <= 8; j++)
            {
                mp[i][j][sle] = 110000000;
                stt.insert(make_pair(110000000 , str(i,j,sle)));
            }
    } while (next_permutation(sle.begin() , sle.end()));

    mp[xst][yst][v] = a[4];
    stt.erase(  stt.find(make_pair(110000000 , str(xst,yst,v)))   );
    stt.insert(make_pair(a[4] , str(xst,yst,v)));
    str stans;
    while (1)
    {
        str w = stt.begin()->second;
        int dis = stt.begin()->first;
        if (dis == 110000000) break;

        x = w.x;
        y = w.y;
        VI b = w.v , c(6);

        for (i = 0; i < 4; i++)
        {
            xx = x + t[i][0];
            yy = y + t[i][1];
            if (xx >= 1 && xx <= 8 && yy >= 1 && yy <= 8); else continue;
            for (j = 0; j < 6 ; j++)
            {
                c[p[i][j]] = b[j];
            }

            if (mp[xx][yy][c] > dis + c[4])
            {
                mp[xx][yy][c] = dis + c[4];
                par[str(xx , yy , c)] = w;
                stt.insert(make_pair(dis + c[4] , str(xx , yy , c)));
                if (xx == xfin && yy == yfin && mp[xx][yy][c] < ans)
                {
                    ans = dis + c[4];
                    stans = str(xx ,yy , c);
                }
            }
        }

        stt.erase(stt.find(make_pair(dis , w)));

    }

    cout<<ans<<" ";
    findans(stans);

    return 0;
}