?? 騎士走棋盤.mht
字號:
From: <由 Microsoft Internet Explorer 5 保存>
Subject: =?gb2312?B?8lTKv9ffxuWxUA==?=
Date: Wed, 13 Sep 2006 01:07:58 +0800
MIME-Version: 1.0
Content-Type: multipart/related;
boundary="----=_NextPart_000_0034_01C6D6D1.0D582FF0";
type="text/html"
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1807
This is a multi-part message in MIME format.
------=_NextPart_000_0034_01C6D6D1.0D582FF0
Content-Type: text/html;
charset="big5"
Content-Transfer-Encoding: quoted-printable
Content-Location: http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip/KnightTour.htm
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>=C3M=A4h=A8=AB=B4=D1=BDL</TITLE>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Dbig5"><LINK=20
href=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip=
/css/stdlayout.css"=20
type=3Dtext/css rel=3Dstylesheet><LINK=20
href=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip=
/css/print.css"=20
type=3Dtext/css rel=3Dstylesheet>
<META content=3D"MSHTML 6.00.2800.1561" name=3DGENERATOR></HEAD>
<BODY>
<H3><A=20
href=3D"http://caterpillar.onlyfun.net/Gossip/index.html">http://caterpil=
lar.onlyfun.net/Gossip/index.html</A></H3>
<H1><A=20
href=3D"http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip=
/AlgorithmGossip.htm">Algorithm=20
Gossip: =C3M=A4h=A8=AB=B4=D1=BDL</A></H1>
<H2> =BB=A1=A9=FA</H2>=C3M=A4h=AE=C8=B9C=A1]Knight=20
tour=A1^=A6b=A4Q=A4K=A5@=AC=F6=AA=EC=AD=BF=A8=FC=BC=C6=BE=C7=AEa=BBP=AB=F7=
=B9=CF=B0g=AA=BA=AA`=B7N=A1A=A5=A6=A4=B0=BB=F2=AE=C9=AD=D4=B3Q=B4=A3=A5X=A4=
w=A4=A3=A5i=A6=D2=A1A=C3M=A4h=AA=BA=A8=AB=AAk=AC=B0=A6=E8=ACv=B4=D1=AA=BA=
=A8=AB=AAk=A1A=C3M=A4h=A5i=A5H=A5=D1=A5=F4=A4@=AD=D3=A6=EC=B8m=A5X=B5o=A1=
A=A5=A6=ADn=A6p=A6=F3=A8=AB=A7=B9[=A9=D2=A6=B3=AA=BA=A6=EC=B8m=A1H<BR>
<H2>=B8=D1=AAk</H2>=C3M=A4h=AA=BA=A8=AB=AAk=A1A=B0=F2=A5=BB=A4W=A5i=A5H=A8=
=CF=A5=CE=BB=BC=B0j=A8=D3=B8=D1=A8M=A1A=A6=FD=ACO=AF=C2=E3c=AA=BA=BB=BC=B0=
j=A6b=BA=FB=AB=D7=A4j=AE=C9=AC=DB=B7=ED=A8S=A6=B3=AE=C4=B2v=A1A=A4@=AD=D3=
=C1o=A9=FA=AA=BA=B8=D1=AAk=A5=D1J.C.=20
Warnsdorff=A6b1823=A6~=B4=A3=A5X=A1A=C2=B2=B3=E6=AA=BA=BB=A1=A1A=A5=FD=B1=
N=B3=CC=C3=F8=AA=BA=A6=EC=B8m=A8=AB=A7=B9=A1A=B1=B5=A4U=A8=D3=AA=BA=B8=F4=
=B4N=BCe=BCs=A4F=A1A=C3M=A4h=A9=D2=ADn=A8=AB=AA=BA=A4U=A4@=A8B=A1A=A1u=AC=
=B0=A4U=A4@=A8B=A6A=BF=EF=BE=DC=AE=C9=A1A=A9=D2=AF=E0=A8=AB=AA=BA=A8B=BC=C6=
=B3=CC=A4=D6=AA=BA=A4@=A8B=A1C=A1v=A1A=A8=CF=A5=CE=B3o=AD=D3=A4=E8=AAk=A1=
A=A6b=A4=A3=A8=CF=A5=CE=BB=BC=B0j=AA=BA=B1=A1=AAp=A4U=A1A=A5i=A5H=A6=B3=B8=
=FB=B0=AA=AA=BA=BE=F7=B2v=A7=E4=A5X=A8=AB=AAk=A1]=A7=E4=A4=A3=A8=EC=A8=AB=
=AAk=AA=BA=BE=F7=B7|=A4]=ACO=A6=B3=AA=BA=A1^=A1C=20
<BR>
<H2>=BAt=BA=E2=AAk</H2><PRE>FOR(m =3D 2; m <=3D =C1`=A8B=BC=C6; m++) =
[<BR> =
=B4=FA=B8=D5=A4U=A4@=A8B=A5i=A5H=A8=AB=AA=BA=A4K=AD=D3=A4=E8=A6V=A1A=B0O=BF=
=FD=A5i=B0=B1=AFd=AA=BA=AE=E6=BC=C6count=A1C<BR><BR> IF(count =3D=3D =
0) [<BR> =B9C=BE=FA=A5=A2=B1=D1<BR> ]<BR> ELSE IF(count =
=3D=3D 1) [<BR> =A4U=A4@=A8B=A5u=A6=B3=A4@=AD=D3=A5i=AF=E0<BR> =
]<BR> ELSE [<BR> =
=A7=E4=A5X=A4U=A4@=A8B=AA=BA=A5X=B8=F4=B3=CC=A4=D6=AA=BA=AE=E6=A4l<BR> =
=
=A6p=AAG=A5X=B8=F4=AD=C8=AC=DB=A6P=A1A=ABh=BF=EF=B2=C4=A4@=AD=D3=B9J=A8=EC=
=AA=BA=A5X=B8=F4=A1C <BR> ]<BR><BR> =
=A8=AB=B3=CC=A4=D6=A5X=B8=F4=AA=BA=AE=E6=A4l=A1A=B0O=BF=FD=C3M=A4h=AA=BA=B7=
s=A6=EC=B8m=A1C <BR>] <BR></PRE>
<H2>=B9=EA=A7@</H2>
<UL>
<LI>C </LI></UL><PRE>#include <stdio.h> <BR><BR>int board[8][8] =
=3D {0}; <BR><BR>int main(void) {<BR> int startx, starty;<BR> int =
i, j;<BR><BR> printf("=BF=E9=A4J=B0_=A9l=C2I=A1G");<BR> scanf("%d =
%d", &startx, &starty);<BR><BR> if(travel(startx, starty)) =
{<BR> printf("=B9C=BE=FA=A7=B9=A6=A8=A1I\n");<BR> }<BR> =
else {<BR> printf("=B9C=BE=FA=A5=A2=B1=D1=A1I\n");<BR> =
}<BR><BR> for(i =3D 0; i < 8; i++) {<BR> for(j =3D 0; j =
< 8; j++) {<BR> printf("%2d ", board[i][j]);<BR> =
}<BR> putchar('\n');<BR> }<BR><BR> return 0;<BR>} =
<BR><BR>int travel(int x, int y) {<BR> // =
=B9=EF=C0=B3=C3M=A4h=A5i=A8=AB=AA=BA=A4K=AD=D3=A4=E8=A6V<BR> int =
ktmove1[8] =3D {-2, -1, 1, 2, 2, 1, -1, -2};<BR> int ktmove2[8] =3D =
{1, 2, 2, 1, -1, -2, -2, -1};<BR><BR> // =
=B4=FA=B8=D5=A4U=A4@=A8B=AA=BA=A5X=B8=F4<BR> int nexti[8] =3D =
{0};<BR> int nextj[8] =3D {0};<BR><BR> // =
=B0O=BF=FD=A5X=B8=F4=AA=BA=AD=D3=BC=C6<BR> int exists[8] =3D =
{0};<BR><BR> int i, j, k, m, l;<BR> int tmpi, tmpj;<BR> int =
count, min, tmp;<BR><BR> i =3D x;<BR> j =3D y;<BR><BR> =
board[i][j] =3D 1;<BR><BR> for(m =3D 2; m <=3D 64; m++) {<BR> =
for(l =3D 0; l < 8; l++) {<BR> exists[l] =3D 0;<BR> =
}<BR><BR> l =3D 0;<BR><BR> // =
=B8=D5=B1=B4=A4K=AD=D3=A4=E8=A6V<BR> for(k =3D 0; k < 8; k++) =
{<BR> tmpi =3D i + ktmove1[k];<BR> tmpj =3D j + =
ktmove2[k];<BR><BR> // =
=A6p=AAG=ACO=C3=E4=AC=C9=A4F=A1A=A4=A3=A5i=A8=AB<BR> if(tmpi =
< 0 || tmpj < 0 || tmpi > 7 || tmpj > 7)<BR> =
continue;<BR><BR> // =
=A6p=AAG=B3o=AD=D3=A4=E8=A6V=A5i=A8=AB=A1A=B0O=BF=FD=A4U=A8=D3<BR> =
if(board[tmpi][tmpj] =3D=3D 0) {<BR> nexti[l] =3D =
tmpi;<BR> nextj[l] =3D tmpj;<BR> // =
=A5i=A8=AB=AA=BA=A4=E8=A6V=A5[=A4@=AD=D3<BR> l++;<BR> =
}<BR> }<BR><BR> count =3D l;<BR><BR> // =
=A6p=AAG=A5i=A8=AB=AA=BA=A4=E8=A6V=AC=B00=AD=D3=A1A=AA=F0=A6^<BR> =
if(count =3D=3D 0) {<BR> return 0;<BR> }<BR> =
else if(count =3D=3D 1) {<BR> // =
=A5u=A6=B3=A4@=AD=D3=A5i=A8=AB=AA=BA=A4=E8=A6V<BR> // =
=A9=D2=A5H=AA=BD=B1=B5=ACO=B3=CC=A4=D6=A5X=B8=F4=AA=BA=A4=E8=A6V<BR> =
min =3D 0;<BR> }<BR> else {<BR> // =
=A7=E4=A5X=A4U=A4@=AD=D3=A6=EC=B8m=AA=BA=A5X=B8=F4=BC=C6<BR> =
for(l =3D 0; l < count; l++) {<BR> for(k =3D 0; k < =
8; k++) {<BR> tmpi =3D nexti[l] + ktmove1[k];<BR> =
tmpj =3D nextj[l] + ktmove2[k];<BR><BR> =
if(tmpi < 0 || tmpj < 0 || <BR> tmpi > 7 =
|| tmpj > 7) {<BR> continue;<BR> =
}<BR><BR> if(board[tmpi][tmpj] =3D=3D 0)<BR> =
exists[l]++;<BR> }<BR> =
}<BR><BR> tmp =3D exists[0];<BR> min =3D =
0;<BR><BR> // =
=B1q=A5i=A8=AB=AA=BA=A4=E8=A6V=A4=A4=B4M=A7=E4=B3=CC=A4=D6=A5X=B8=F4=AA=BA=
=A4=E8=A6V<BR> for(l =3D 1; l < count; l++) {<BR> =
if(exists[l] < tmp) {<BR> tmp =3D =
exists[l];<BR> min =3D l;<BR> }<BR> =
}<BR> }<BR><BR> // =
=A8=AB=B3=CC=A4=D6=A5X=B8=F4=AA=BA=A4=E8=A6V<BR> i =3D =
nexti[min];<BR> j =3D nextj[min];<BR> board[i][j] =3D =
m;<BR> }<BR><BR> return 1;<BR>} <BR></PRE>
<UL>
<LI>Java </LI></UL><PRE>public class Knight {<BR> public boolean =
travel(int startX, <BR> int startY, int[][] =
board) {<BR> // =
=B9=EF=C0=B3=C3M=A4h=A5i=A8=AB=AA=BA=A4K=AD=D3=A4=E8=A6V<BR> =
int[] ktmove1 =3D {-2, -1, 1, 2, 2, 1, -1, -2};<BR> int[] ktmove2 =
=3D {1, 2, 2, 1, -1, -2, -2, -1};<BR> <BR> // =
=A4U=A4@=A8B=A5X=B8=F4=AA=BA=A6=EC=B8m<BR> int[] nexti =3D new =
int[board.length];<BR> int[] nextj =3D new int[board.length];<BR> =
<BR> // =B0O=BF=FD=A5X=B8=F4=AA=BA=AD=D3=BC=C6<BR> =
int[] exists =3D new int[board.length];<BR> <BR> int x =3D =
startX;<BR> int y =3D startY;<BR> <BR> board[x][y] =
=3D 1;<BR> <BR> for(int m =3D 2; m <=3D =
Math.pow(board.length, 2); m++) {<BR> for(int k =3D 0; k < =
board.length; k++) {<BR> exists[k] =3D 0;<BR> =
}<BR> <BR> int count =3D 0;<BR> // =
=B8=D5=B1=B4=A4K=AD=D3=A4=E8=A6V<BR> for(int k =3D 0; k < =
board.length; k++) {<BR> int tmpi =3D x + ktmove1[k];<BR> =
int tmpj =3D y + ktmove2[k];<BR> <BR> =
// =A6p=AAG=ACO=C3=E4=AC=C9=A4F=A1A=A4=A3=A5i=A8=AB<BR> =
if(tmpi < 0 || tmpj < 0 || <BR> tmpi =
> 7 || tmpj > 7) {<BR> continue;<BR> =
}<BR> <BR> // =
=A6p=AAG=B3o=AD=D3=A4=E8=A6V=A5i=A8=AB=A1A=B0O=BF=FD=A4U=A8=D3<BR> =
if(board[tmpi][tmpj] =3D=3D 0) {<BR> =
nexti[count] =3D tmpi;<BR> nextj[count] =3D tmpj;<BR> =
// =A5i=A8=AB=AA=BA=A4=E8=A6V=A5[=A4@=AD=D3<BR> =
count++;<BR> }<BR> }<BR> =
<BR> int min =3D -1;<BR> if(count =3D=3D 0) =
{<BR> return false;<BR> }<BR> else =
if(count =3D=3D 1) {<BR> min =3D 0;<BR> }<BR> =
else {<BR> // =
=A7=E4=A5X=A4U=A4@=AD=D3=A6=EC=B8m=AA=BA=A5X=B8=F4=BC=C6<BR> =
for(int l =3D 0; l < count; l++) {<BR> for(int =
k =3D 0; k < board.length; k++) {<BR> int tmpi =
nextj[l] + ktmove2[k];<BR><BR> if(tmpi < 0 || =
tmpj < 0 || <BR> tmpi > 7 || tmpj > =
7) {<BR> continue;<BR> =
}<BR><BR> if(board[tmpi][tmpj] =3D=3D 0)<BR> =
exists[l]++;<BR> }<BR> =
}<BR><BR> int tmp =3D exists[0];<BR> =
min =3D 0;<BR><BR> // =
=B1q=A5i=A8=AB=AA=BA=A4=E8=A6V=A4=A4=B4M=A7=E4=B3=CC=A4=D6=A5X=B8=F4=AA=BA=
=A4=E8=A6V<BR> for(int l =3D 1; l < count; l++) {<BR> =
if(exists[l] < tmp) {<BR> =
tmp =3D exists[l];<BR> min =3D l;<BR> =
}<BR> }<BR> }<BR> <BR> =
// =A8=AB=B3=CC=A4=D6=A5X=B8=F4=AA=BA=A4=E8=A6V<BR> x =
=3D nexti[min];<BR> y =3D nextj[min];<BR> =
board[x][y] =3D m;<BR> }<BR> <BR> return true;<BR> =
}<BR> <BR> public static void main(String[] args) {<BR> =
int[][] board =3D new int[8][8];<BR> Knight knight =3D new =
Knight();<BR> <BR> if(knight.travel(<BR> =
Integer.parseInt(args[0]), <BR> =
Integer.parseInt(args[1]), board)) {<BR> =
System.out.println("=B9C=BE=FA=A7=B9=A6=A8=A1I");<BR> }<BR> =
else {<BR> =
System.out.println("=B9C=BE=FA=A5=A2=B1=D1=A1I");<BR> }<BR> =
<BR> for(int i =3D 0; i < board.length; i++) {<BR> =
for(int j =3D 0; j < board[0].length; j++) {<BR> =
if(board[i][j] < 10) {<BR> System.out.print(" " + =
board[i][j]);<BR> }<BR> else {<BR> =
System.out.print(board[i][j]);<BR> }<BR> =
System.out.print(" ");<BR> }<BR> =
System.out.println();<BR> }<BR> =
}<BR>}</PRE><BR><BR></BODY></HTML>
------=_NextPart_000_0034_01C6D6D1.0D582FF0
Content-Type: text/css;
charset="gb2312"
Content-Transfer-Encoding: quoted-printable
Content-Location: http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip/css/stdlayout.css
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -