road.htm

常用经典算法及讲解

<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;</span><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;&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;&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,queue2[qend2]^);</span></p>

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

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

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

<p class=MsoPlainText><span lang=EN-US>end;{8}</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
toij_1(xz:byte;node4:node_ext;kz,i,j,kz3:integer);{No.9,xin01等过程共用的中间过程}</span></p>

<p class=MsoPlainText><span lang=EN-US>begin{9}</span></p>

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

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>arr[i,j]:=0;</span></p>

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

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

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

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

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>toqueue(node4,i,j,kz3);</span></p>

<p class=MsoPlainText><span lang=EN-US>end;{9}</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
toij_2(xz:byte;node4:node_ext;i,j,kz3:integer); {No.10,xin01等过程共用的中间过程}</span></p>

<p class=MsoPlainText><span lang=EN-US>begin{10}</span></p>

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

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>arr[i,j]:=0;</span></p>

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&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; </span>arr[i,j+1]:=0;<span
style="mso-spacerun: yes">&nbsp; </span>i1:=i; i2:=i;</span></p>

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

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&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; </span>arr[i+1,j]:=0;<span
style="mso-spacerun: yes">&nbsp; </span>j1:=j; j2:=j;</span></p>

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

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>toqueue(node4,i,j,kz3);</span></p>

<p class=MsoPlainText><span lang=EN-US>end;{10}</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 xin01(
node4:node_ext;ii,jj,kz,kz3:integer); {No.11 处理单个空结点}</span></p>

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

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

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

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

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

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

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if arr[i-1,j]=1 then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&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; </span>arr[i,j]:=1;<span
style="mso-spacerun: yes">&nbsp; </span>i:=i-1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>toij_1(1,node4,kz,i,j,kz3);</span></p>

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>i:=ii;j:=jj; {to upper}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if arr[i-1,j] in b1 then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&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; </span>arr[i,j]:=arr[i-2,j];</span></p>

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>toij_1(1,node4,kz,i,j,kz3);</span></p>

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

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>i:=ii;j:=jj; {to lower}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if arr[i+1,j]=1 then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&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; </span>arr[i,j]:=1;<span
style="mso-spacerun: yes">&nbsp; </span>i:=i+1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>toij_1(1,node4,kz,i,j,kz3);</span></p>

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

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if arr[i+1,j] in b1 then</span></p>

<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>arr[i,j]:=arr[i+2,j];</span></p>

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>toij_1(1,node4,kz,i,j,kz3);</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;&nbsp;&nbsp; </span>node4:=nodetmp;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>i:=ii;j:=jj; {to left}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if arr[i,j-1]=1 then</span></p>

<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>arr[i,j]:=1; j:=j-1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>toij_1(2,node4,kz,i,j,kz3);</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;&nbsp;&nbsp; </span>i:=ii;j:=jj;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if arr[i,j-1]=8 then</span></p>

<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>arr[i,j]:=8;<span
style="mso-spacerun: yes">&nbsp; </sp