the output part states that:
"The only line of the output must contain the minimal sum
followed by the optimal route (one of possible routes with
minimal sum)",

but I got wrong answer! why?

my output for sample input is:
5 e2 e1 d1 d2 e2 e3

I think it's also right.

a1 h1 0 0 10 0 0 10

alot of time in debugging though ! :)

Edited by author 21.11.2015 16:12

package timus;

import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Scanner;

public class p1016_ {
    static Integer sx, sy, ex, ey;

    public static void main(String[] args) {
        InputStream is = System.in;
        Scanner sc = new Scanner(new InputStreamReader(is));
        String S = sc.next();
        char[] s = S.toCharArray();
        String E = sc.next();
        char[] e = E.toCharArray();
        sx = s[0]-'a';    sy = 8 - (s[1]-'0');
        ex = e[0]-'a';    ey = 8 - (e[1]-'0');
        int a[] = new int[6];
        for (int i=0; i<6; i++) {
            a[i] = sc.nextInt();
        }
        for (int i=0; i<24; i++) {
            int b[] = R[i];
            bottoms[i] = a[b[4]];
        }
        //=======
        for (int r=0; r<24; r++) {
            int next[] = moves[r];
            long costToMove[] = new long[4];
            for (int i=0; i<4; i++) {
                costToMove[i] = bottoms[next[i]];
            }
            for (int y=0; y<8; y++)
                for (int x=0; x<8; x++) {
                    totalCost_TO_YX24[y][x][r] = MAX;
                    //l r u d
                    for (int i=0; i<4; i++) {
                        costYX24lrud[y][x][r][i] = MAX;
                    }
                    if (x>0) costYX24lrud[y][x][r][0] = costToMove[0];
                    if (x<7) costYX24lrud[y][x][r][1] = costToMove[1];
                    if (y>0) costYX24lrud[y][x][r][2] = costToMove[2];
                    if (y<7) costYX24lrud[y][x][r][3] = costToMove[3];
                }
        }
        LinkedList<Integer> X = new LinkedList<Integer>();
        LinkedList<Integer> Y = new LinkedList<Integer>();
        LinkedList<Integer> St = new LinkedList<Integer>();
        LinkedList<Integer> Dir = new LinkedList<Integer>();
        totalCost_TO_YX24[sy][sx][0] = bottoms[0];

        LinkedList<Integer> X0 = new LinkedList<Integer>();
        LinkedList<Integer> Y0 = new LinkedList<Integer>();
        LinkedList<Integer> St0 = new LinkedList<Integer>();
        X0.add(sx); Y0.add(sy); St0.add(0);

        while( !X0.isEmpty() ) {
            Integer x = X0.removeFirst(); Integer y = Y0.removeFirst(); Integer st = St0.removeFirst();
            if (x>0) {X.add(x-1); Y.add(y); St.add(moves[st][0]); Dir.add(0);}
            if (x<7) {X.add(x+1); Y.add(y); St.add(moves[st][1]); Dir.add(1);}
            if (y>0) {X.add(x); Y.add(y-1); St.add(moves[st][2]); Dir.add(2);}
            if (y<7) {X.add(x); Y.add(y+1); St.add(moves[st][3]); Dir.add(3);}
            while ( !X.isEmpty() ) {
                Integer x1 = X.removeFirst();
                Integer y1 = Y.removeFirst();
                Integer st1 = St.removeFirst();
                int dir1 = Dir.removeFirst();
                long cost1 = costYX24lrud[y][x][st][dir1] + totalCost_TO_YX24[y][x][st];
                if (totalCost_TO_YX24[y1][x1][st1]>cost1) {
                    totalCost_TO_YX24[y1][x1][st1] = cost1;
                    prevDir[y1][x1][st1] = dir1;
                    prevSt[y1][x1][st1] = st;
                    X0.add(x1); Y0.add(y1); St0.add(st1);
                }
            }
        }
        long min = MAX;
        int st = -1;
        for (int i=0; i<24; i++) {
            if (min > totalCost_TO_YX24[ey][ex][i]) {
                min = totalCost_TO_YX24[ey][ex][i];
                st = i;
            }
        }
        //PRINT
        int x = ex; int y = ey;
        LinkedList<String> route = new LinkedList<String>();
        while(x != sx || y!= sy || st!=0) {
            route.add(0, tok(x,y));
            int dir = prevDir[y][x][st];
            st = prevSt[y][x][st];
            x += xS[reverse[dir]];
            y += yS[reverse[dir]];
        }
        route.add(0,tok(sx,sy));
        System.out.print(min);
        for (String mv: route) System.out.print(" " + mv);
    }//lrud     reversed RLDU

    static int prevDir[][][] = new int[8][8][24];
    static int prevSt[][][] = new int[8][8][24];
    static long[][][][] costYX24lrud = new long[8][8][24][4];
    static long[][][] totalCost_TO_YX24 = new long[8][8][24];
    static String tok(int x, int y){
        char ah = (char) ('a'+x);
        char oe = (char) ('1'+(7-y));
        return ah+""+oe;
    }
    static long MAX = Long.MAX_VALUE/3;
    static int xS[] = new int[]{-1,+1,0,0};
    static int yS[] = new int[]{0,0,-1,+1};
    static int reverse[] = new int[]{1,0,3,2};
//========================================================
    static int R[][] = new int[][]{    //front, back, up, right, down, left
        {0,1, 2,3,4,5}, {0,1, 5,2,3,4}, {0,1, 4,5,2,3}, {0,1, 3,4,5,2},
        {1,0, 2,5,4,3}, {1,0, 3,2,5,4}, {1,0, 4,3,2,5}, {1,0, 5,4,3,2},
        {3,5, 0,2,1,4}, {3,5, 4,0,2,1}, {3,5, 1,4,0,2}, {3,5, 2,1,4,0},
        {5,3, 0,4,1,2}, {5,3, 4,1,2,0}, {5,3, 1,2,0,4}, {5,3, 2,0,4,1},
        {4,2, 1,5,0,3}, {4,2, 3,1,5,0}, {4,2, 0,3,1,5}, {4,2, 5,0,3,1},
        {2,4, 1,3,0,5}, {2,4, 3,0,5,1}, {2,4, 0,5,1,3}, {2,4, 5,1,3,0},
    };
    //l r u d
    static int moves[][] = new int[][] {
        {3, 1, 18, 20}, {0, 2, 8, 14}, {1, 3, 22, 16}, {2, 0, 12, 10},
        {7, 5, 16, 22}, {4, 6, 14, 8}, {5, 7, 20, 18}, {6, 4, 10, 12},
        {11, 9, 5, 1}, {8, 10, 21, 19}, {9, 11, 3, 7}, {10, 8, 17, 23},
        {13, 15, 7, 3}, {14, 12, 23, 17}, {15, 13, 1, 5}, {12, 14, 19, 21},
        {19, 17, 2, 4}, {16, 18, 13, 11}, {17, 19, 6, 0}, {18, 16, 9, 15},
        {21, 23, 0, 6}, {22, 20, 15, 9}, {23, 21, 4, 2}, {20, 22, 11, 13},
    };

    static int bottoms[] = new int [24];

}

You can solve that with algo Djikstra.
We have 6!*8*8 vertex (hash of cube and point) .
And all vertexs have <=4 edges.
P.s. sry for English )

Edited by author 09.08.2014 16:51

Could you give me some tests?

What is Test#4?

Edited by author 06.04.2008 17:03

Who can  help  me?(give  me Test#1)
Thanks very much.
And where is "forward"?
I think the chessboard if like this:
 H G F E D C B A
1
2
3
4
5
6
7
8
Is it right?


Edited by author 24.08.2007 21:17

I use bfs like spfa and work in 0.031S

Hello, everybody!

I tryed to solve this problem for a week. I DO NOT KNOW WHAT TO DO. I can't think out anything :(

Thanks.

see <http://en.wikipedia.org/wiki/Chessboard>, the problem assumes otherwise.

does anyone know what's the Test 5 ?

Or can sent some tests.

Thx

I used SPFA, but failed in test 8. Who can help me?

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
int op[] = {0, 2, 1, 5, 6, 3, 4};
int r[7][7] = {
    {0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 4, 5, 6, 3},
    {0, 0, 0, 6, 3, 4, 5},
    {0, 6, 4, 0, 1, 0, 2},
    {0, 3, 5, 2, 0, 1, 0},
    {0, 4, 6, 0, 2, 0, 1},
    {0, 5, 3, 1, 0, 2, 0}
};
struct State {
    int x, y, b, f; //表示坐标(x, y)和底面和前面上的标号
} beg, end, que[24*8*8*100];
bool inque[9][9][7][7];
int dist[9][9][7][7], a[7], path[24*8*8*2];
int ans = 1000000000, last;
char s1[4], s2[4];

void eval(State &s, int x, int y, int b, int f)
{
    s.x = x, s.y = y, s.b = b, s.f = f;
}
bool check(State &s)
{
    if (s.x == 0 || s.x > 8 || s.y == 0 || s.y > 8) return 0;
    return 1;
}
void SPFA()
{
    int closed = 0, open = 2;
    memset(dist, 0x3f, sizeof(dist));
    eval(que[1], beg.x, beg.y, beg.b, beg.f);
    inque[beg.x][beg.y][beg.b][beg.f] = 1;
    dist[beg.x][beg.y][beg.b][beg.f] = 0;
    do {
        closed++;
        inque[que[closed].x][que[closed].y][que[closed].b][que[closed].f] = 0;
        if (que[closed].x == end.x && que[closed].y == end.y && dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] < ans) {
            ans = dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f];
            last = closed;
        }
        State newst;
        // forward
        eval(newst, que[closed].x, que[closed].y-1, que[closed].f, op[que[closed].b]);
        if (check(newst)) {
            if (dist[newst.x][newst.y][newst.b][newst.f] > dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b]) {
                dist[newst.x][newst.y][newst.b][newst.f] = dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b];
                if (!inque[newst.x][newst.y][newst.b][newst.f]) {
                    inque[newst.x][newst.y][newst.b][newst.f] = 1;
                    que[open] = newst;
                    path[open] = closed;
                    open++;
                }
            }
        }
        // right
        eval(newst, que[closed].x+1, que[closed].y, r[que[closed].b][que[closed].f], que[closed].f);
        if (check(newst)) {
            if (dist[newst.x][newst.y][newst.b][newst.f] > dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b]) {
                dist[newst.x][newst.y][newst.b][newst.f] = dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b];
                if (!inque[newst.x][newst.y][newst.b][newst.f]) {
                    inque[newst.x][newst.y][newst.b][newst.f] = 1;
                    que[open] = newst;
                    path[open] = closed;
                    open++;
                }
            }
        }
        // backward
        eval(newst, que[closed].x, que[closed].y+1, op[que[closed].f], que[closed].b);
        if (check(newst)) {
            if (dist[newst.x][newst.y][newst.b][newst.f] > dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b]) {
                dist[newst.x][newst.y][newst.b][newst.f] = dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b];
                if (!inque[newst.x][newst.y][newst.b][newst.f]) {
                    inque[newst.x][newst.y][newst.b][newst.f] = 1;
                    que[open] = newst;
                    path[open] = closed;
                    open++;
                }
            }
        }
        // left
        eval(newst, que[closed].x-1, que[closed].y, op[r[que[closed].b][que[closed].f]], que[closed].f);
        if (check(newst)) {
            if (dist[newst.x][newst.y][newst.b][newst.f] > dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b]) {
                dist[newst.x][newst.y][newst.b][newst.f] = dist[que[closed].x][que[closed].y][que[closed].b][que[closed].f] + a[newst.b];
                if (!inque[newst.x][newst.y][newst.b][newst.f]) {
                    inque[newst.x][newst.y][newst.b][newst.f] = 1;
                    que[open] = newst;
                    path[open] = closed;
                    open++;
                }
            }
        }
    } while (closed < open);
}
void print(int i)
{
    if (que[i].x == beg.x && que[i].y == beg.y) {
        printf("%d %c%d", ans+a[beg.b], beg.x+'a'-1, beg.y);
        return;
    }
    print(path[i]);
    printf(" %c%d", que[i].x+'a'-1, que[i].y);
}
int main()
{
    scanf("%s%s%d%d%d%d%d%d", s1, s2, &a[1], &a[2], &a[3], &a[4], &a[5], &a[6]);
    beg.x = s1[0] - 'a' + 1;
    beg.y = s1[1] - '0';
    beg.b = 5;
    beg.f = 1;
    end.x = s2[0] - 'a' + 1;
    end.y = s2[1] - '0';
    SPFA();
    print(last);
    printf("\n");
    return 0;
}

"Сначала даны начальная и конечная позиции на доске в стандартной шахматной нотации"

Standart chess notaion is http://www.google.ru/imglanding?q=%D1%88%D0%B0%D1%85%D0%BC%D0%B0%D1%82%D1%8B&imgurl=http://www.chess-master.net/images/play_chess.gif&imgrefurl=http://www.chess-master.net/articles/9.html&h=350&w=400&sz=58&tbnid=1oNeUJIo8F_rpM:&tbnh=109&tbnw=124&prev=/images%3Fq%3D%25D1%2588%25D0%25B0%25D1%2585%25D0%25BC%25D0%25B0%25D1%2582%25D1%258B&usg=__rCBt0C2kIGUCdnfufCJ5tdd96cw=&ei=blB-S6fEOZLj-QaRmPH8Cw&sa=X&oi=image_result&resnum=5&ct=image&ved=0CCIQ9QEwBA&start=0#tbnid=1oNeUJIo8F_rpM&start=0

but in this problem row numbered from top to bottom

sorry  my English is bad

Edited by author 19.02.2010 14:04

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;
}

=)

Edited by author 07.09.2009 03:15