/* 14:38- */ #include #include #define FORWARD 0 #define TOP 1 #define LEFT 2 #define RIGHT 3 #define BOTTOM 4 #define BACKWARD 5 int s_col, s_row, e_col, e_row; int sides[6]; /* backward, top, left, right, bottom, forward */ unsigned int fromStart[8][8][6][6][6]; unsigned char backTrackColumn[8][8][6][6][6]; unsigned char backTrackRow[8][8][6][6][6]; unsigned char backTrackBottom[8][8][6][6][6]; unsigned char backTrackLeft[8][8][6][6][6]; unsigned char backTrackBackward[8][8][6][6][6]; unsigned char PathC[8192]; unsigned char PathR[8192]; unsigned int PathLen; void to_left(int *bottom, int *left, int *backward) { int tmp; tmp = *bottom; *bottom = *left; *left = 5 - tmp; } void to_right(int *bottom, int *left, int *backward) { int tmp; tmp = *bottom; *bottom = 5 - *left; *left = tmp; } void to_forward(int *bottom, int *left, int *backward) { int tmp; tmp = *bottom; *bottom = 5 - *backward; *backward = tmp; } void to_backward(int *bottom, int *left, int *backward) { int tmp; tmp = *bottom; *bottom = *backward; *backward = 5 - tmp; } int main() { int i, j, k, l, m, d; char s[1024]; int dc[4] = {0, 1, 0, -1}; int dr[4] = {1, 0, -1, 0}; void (*dfunc[4])(int*,int*,int*) = {to_backward, to_right, to_forward, to_left}; void (*dback[4])(int*,int*,int*) = {to_forward, to_left, to_backward, to_right}; scanf("%s", s); s_col = s[0] - 'a'; s_row = s[1] - '1'; scanf("%s", s); e_col = s[0] - 'a'; e_row = s[1] - '1'; scanf("%d %d %d %d %d %d", &sides[FORWARD], &sides[BACKWARD], &sides[TOP], &sides[RIGHT], &sides[BOTTOM], &sides[LEFT]); for (i = 0; i < 8; i++) { for (j = 0; j < 8; j++) { for (k = 0; k < 6; k++) { for (l = 0; l < 6; l++) { for (m = 0; m < 6; m++) { fromStart[i][j][k][l][m] = INT_MAX / 2; } } } } } fromStart[s_col][s_row][BOTTOM][LEFT][BACKWARD] = 0; /* Dijkstra */ while (1) { int from; int MinDist = INT_MAX / 2; int MinDistColumn, MinDistRow, MinDistBottom, MinDistLeft, MinDistBackward; int BackColumn, BackRow, BackBottom, BackLeft, BackBackward; for (i = 0; i < 8; i++) { /* column */ for (j = 0; j < 8; j++) { /* row */ for (k = 0; k < 6; k++) { /* bottom */ for (l = 0; l < 6; l++) { /* left */ for (m = 0; m < 6; m++) { /* backward */ if (fromStart[i][j][k][l][m] < INT_MAX / 2) { #if 0 printf(">> %c%d %d %d %d (%d)\n", i+'a', j+1, k, l, m, fromStart[i][j][k][l][m]); #endif for (d = 0; d < 4; d++) { int updated = 0; if (i+dc[d]<0 || i+dc[d]>7 || j+dr[d]<0 || j+dr[d]>7) { continue; } from = fromStart[i][j][k][l][m]; dfunc[d](&k, &l, &m); i += dc[d]; j += dr[d]; #if 0 printf(" )) %c%d %d %d %d (%d) %d\n", i+'a', j+1, k, l, m, from + sides[k], fromStart[i][j][k][l][m]); #endif if (from + sides[k] < MinDist && fromStart[i][j][k][l][m] == INT_MAX / 2) { #if 0 printf(" >> %c%d %d %d %d (%d)\n", i+'a', j+1, k, l, m, from + sides[k]); #endif MinDist = from + sides[k]; MinDistColumn = i; MinDistRow = j; MinDistBottom = k; MinDistLeft = l; MinDistBackward = m; updated = 1; } i -= dc[d]; j -= dr[d]; dback[d](&k, &l, &m); if (updated) { BackColumn = i; BackRow = j; BackBottom = k; BackLeft = l; BackBackward = m; } } } } } } } } #if 0 printf("Next: %c%d %d %d %d (%d)\n", MinDistColumn + 'a', MinDistRow + 1, MinDistBottom, MinDistLeft, MinDistBackward, MinDist); fflush(stdout); #endif fromStart[MinDistColumn][MinDistRow] [MinDistBottom][MinDistLeft][MinDistBackward] = MinDist; backTrackColumn[MinDistColumn][MinDistRow] [MinDistBottom][MinDistLeft][MinDistBackward] = BackColumn; backTrackRow[MinDistColumn][MinDistRow] [MinDistBottom][MinDistLeft][MinDistBackward] = BackRow; backTrackBottom[MinDistColumn][MinDistRow] [MinDistBottom][MinDistLeft][MinDistBackward] = BackBottom; backTrackLeft[MinDistColumn][MinDistRow] [MinDistBottom][MinDistLeft][MinDistBackward] = BackLeft; backTrackBackward[MinDistColumn][MinDistRow] [MinDistBottom][MinDistLeft][MinDistBackward] = BackBackward; if (s_col == e_col && s_row == e_row) { MinDist = 0; MinDistColumn = s_col; MinDistRow = s_row; printf("%d", sides[BOTTOM]); printf(" %c%d\n", MinDistColumn + 'a', MinDistRow + 1); break; } if (MinDistColumn == e_col && MinDistRow == e_row) { printf("%d", MinDist + sides[BOTTOM]); PathLen = 0; while (1) { PathC[PathLen] = MinDistColumn; PathR[PathLen] = MinDistRow; PathLen++; if (MinDistColumn == s_col && MinDistRow == s_row) { break; } BackColumn = MinDistColumn; BackRow = MinDistRow; BackBottom = MinDistBottom; BackLeft = MinDistLeft; BackBackward = MinDistBackward; MinDistColumn = backTrackColumn[BackColumn] [BackRow][BackBottom][BackLeft][BackBackward]; MinDistRow = backTrackRow[BackColumn] [BackRow][BackBottom][BackLeft][BackBackward]; MinDistBottom = backTrackBottom[BackColumn] [BackRow][BackBottom][BackLeft][BackBackward]; MinDistLeft = backTrackLeft[BackColumn] [BackRow][BackBottom][BackLeft][BackBackward]; MinDistBackward = backTrackBackward[BackColumn] [BackRow][BackBottom][BackLeft][BackBackward]; } for (i = PathLen - 1; i >= 0; i--) { printf(" %c%d", PathC[i] + 'a', PathR[i] + 1); } printf("\n"); break; } } return 0; }