ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1016. Кубик на прогулке

WA3 xelp
Послано Tbilisi SU: Giorgi Saghinadze (GVS) 16 сен 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;
}