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

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

AC java 0.14
Послано esbybb 21 ноя 2015 10:13
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];

}