1 /*
2 * File: 1016. A Cube on the Walk
3 * Author: xiaotian @ hnu
4 * Created on 2010年9月28日, 上午9:26
5 * 解题：bfs，很基础的。可以看作在一个图上跑最短路，
6 * 关健是建图，本人愚拙，手打整个图。
7 */
8
9 #include<stdio.h>
10 #include<iostream>
11 #include<string.h>
12 #include<queue>
13 #define inf 0x3fffffff
14 using namespace std;
15 const int dy[4]={0,-1,0,1};
16 const int dx[4]={1,0,-1,0};
17 int map[6][6][4][2]=
18 {{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,2,2,1,5,2,4,0,4,3,3,1,2,3,5,0,5,4,4,1,3,4,2,0,2,5,5,1,4,5,3,0},
19 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,2,2,0,3,2,4,1,2,3,3,0,4,3,5,1,3,4,4,0,5,4,2,1,4,5,5,0,2,5,3,1},
20 {5,0,0,4,3,0,1,2,3,1,1,4,5,1,0,2,0,0,0,0,0,0,0,0,0,3,3,4,1,3,5,2,0,0,0,0,0,0,0,0,1,5,5,4,0,5,3,2},
21 {2,0,0,5,4,0,1,3,4,1,1,5,2,1,0,3,1,2,2,5,0,2,4,3,0,0,0,0,0,0,0,0,0,4,4,5,1,4,2,3,0,0,0,0,0,0,0,0},
22 {3,0,0,2,5,0,1,4,5,1,1,2,3,1,0,4,0,0,0,0,0,0,0,0,1,3,3,2,0,3,5,4,0,0,0,0,0,0,0,0,0,5,5,2,1,5,3,4},
23 {4,0,0,3,2,0,1,5,2,1,1,3,4,1,0,5,0,2,2,3,1,2,4,5,0,0,0,0,0,0,0,0,1,4,4,3,0,4,2,5,0,0,0,0,0,0,0,0}};
24 int num[6];
25 int g[10][10][6][6];
26 struct point
27 {
28 int x,y,b,f;
29 point(int xx=0,int yy=0,int bb=0,int ff=0):x(xx),y(yy),b(bb),f(ff){}
30 };
31 struct node
32 {
33 int x,y;
34 node(int xx=0,int yy=0):x(xx),y(yy){}
35 };
36 node out[1000];
37 point pre[10][10][6][6];
38 point s,t;
39 int ok(int x,int y){ return x>=0 && x<8 && y>=0 && y<8; }
40 void bfs()
41 {
42 for(int i=0;i<10;i++)
43 for(int j=0;j<10;j++)
44 for(int k=0;k<6;k++)
45 for(int l=0;l<6;l++) g[i][j][k][l]=inf;
46 queue<point>q;
47 g[s.x][s.y][s.b][s.f]=num[s.b];
48 pre[s.x][s.y][s.b][s.f]=point(-1,-1,-1,-1);
49 q.push(s);
50 while(!q.empty())
51 {
52 point p=q.front(); q.pop();
53 int k=g[p.x][p.y][p.b][p.f];
54 for(int i=0;i<4;i++)
55 {
56 int x=p.x+dx[i],y=p.y+dy[i];
57 int b=map[p.b][p.f][i][0];
58 int f=map[p.b][p.f][i][1];
59 if(ok(x,y) && k+num[b]<g[x][y][b][f])
60 {
61 pre[x][y][b][f]=p;
62 q.push(point(x,y,b,f));
63 g[x][y][b][f]=k+num[b];
64 }
65 }
66 }
67 }
68 int main() {
69 char s1[10],s2[10];
70 while(scanf("%s %s",s1,s2)!=EOF)
71 {
72 s=point(s1[0]-'a',s1[1]-'1',4,0);
73 t=point(s2[0]-'a',s2[1]-'1',-1,-1);
74 for(int i=0;i<6;i++) scanf("%d",num+i);
75 bfs();
76 int ans=inf;
77 for(int i=0;i<6;i++)
78 for(int j=0;j<6;j++)
79 {
80 if(ans>g[t.x][t.y][i][j])
81 {
82 ans=g[t.x][t.y][i][j];
83 t.b=i;
84 t.f=j;
85 }
86 }
87 printf("%d ",ans);
88 out[0]=node(t.x,t.y);
89 int tot=1;
90 point k=t;
91 while(k.x!=-1 && k.y!=-1 && k.b!=-1 && k.f!=-1)
92 {
93 k=pre[k.x][k.y][k.b][k.f];
94 out[tot++]=node(k.x,k.y);
95 }
96 tot--;
97 for(int i=tot-1;i>=0;i--)
98 {
99 printf("%c%d",out[i].x+'a',out[i].y+1);
100 if(out[i].x==t.x && out[i].y==t.y) { printf("\n"); break; }
101 else printf(" ");
102 }
103 }
104 return 0;
105 }