P1930 亚瑟王的宫殿

2024-03-04 07:38

文章标签 宫殿亚瑟王 p1930

本文主要是介绍P1930 亚瑟王的宫殿，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题主要是玄学输入+玄学理解+玄学时间复杂度+玄学定理呀QAQ…
至于玄学理解其他题解已经讲得很清楚了呀，主要还是让大家看看我的玄学代码呀QAQ…

//先玄学理解呀
const z:array[1..8,1..2]of -2..2=((1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1));
var i,j,k,ix,iy:longint;m,n,h,t,sum,q:longint;kingx,kingy:longint;x_ch:array[char]of longint;min,p:array[-1..100,-1..100]of longint;x,y,u:array[0..10000]of longint;main:longint=maxlongint;boo:array[-1..100,-1..100]of boolean;ans:array[-1..30,-1..50,-1..30,-1..50] of longint;s:string;ch:char;
function mine(m,n:longint):longint;//min
beginif m>n then exit(n) else exit(m);
end;
function max(m,n:longint):longint;//max
beginif m>n then exit(m) else exit(n);
end;
procedure find(x1,y1:longint);//以x1,y1为终点呀QAQ
var i,j,k,pd:longint;
beginfor i:=-2 to 2 do//玄学定理，不知道是谁怎么的呀for j:=-2 to 2 do//接国王的位置一定在国王旁边2格内if boo[kingx+i,kingy+j] thenbeginpd:=0;for k:=1 to sum doinc(pd,ans[x1,y1,x[k],y[k]]);main:=mine(main,pd+max(abs(x1-kingx),abs(y1-kingy)));//当国王直接走到终点for k:=1 to sum dobeginmain:=mine(main,pd-ans[x1,y1,x[k],y[k]]{骑士直接去终点}+ans[kingx+i,kingy+j,x[k],y[k]]{骑士到接的位置}+ans[x1,y1,kingx+i,kingy+j]{从接的位置到终点}+max(abs(i),abs(j))){国王到接的位置};//第k个骑士去接国王呀end;end;
end;
beginreadln(m,n);k:=m;m:=n;n:=k;for ch:='A' to 'Z' do x_ch[ch]:=ord(ch)-ord('A')+1;read(ch,k);kingx:=x_ch[ch];kingy:=k;//读入国王位置呀QAQfor ix:=1 to m dofor iy:=1 to n dofor i:=1 to m dofor j:=1 to n do ans[ix,iy,i,j]:=123123123;//赋初值for ix:=1 to m do//用bfs计算每两个点之间的最短步数,四次居然不超呀，玄学时间复杂度....for iy:=1 to n dobeginx[1]:=ix;y[1]:=iy;u[1]:=0;h:=1;t:=1;for i:=1 to m dofor j:=1 to n doboo[i,j]:=true;boo[ix,iy]:=false;ans[ix,iy,ix,iy]:=0;repeatfor i:=1 to 8 doif boo[x[t]+z[i,1],y[t]+z[i,2]] thenbegininc(h);x[h]:=x[t]+z[i,1];y[h]:=y[t]+z[i,2];u[h]:=u[t]+1;ans[ix,iy,x[h],y[h]]:=u[h];//保存最优解呀boo[x[h],y[h]]:=false;end;inc(t);until t>h;end;while not eof do//玄学读入beginreadln(s);//字符串，真麻烦...for i:=1 to length(s) dobeginif (s[i] in ['A'..'Z']) thenbegininc(sum);x[sum]:=x_ch[s[i]];k:=0;j:=i+2;while (s[j] in ['0'..'9']) and (j<=length(s))dobegink:=k*10+ord(s[j])-48;inc(j);end;y[sum]:=k;end;end;end;if sum=0 then begin write(0); exit; end;for i:=1 to m dofor j:=1 to n do boo[i,j]:=true;for i:=1 to m dofor j:=1 to n dobeginfind(i,j);//找最优解呀QAQend;write(main);//输出
end.