如果发现广告等破坏行为，请尽量将条目恢复到较早的版本而不是把相应内容直接删除，谢谢合作。
URAL/1016
来自"NOCOW"
< URAL
//zhujf553 #include <iostream> #include <stdlib.h> #include <string.h> #include <string> using namespace std; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; const int jc[6] = {1, 1, 2, 6, 24, 120}; struct Cq { int x, y, s[7], ss, v; }q[100000]; struct Cq2 { int x, y, k; }g[10][10][721]; bool inq[10][10][721]; int d[10][10][721]; int sx, sy, tx, ty, vv[7]; void roll(int o[], int d) { if(d == 0) d = o[5], o[5] = o[4], o[4] = o[3], o[3] = o[6], o[6] = d; else if(d == 1) d = o[5], o[5] = o[2], o[2] = o[3], o[3] = o[1], o[1] = d; else if(d == 2) d = o[5], o[5] = o[6], o[6] = o[3], o[3] = o[4], o[4] = d; else if(d == 3) d = o[5], o[5] = o[1], o[1] = o[3], o[3] = o[2], o[2] = d; } int calc(int o[]) { bool u[7]; int i, j, k, l, s; s = 0, j = 0; memset(u, 1, sizeof(u)); for(i = 5 ; i >= 0 ; i--) { l = 0; j++; u[o[i]] = false; for(k = 1 ; k <= o[i] ; k++) if(u[k]) l++; s += jc[i] * l; } return s; } void print(int x, int y, int k) { if(x == sx && y == sy) { cout << ' ' << char(x + 'a') << char(y + '1'); return; } print(g[x][y][k].x, g[x][y][k].y, g[x][y][k].k); cout << ' ' << char(x + 'a') << char(y + '1'); } void work() { string t1, t2; int i, j, k, l; int sm[7]; cin >> t1 >> t2; sx = t1[0] - 'a', sy = t1[1] - '1'; tx = t2[0] - 'a', ty = t2[1] - '1'; k = 0; for(i = 1 ; i <= 6 ; i++) cin >> vv[i], q[0].s[i] = i; int op = 0, cl = 1; q[0].x = sx, q[0].y = sy, q[0].v = 0, q[0].ss = calc(q[0].s); memset(d, 0x0f, sizeof(d)); memset(g, 0xff, sizeof(g)); d[sx][sy][q[0].ss] = vv[q[0].s[5]]; inq[sx][sy][q[0].ss] = true; while(op < cl) { int tt[7], tk[7]; memcpy(tt, q[op].s, sizeof(tt)); for(k = 0 ; k <= 3 ; k++) { if(q[op].x + dx[k] < 0 || q[op].x + dx[k] > 7) continue; if(q[op].y + dy[k] < 0 || q[op].y + dy[k] > 7) continue; memcpy(tk, tt, sizeof(tt)); roll(tk, k); j = calc(tk); if(d[q[op].x + dx[k]][q[op].y + dy[k]][j] > d[q[op].x][q[op].y][q[op].ss] + vv[tk[5]]) { d[q[op].x + dx[k]][q[op].y + dy[k]][j] = d[q[op].x][q[op].y][q[op].ss] + vv[tk[5]]; g[q[op].x + dx[k]][q[op].y + dy[k]][j].x = q[op].x; g[q[op].x + dx[k]][q[op].y + dy[k]][j].y = q[op].y; g[q[op].x + dx[k]][q[op].y + dy[k]][j].k = q[op].ss; if(!inq[q[op].x + dx[k]][q[op].y + dy[k]][j]) { inq[q[op].x + dx[k]][q[op].y + dy[k]][j] = true; q[cl].x = q[op].x + dx[k]; q[cl].y = q[op].y + dy[k]; q[cl].ss = j; memcpy(q[cl].s, tk, sizeof(tk)); cl++; } } } inq[q[op].x][q[op].y][q[op].ss] = false; op++; } l = 99999999, k = 0; for(j = 0 ; j <= 720 ; j++) if(d[tx][ty][j] < l) l = d[tx][ty][j], k = j; cout << l; print(tx, ty, k); cout << endl; } int main() { work(); return 0; }
by cgangee http://www.cgang.tk
const maxn=64*720; biao:array[1..4,1..2]of longint= ((0,1),(0,-1),(-1,0),(1,0)); next:array[1..4,1..6]of longint= ( (5,3,1,4,2,6), (3,5,2,4,1,6), (1,2,4,5,6,3), (1,2,6,3,4,5) ); jie:array[0..5]of longint=(1,1,2,6,24,120); type arr=array[1..6]of longint; var i,j,k,m,n,l:longint; c:array[1..5]of char; d:array[1..6]of longint; v:array[1..8,1..8,0..720]of boolean; dist:array[1..8,1..8,0..720]of longint; g:array[1..8,1..8,0..720]of record x,y,z:longint; end; q:array[0..maxn]of record x,y,kt:longint; a:arr; end; used:array[1..6]of boolean; x,y,head,tail:longint; temp:arr; min:longint; function kt:longint; var i,j,k,m,n:longint; begin n:=0; j:=0; fillchar(used,sizeof(used),true); for i:=5 downto 0 do begin m:=0; inc(j); used[temp[j]]:=false; for k:=1 to temp[j] do if used[k] then inc(m); n:=n+jie[i]*m; end; kt:=n; end; procedure print(i,j,k:longint); begin if (i=0)or(j=0) then exit; print(g[i,j,k].x,g[i,j,k].y,g[i,j,k].z); write(' ',chr(i+ord('a')-1),j); end; begin for i:=1 to 5 do read(c[i]); for i:=1 to 6 do read(d[i]); fillchar(dist,sizeof(dist),127); head:=0; tail:=1; q[1].x:=ord(c[1])-ord('a')+1; q[1].y:=ord(c[2])-ord('0'); q[1].kt:=0; for i:=1 to 6 do q[1].a[i]:=i; dist[q[1].x,q[1].y,0]:=d[5]; while head<tail do begin head:=(head+1)mod maxn; for i:=1 to 4 do begin x:=q[head].x+biao[i,1]; y:=q[head].y+biao[i,2]; if (x>0)and(y>0)and(x<9)and(y<9) then begin for j:=1 to 6 do temp[j]:=q[head].a[next[i,j]]; k:=kt; if dist[q[head].x,q[head].y,q[head].kt]+d[temp[5]]<dist[x,y,k] then begin dist[x,y,k]:=dist[q[head].x,q[head].y,q[head].kt]+d[temp[5]]; g[x,y,k].x:=q[head].x; g[x,y,k].y:=q[head].y; g[x,y,k].z:=q[head].kt; if not v[x,y,k] then begin tail:=(tail+1)mod maxn; q[tail].x:=x; q[tail].y:=y; q[tail].kt:=k; q[tail].a:=temp; v[x,y,k]:=true; end; end; end; end; v[q[head].x,q[head].y,q[head].kt]:=false; end; min:=maxlongint; x:=ord(c[4])-ord('a')+1; y:=ord(c[5])-ord('0'); for i:=0 to 720 do if dist[x,y,i]<=min then begin k:=i; min:=dist[x,y,i]; end; write(dist[x,y,k]); print(x,y,k); end.
withflying:这里有程序,与大致思路 http://withflying.com/?p=54 [1]
dejiyu:我的SPFA程序
program djy; const opposite:array[1..6] of longint=(2,1,5,6,3,4); {预处理对称面} var num:array[1..6] of longint; dis,nexta,nextb,nextc,nextx,nexty:array[1..6,1..6,1..6,1..8,1..8] of longint; {dis:距离；next:静态链表，队列中的下一个元素} flag:array[0..6,0..6,0..6,0..8,0..8] of boolean; {是否在队列中} way:array[1..6,1..6,1..6,1..8,1..8] of string; {字符串存储行走路线} startx,starty,finalx,finaly,ans:longint; a,b,c,x,y:longint; aa,bb,cc,xx,yy:longint; lasta,lastb,lastc,lastx,lasty:longint; now:char; procedure init; var i:longint; ch:char; begin read(ch); starty:=ord(ch)-96; read(ch); startx:=ord(ch)-48; read(ch); read(ch); finaly:=ord(ch)-96; read(ch); finalx:=ord(ch)-48; for i:=1 to 6 do read(num[i]); end; procedure prepare; begin for a:=1 to 6 do for b:=1 to 6 do for c:=1 to 6 do for x:=1 to 8 do for y:=1 to 8 do dis[a,b,c,x,y]:=maxlongint; end; procedure new; begin if (xx<1) or (xx>8) or (yy<1) or (yy>8) then exit; if dis[a,b,c,x,y]+num[opposite[bb]]<dis[aa,bb,cc,xx,yy] then {更新距离} begin dis[aa,bb,cc,xx,yy]:=dis[a,b,c,x,y]+num[opposite[bb]]; way[aa,bb,cc,xx,yy]:=way[a,b,c,x,y]+now; if flag[aa,bb,cc,xx,yy]=false then {加入队列} begin flag[aa,bb,cc,xx,yy]:=true; nexta[lasta,lastb,lastc,lastx,lasty]:=aa; nextb[lasta,lastb,lastc,lastx,lasty]:=bb; nextc[lasta,lastb,lastc,lastx,lasty]:=cc; nextx[lasta,lastb,lastc,lastx,lasty]:=xx; nexty[lasta,lastb,lastc,lastx,lasty]:=yy; lasta:=aa; lastb:=bb; lastc:=cc; lastx:=xx; lasty:=yy; end; end; end; procedure workleft; {向左翻} begin aa:=a; bb:=c; cc:=opposite[b]; xx:=x; yy:=y-1; now:='l'; new; end; procedure workright; {向右翻} begin aa:=a; bb:=opposite[c]; cc:=b; xx:=x; yy:=y+1; now:='r'; new; end; procedure workforward; {向前翻} begin aa:=b; bb:=opposite[a]; cc:=c; xx:=x-1; yy:=y; now:='f'; new; end; procedure workbackward; {向后翻} begin aa:=opposite[b]; bb:=a; cc:=c; xx:=x+1; yy:=y; now:='b'; new; end; procedure main; begin a:=1; b:=3; c:=4; x:=startx; y:=starty; lasta:=a; lastb:=b; lastc:=c; lastx:=x; lasty:=y; dis[a,b,c,x,y]:=num[opposite[b]]; flag[a,b,c,x,y]:=true; while flag[a,b,c,x,y]=true do begin workleft; workright; workforward; workbackward; flag[a,b,c,x,y]:=false; aa:=a; bb:=b; cc:=c; xx:=x; yy:=y; a:=nexta[aa,bb,cc,xx,yy]; {指针跳到队列中的下一个元素} b:=nextb[aa,bb,cc,xx,yy]; c:=nextc[aa,bb,cc,xx,yy]; x:=nextx[aa,bb,cc,xx,yy]; y:=nexty[aa,bb,cc,xx,yy]; end; end; procedure print; var i:longint; s:string; begin ans:=maxlongint; for a:=1 to 6 do for b:=1 to 6 do for c:=1 to 6 do if dis[a,b,c,finalx,finaly]<ans then begin ans:=dis[a,b,c,finalx,finaly]; s:=way[a,b,c,finalx,finaly]; end; x:=startx; y:=starty; write(ans,' ',chr(y+96),x); for i:=1 to length(s) do {照行进路线输出路径} begin if s[i]='l' then y:=y-1; if s[i]='r' then y:=y+1; if s[i]='f' then x:=x-1; if s[i]='b' then x:=x+1; write(' ',chr(y+96),x); end; end; begin init; prepare; main; print; end.
我的大致思想是利用BFS,其实也就是SPFA吧
visit:保证同一结点在队列中同时出现多次
flag:记录每个位置上的最优解
dirc:记录在向4个方向上旋转后,骰子各个面的情况和坐标的位移
以下是代码:
program P1016_YoungBoy; const limit=19920110; dirc:array [1..4,1..8] of longint= ((5,3,1,4,2,6,1,0),(3,5,2,4,1,6,-1,0),(1,2,6,3,4,5,0,1),(1,2,4,5,6,3,0,-1)); maxn=4000; ctn:array ['a'..'h'] of longint=(1,2,3,4,5,6,7,8); ntc='abcdefgh'; type cube=array [1..6] of longint; pnode=record zt:cube; last,x,y:longint; end; var flag,visit:array [1..8,1..8,1..6,1..6] of longint; data:cube; p:array [1..maxn] of pnode; n,m,tx,ty,op,cl,min,ans:longint; procedure Init; var ic:char; int,i:longint; begin read(ic); p[1].y:=ctn[ic]; read(p[1].x); read(ic); read(ic); ty:=ctn[ic]; read(tx); for i:=1 to 6 do read(data[i]); end; procedure Print; procedure PrintRoad(ps:longint); var i:longint; begin with p[ps] do begin if last<>0 then PrintRoad(last); write(ntc[y],x,' '); end; end; begin writeln(flag[tx,ty,p[ans].zt[1],p[ans].zt[3]]); PrintRoad(ans); end; procedure Expand(fx:longint); var nzt:cube; i,nx,ny,nt:longint; begin with p[op] do begin for i:=1 to 6 do nzt[i]:=zt[dirc[fx,i]]; nx:=x+dirc[fx,7]; ny:=y+dirc[fx,8];{算出新的骰子状态,坐标} if (nx in [1..8]) and (ny in [1..8]) and (flag[nx,ny,nzt[1],nzt[3]]>flag[x,y,zt[1],zt[3]]+data[nzt[5]]) then begin flag[nx,ny,nzt[1],nzt[3]]:=flag[x,y,zt[1],zt[3]]+data[nzt[5]]; {更新当前值} if visit[nx,ny,nzt[1],nzt[3]]=0 then {判断结点是否在队列中} begin inc(cl); nt:=cl; visit[nx,ny,nzt[1],nzt[3]]:=cl; p[cl].zt:=nzt; p[cl].last:=op; p[cl].x:=nx; p[cl].y:=ny; end else begin p[visit[nx,ny,nzt[1],nzt[3]]].last:=op; {如果已经在队列中,则更新结点的father} nt:=visit[nx,ny,nzt[1],nzt[3]]; end; if (nx=tx) and (ny=ty) and (flag[nx,ny,nzt[1],nzt[3]]<min) then {得到一个更优的解} begin min:=flag[nx,ny,nzt[1],nzt[3]]; ans:=nt; end; end; end; end; procedure BFS; var i:longint; begin repeat for i:=1 to 4 do Expand(i); visit[p[op].x,p[op].y,p[op].zt[1],p[op].zt[3]]:=0; {表示结点出队列} inc(op); until op>cl; end; procedure First; {初始化} var i,j,k,l:longint; begin for i:=1 to 8 do for j:=1 to 8 do for k:=1 to 6 do for l:=1 to 6 do flag[i,j,k,l]:=limit; {哪位大牛能够告诉我如何不用循环把数组全部赋值成一个较大的数?} cl:=1; op:=1; p[1].last:=0; flag[p[1].x,p[1].y,1,3]:=data[5]; for i:=1 to 6 do p[1].zt[i]:=i; min:=limit; fillchar(visit,sizeof(visit),0); visit[p[1].x,p[1].y,1,3]:=1; end; procedure Main; begin First; BFS; end; begin Init; Main; Print; end.
回复程序中的问题：只要用fillchar(f,sizeof(f),十六进制数)就行了。至于十六进制数是多少，多用的是$7f，自己可以尝试。
回复程序中的问题: fillchar(f,sizeof(f),127)也可以，但不是最大的数。
peng tian yi # include<iostream> using namespace std; const int maxn=30,maxm=300000; const int oppt[7]={0,2,1,5,6,3,4};//记录相反的面 int d[maxn][maxn][7][7][7]/*下，后，右*/,dfa[maxn][maxn][7][7][7]; bool flag[maxn][maxn][7][7][7]; int li[8],head=1,tail=1; /*前，后，上，右，下，左*/; struct brr { int x,y; }ans[maxm]; struct arr { int x,y,xia,hou,you,f; }h[maxm]; void rudui(int x,int y,int xia,int you,int hou) { if (flag[x][y][xia][hou][you])//原来不在队列，则入队列 { tail++; h[tail].x=x;h[tail].y=y;h[tail].xia=xia;h[tail].hou=hou;h[tail].you=you; h[tail].f=head; dfa[x][y][xia][hou][you]=tail; flag[x][y][xia][hou][you]=false; } else //在在则更新原来的状态 { int p=dfa[x][y][xia][hou][you]; h[p].f=head; //开始没有这句话，WA在第8个点 } } void workleft() { int xia,hou,you,x,y; xia=oppt[h[head].you];you=h[head].xia;hou=h[head].hou;x=h[head].x;y=h[head].y-1; if (y<1) return; if (d[x][y][xia][hou][you]>d[x][y+1][h[head].xia][h[head].hou][h[head].you]+li[xia]) { d[x][y][xia][hou][you]=d[x][y+1][h[head].xia][h[head].hou][h[head].you]+li[xia]; rudui(x,y,xia,you,hou); } } void workright() { int xia,hou,you,x,y; xia=h[head].you;you=oppt[h[head].xia];hou=h[head].hou;x=h[head].x;y=h[head].y+1; if (y>8) return; if (d[x][y][xia][hou][you]>d[x][y-1][h[head].xia][h[head].hou][h[head].you]+li[xia]) { d[x][y][xia][hou][you]=d[x][y-1][h[head].xia][h[head].hou][h[head].you]+li[xia]; rudui(x,y,xia,you,hou); } } void workfront() { int xia,hou,you,x,y; xia=oppt[h[head].hou];you=h[head].you;hou=h[head].xia;x=h[head].x-1;y=h[head].y; if (x<1) return; if (d[x][y][xia][hou][you]>d[x+1][y][h[head].xia][h[head].hou][h[head].you]+li[xia]) { d[x][y][xia][hou][you]=d[x+1][y][h[head].xia][h[head].hou][h[head].you]+li[xia]; rudui(x,y,xia,you,hou); } } void workbehind() { int xia,hou,you,x,y; xia=h[head].hou;you=h[head].you;hou=oppt[h[head].xia];x=h[head].x+1;y=h[head].y; if (x>8) return; if (d[x][y][xia][hou][you]>d[x-1][y][h[head].xia][h[head].hou][h[head].you]+li[xia]) { d[x][y][xia][hou][you]=d[x-1][y][h[head].xia][h[head].hou][h[head].you]+li[xia]; rudui(x,y,xia,you,hou); } } int main() { int i,j,k,l,m; char st1[5],st2[5]; scanf("%s%s",st1,st2); int sx,sy,ex,ey; sy=st1[0]-96; sx=st1[1]-48; ey=st2[0]-96; ex=st2[1]-48; for (i=1;i<=6;i++) scanf("%d",&li[i]); h[head].x=sx;h[head].y=sy; h[head].xia=5;h[head].hou=2;h[head].you=4; memset(flag,true,sizeof(flag)); flag[sx][sy][5][2][4]=false; memset(d,50,sizeof(d)); d[sx][sy][5][2][4]=li[5]; while (head<=tail) { workleft(); workright(); workfront(); workbehind();//BFS flag[h[head].x][h[head].y][h[head].xia][h[head].hou][h[head].you]=true; head++; } int min=2147483647,t=0; for (i=1;i<=6;i++) for (j=1;j<=6;j++) for (k=1;k<=6;k++) if (d[ex][ey][i][j][k]<min) { t=dfa[ex][ey][i][j][k]; min=d[ex][ey][i][j][k]; } printf("%d ",min); m=0; while (t!=0) { ans[++m].x=h[t].x; ans[m].y=h[t].y; t=h[t].f; } for (i=m;i>0;i--) printf("%c%d ",ans[i].y+96,ans[i].x); return 0; } //SPFA
