road.htm

常用经典算法及讲解

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>num:=num+1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>snode:=queue2[tmp]^;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>sd_to_ext(snode,node2);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>writeln(f1,'num=',num);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>prtnode(node2);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>tmp:=snode.parent;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>writeln('OK!!!');</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>close(f1);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>for i:=0 to range2 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>freemem(queue[i],sizeof(queue[i]^));</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>for i:=0 to range2 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>freemem(queue2[i],sizeof(queue2[i]^));</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>halt(0);</span></p>

<p class=MsoPlainText><span lang=EN-US>end;{5}</span></p>

<p class=MsoPlainText><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US>function judge2(arr:arr1):boolean;<span
style="mso-spacerun: yes">&nbsp; </span>{No.6 排除若干不可能情形，以减少入队的结点数}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>var i3:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>begin {6}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>judge2:=true;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if(arr[2,1]=9)and(arr[3,2]=9)and(arr[1,3] in
b1)and(arr[1,1]=0)</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp; </span>and(arr[1,2]=0) then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>judge2:=false;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if(arr[2,2]=9)and(arr[3,3]=9)and(arr[1,1] in
b1)and(arr[1,4] in b1)</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>and(arr[1,2]=0)and(arr[1,3]=0) then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>judge2:=false;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;
</span>if(arr[1,1]=9)and(arr[2,2]=9)and((arr[1,3]=0)or(arr[1,4]=0))</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>and(arr[2,3]=8)<span
style="mso-spacerun: yes">&nbsp; </span>then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>judge2:=false;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>for i3:=1 to 2 do {利用对称性，可限定在前两行，曹操只能向左或向中间移动}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>if (arr[i3,4]=9) then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>judge2:=false;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;
</span>if(arr[1,2]=9)and(arr[2,3]=9)and(arr[1,1]=0)and(arr[1,4]=0)</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>judge2:=false;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>end; {6}</span></p>

<p class=MsoPlainText><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US>function
judge3(arr01:arr1;arr02:arr2):boolean;<span style="mso-spacerun: yes">&nbsp;
</span>{No.7 判断是否等于已入队结点}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>var i3,j3:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>begin {7}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>judge3:=true;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp; </span>for i3:=1 to 5 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for j3:=1 to 4 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>if
(arr01[i3,j3] in b1) then<span style="mso-spacerun: yes">&nbsp;
</span>arr01[i3,j3]:=2;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>if
(arr02[i3,j3] in b1) then<span style="mso-spacerun: yes">&nbsp;
</span>arr02[i3,j3]:=2;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>if
(arr01[i3,j3]&lt;&gt;arr02[i3,j3]) then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>begin<span style="mso-spacerun: yes">&nbsp; </span>judge3:=false;<span
style="mso-spacerun: yes">&nbsp; </span>exit;<span style="mso-spacerun:
yes">&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>end;{7}</span></p>

<p class=MsoPlainText><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US>procedure toqueue(node3:node_ext;
i,j,kz3:integer); {No.8 判断新扩展的结点可否进入队列}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>var k,t,i3,j3:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>begin {8}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp; </span>with node3 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp; </span>begin {node3}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if kz3=1 then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begin {kz3_1}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for k:=qend-1 downto 0
do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>if
judge3(node3.arr,queue[k]^.arr) then exit;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for k:=qend2-1 downto
0<span style="mso-spacerun: yes">&nbsp; </span>do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>if
judge3(node3.arr,queue2[k]^.arr) then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>writeln('No.1 k=',k);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>result(k,node3);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>if(node3.j1&gt;node3.j2)
then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>t:=i1; i1:=i2; i2:=t;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>t:=j1; j1:=j2; j2:=t;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>if(node3.j1=node3.j2)and(i1=i2+1) then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begin<span
style="mso-spacerun: yes">&nbsp; </span>t:=i1; i1:=i2; i2:=t;<span
style="mso-spacerun: yes">&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>if not judge2(arr)
then<span style="mso-spacerun: yes">&nbsp; </span>exit;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>ext_to_sd(node3,queue[qend]^);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>qend:=qend+1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>end; {kz3_1}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if kz3=2 then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begin {kz3_2}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for k:=qend2-1 downto 0
do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>if
judge3(node3.arr,queue2[k]^.arr) then<span style="mso-spacerun: yes">&nbsp;
</span>exit;</span></p>