- 在线时间
- 8 小时
- 最后登录
- 2013-6-25
- 注册时间
- 2010-4-17
- 听众数
- 3
- 收听数
- 0
- 能力
- 0 分
- 体力
- 128 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 88
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 102
- 主题
- 3
- 精华
- 0
- 分享
- 0
- 好友
- 1
升级 87.37% TA的每日心情 | 奋斗 2013-6-25 15:34 |
---|
签到天数: 8 天 [LV.3]偶尔看看II
- 自我介绍
- 200 字节以内
不支持自定义 Discuz! 代码
群组: 2013认证赛A题讨论群组 |
调试的时候就是有两个问题,弄了两天了,我也不好说,哪位高手帮忙指点下:非常感激,急急急!!!!! qq:3940376682 z, x- L# [8 C7 ~
+ f; j0 _% H- v. |
Hamilton周游路线问题
1 L9 U5 u7 A8 w4 X/ G+ o- v9 H8 H, i
0 Y% S5 z0 z S6 d. p8×8 的国际象棋棋盘上的一只马,恰好走过除起点外的其它63 个位置各一次,最后回到起点。这条路线称为一条马的Hamilton 周游路线。对于给定的m×n 的国际象棋棋盘,m和n均为大于5 的偶数,且|m-n|≤2,试设计一个分治算法找出一条马的Hamilton周游路线。
{; f/ [# t7 e. E$ T* ~1 `1 B9 }) `7 Y: ?& |' v4 o
对于给定的偶数m,n≥6,且|m-n|≤2,编程计算m×n 的国际象棋棋盘一条马的Hamilton周游路线。; t1 a6 e" v3 Q. [, S6 C
. O! P8 j! q- u9 N) [
, s1 T: s9 ~: X$ z" W# L% Q0 Y
" m. I; c' h, f8 H( ^3 a& Z: i//算法实现:
# n) v! U( L9 B' N! E O# X4 f, L" ~$ T7 r# v0 L
#include <iostream>/ I& S4 v( Y* [( \+ t# g$ {: Q
#include <fstream>
4 a: Q, @2 H; M' j; y: ?#include <stdlib.h>* P! H2 r/ e, C0 c
#include <afxtempl.h> 6 t; H' ?/ D0 B; j7 L
using namespace std;
" L d% q6 F" y4 e. f$ D' V7 g" @template<class T>7 x' @4 {8 \4 Z- O- g5 _
5 U3 R0 L& d9 `
void Make2DArray(T** &x , int rows , int cols ) ) M, h. }' D4 m; h" Z: d
{
5 ?+ S) I8 H& ?2 \/ t# Z //创建行指针 7 m! D& M1 g6 X; C) z
x = new T*[rows] ;
2 n. ]+ \7 v4 H( l3 ^ //为每一行分配空间
8 z1 m }3 E/ d% B- x6 F# p3 E for( int i= 0 ; i<rows; i++ )
4 L3 k- h0 J# t9 ?5 D" S {
' W9 V& J2 G% J. b1 r, n8 Z3 n5 N x[i] = new int[cols] ;
& |; K& T1 [" W8 d# E; F J. S1 d6 U; B } 5 D, ~3 i1 ?) {) F: c9 X! s
}
8 J9 y; m& m) Y Otemplate<class T>; t% f- P3 D, M0 I2 g& O2 v
, J8 F+ g- w7 o0 U. H x1 `$ N! N/ lvoid Delete2DArray(T** &x , int rows) 9 g4 B/ r6 f4 w1 }. C/ O* ` M; H
{ 6 S+ t# i5 P: l# T- |
//释放为每一行所分配的空间 0 [5 a5 t4 p: U9 H' \3 `
for( int i = 0 ; i < rows ; i++ )
/ K7 C0 x+ i) I5 { {
& B' P4 `2 V% W! l! b2 }- N+ V delete[] x[i] ; $ w" h& K3 r6 E0 `7 K" l
}
' W# m! ~$ B% _/ M% z H // 释放行指针
( }' @! o8 N$ e4 i delete[] x ; 5 ]- i& S3 o" f7 N b, z: ], i' }
x = 0 ;
0 v1 y2 B+ u. w* I' V7 ^}' Q$ _: k, w: m$ ^8 q% p
/ j* i) i9 ?& C# |# Q" k$ H//其中,grid是表示整数对的结构。
. O" z7 ?3 `% Z% jtypedef struct
- k$ i! [2 M0 B: }{/ Y5 r( F1 l1 _8 @6 y
int x;
2 z# Z L& R4 F int y;
m$ v5 P: d L. S/ R}grid;8 t, b0 e1 V" r7 q
S6 z# L& E7 `, v8 \//用一个类Knight实现算法。2 T6 n+ y s% U; t
5 r' ?6 e e# n# _! R1 {% U
+ v* S. b T# ?
class Knight
( O) v0 o! p& T! p$ M{3 m3 s0 z E! O; ]$ y
public:1 w' x0 a6 g# v9 Q( j# M2 ^; x
Knight(int m,int n);# t3 F& J6 t+ j$ M; s9 c
~Knight(){};" [. y( `- P% o3 v
void out();
& ]4 m" H3 ]% }private:) g" w) I6 \3 i% z8 x
int m,n;
4 m$ @4 C% L2 A; z' a3 y! J grid *b66,*b68,*b86,*b88,*b810,*b108,*b1010,*b1012,*b1210,**link;9 p3 Y5 Z! T' T4 V
int pos(int x,int y,int col); ]1 Y3 `3 _9 x: g; t
void step(int m,int n,int **a,grid *b);0 H/ @" @1 |5 S- ]( d6 j
void build(int m,int n,int offx,int offy,int col,grid *b);7 r/ q7 G3 g# u3 P( M; \' W2 a2 z# X
void base(int mm,int nn,int offx,int offy);2 R' X6 M0 _0 F7 R& x% C
bool comp(int mm,int nn,int offx,int offy );1 C$ |/ @" K2 n8 M0 |
};3 S9 @" M: z6 H# b4 B
6 l# m( U2 o: l. A8 }
# M% V% Q( M5 _0 g4 ~. r1 c# m
5 D( D3 r6 J, A8 _
//m和n分别表示棋盘的行数和列数。二维数组link用来表示Hamilton回路。2 ?" M+ C/ ]- e* g
//b66,b68,b86,b88,b810,b108,b1010,b1012,b1210分别表示6*6,6*8,8*6,8*8,8*10,10*8,10*10,10*12,12*10棋盘上的结构化Hamilton回路。
+ k7 O) C. x, c2 n3 ~; `. _0 C" V) R
0 q2 _8 A' d/ ~) |//构造函数读入基础数据,初始化各数组。
. c! ?/ j5 ~5 H: U9 f7 {' _4 J$ {4 B5 M9 l2 H
Knight::Knight(int mm,int nn). I+ C/ [0 ^+ @; V; V- ^
{
3 H7 k0 C9 g9 ^4 A, E/ J8 R7 W int i,j,**a;& a: |6 I& n4 g
ifstream fin0;
. y# Y# P: o2 F* ]5 ` m=mm;n=nn;
$ G8 N) U$ k3 c G2 A* Y6 ~- c b66=new grid[36];
( R6 M7 t1 S( n5 a2 I b68=new grid[48];
0 Q! S6 `$ q9 ~ { b86=new grid[48];
! `4 W, d/ K* }( L% w$ p8 B b88=new grid[64];2 p* S: W6 i2 ~% r! f% \
b810=new grid[80];
) {$ x8 T5 Z f$ ^ b108=new grid[80];, D1 ^# ~( G' ]
b1010=new grid[100];
: K2 u$ e0 E1 d4 \# m/ t- y0 m b1012=new grid[120];
8 m; K* p: c7 L' @& q( f$ ^ b1210=new grid[120];. s& x! ^. N1 L7 B$ a p) t3 }: T) ^
Make2DArray(link,m,n); A" `, z/ X; A
Make2DArray(a,10,12);
7 L# k$ b" A1 F9 ~/ c1 d& X 3 H/ m3 D, H0 P8 ]) C" K$ c$ W
for(i=0;i<6;i++)
6 T/ ^; v) i! { for(j=0;j<6;j++)
8 w, B0 n( y# q) v fin0>>a[i][j];8 U4 ]: O. B' W1 A" I! Y& M* T
step(6,6,a,b66);
5 t G" M0 @" D$ @5 m# H Z( l for(i=0;i<6;i++)
/ x' c) ^+ l" K for(j=0;j<8;j++) 6 G1 Q q- s- M9 e# F, |+ V8 A
fin0>>a[i][j];- ]5 o- m- j* F( e1 E% L
step(6,8,a,b68);
. x/ W2 J; ~, n( m& l( m: B9 a step(8,6,a,b86);- @; f7 I; K: Q S0 T
for(i=0;i<8;i++)# v* u5 P3 e' g" d
for(j=0;j<8;j++) / g6 \! X0 m0 b5 o* g$ i
fin0>>a[i][j];
3 K' ^ X% O/ Y: m7 K/ a step(8,8,a,b88);
, T* L4 X$ T0 K c' J/ ^ for(i=0;i<8;i++)
, @# s, G/ _# ^2 b/ V for(j=0;j<10;j++) # o6 f( Y5 R8 m7 o2 g d6 [. c
fin0>>a[i][j];
' C3 i7 f. V* P step(8,10,a,b810);; P% ?7 N' l5 p
step(10,8,a,b108);
) |( G7 S1 K5 K n! n' T* p6 i( I: C for(i=0;i<10;i++)
4 B8 e" _/ B9 n8 B' ]% Z for(j=0;j<10;j++)
* F' `) s* A9 @7 s* I. ~( S fin0>>a[i][j];
4 Q; B7 m6 i( h7 l9 L# W1 o. Q step(10,10,a,b1010);; g- @% N; {$ t+ v, T5 N! {; a6 J
for(i=0;i<10;i++)
( G0 }# q) Q9 | for(j=0;j<12;j++) ; G8 D% A, o# g# w
fin0>>a[i][j];
! `) `- x' x% C( R- t! h$ o' O step(10,12,a,b1012);; N1 j5 `2 S6 t1 s/ u. q# D. O
step(12,10,a,b1210);
( y3 [, T) z4 I! W
* |+ J7 R( f* n; r7 H) Y8 |8 {4 E}
0 L7 t3 d8 F* j/ ?$ @
5 U7 U) b% Q( ?. P! O* m; x8 U- c, k, n. \6 u3 U6 A2 L
//其中,step用于将读入的基础棋盘的Hamilton回路转化为网格数据。 ?- @- H9 N4 a3 P1 l( W0 M
5 s3 L6 W. y2 b' `5 B- xvoid Knight::step(int m,int n,int **a,grid *b)
: J' X4 |: V1 u8 a$ u4 T2 M" B$ X{& ?8 J2 Y0 k( w3 {" V, P' J
int i,j,k=m*n;
% U/ ~8 u+ ^# _5 t6 J$ O1 j, _ if(m<n)
) ~& W6 `- z5 a {& @ V G+ g% U: t* M1 H6 y# o
for(i=0;i<m;i++)
1 d! ?# o6 A0 v8 C" ?8 l4 I for(j=0;j<n;j++), F9 U/ ?8 i! p+ x& s& j
{! z% S' B6 m- R7 W
int p=a[i][j]-1;
1 t' o, B7 f# i7 V0 w5 f3 E b[p].x=i;b[p].y=j;. z. U5 m' U+ ]& J% P
}
8 e' b% \; F. J6 W1 ]2 l }
7 }3 V( g" Z* j e/ t else{
3 V; ^: s2 A' ^8 J! \! e2 _ for(i=0;i<m;i++)
, l+ h Z1 A. @ for(j=0;j<n;j++){; }- u9 N9 n5 U5 N! `( w7 E( b$ K
int p=a[j][i]-1;% M8 C/ P9 T, n3 j6 _
b[p].x=i;b[p].y=j;
2 ~7 R" ~/ M# O' j& M9 r d }
1 C3 V$ g6 L- @. Y" U }) i8 |( J }1 s& p
}% y. n3 B- k6 l
; O0 Q/ M! @' Y5 ]4 @5 b: a2 b/ j6 H% V, y1 z4 J1 ^% u* A. b
//分治法的主体由如下算法comp给出。% o0 g4 A4 w1 ~7 e) N$ J5 t
bool odd(int data)
9 n7 z7 |, z5 U9 D{
+ @! c+ x, E3 x% \3 k if (data%2 ==0)
5 x, V1 b! k0 ^1 l: W- G8 U. L {
) |+ j$ v8 P8 J+ _5 \& v% z return false;* J6 Z! A: P) u$ k
}: c5 l" a5 h# v- E
return true;
! q" C' A3 p4 j. e9 f}4 R1 Y) L9 @; k7 p! g2 c
1 c4 R; G( ?) ^3 D8 g( R" I W
$ k1 J" D+ o* N. I( w1 Q+ w ?bool Knight::comp(int mm,int nn,int offx,int offy): A, ^" E3 Y2 [
{
: x. z; [. I9 Y( c) z int mm1,mm2,nn1,nn2;0 T& ^: i4 L8 h# z5 }
int x[8],y[8],p[8];, S& n3 C. r( x& _
if(odd(mm)||odd(nn)||mm-nn>2||nn-mm>2||mm<6||nn<6)return 1;* C1 M, K! t8 m. Y% v: ^
if(mm<12||nn<12){base(mm,nn,offx,offy);return 0;} //基础解% y! I0 e6 T1 r0 W4 M$ C
mm1=mm/2;
. d5 S: N5 x1 @$ ?4 W if(mm%4<0)mm1--;
) k/ G9 y0 Y% ^: q7 @2 u mm2=mm-mm1;
/ ]' d1 }$ r! J+ I' L B nn1=nn/2;
& n h! V: x' `. J2 Y if(nn%4>0)nn1--;8 R4 c0 G5 b) A
nn2=nn-nn1;
7 e8 h A% A5 i$ d: q" d8 a9 l //分割步8 \! [. P3 H; C. Y. ^
comp(mm1,nn1,offx,offy);
8 D v4 D: M4 d# E comp(mm1,nn2,offx,offy+nn1);
$ Q5 x% n' D8 C' k. E comp(mm2,nn1,offx+mm1,offy);: V; J/ ~' i: i# V2 b f. O
comp(mm2,nn2,offx+mm1,offy+nn1);
5 h/ w9 c8 F0 b1 P* i# y //合并步8 W% z# K3 L) B6 e) F1 _
x[0]=offx+mm1-1;y[0]=offy+nn1-3;
9 B% o! q- U$ K# y" Y+ G x[1]=x[0]-1;y[1]=y[0]+2;3 o! U: j2 O7 z/ }# l; [; L" O
x[2]=x[1]-1;y[2]=y[1]+2;
/ P m S$ k2 Z: s6 {8 n x[3]=x[2]+2;y[3]=y[2]-1;4 y. l5 U" }+ K3 i
x[4]=x[3]+1;y[4]=y[3]+2;7 p% P+ r6 E+ Z! d# X3 X8 B
x[5]=x[4]+1;y[5]=y[4]-2;
' r# u# x C: z: l: Z x[6]=x[5]+1;y[6]=y[5]-2;
2 v+ T" G. X p ~! X' o x[7]=x[6]-2;y[7]=y[6]+1;) H7 J V7 u# }$ e/ ~$ R6 S0 L
" @7 a0 X( t) K0 R for(int i=0;i<8;i++) p[i]=pos(x[i],y[i],n);
9 w+ a2 h( t" S3 Q) y8 Q3 S for(i=1;i<8;i+=2){
) e2 c3 _( }1 I, u) Q int j1=(i+1)%8,j2=(i+2)%8;( h/ }5 `$ f% Q
if(link[x[i]][y[i]].x==p[i-1]) link[x[i]][y[i]].x=p[j1];% t* M! P: |7 V5 x! Z
else link[x[i]][y[i]].y=p[j1];
0 P3 g2 O9 G4 y/ x' g# [2 U7 b9 X if(link[x[j1]][y[j1]].x==p[j2]) link[x[j1]][y[j1]].x=p[i];; X+ \1 O! c/ X6 J( A
else link[x[j1]][y[j1]].y=p[i]; {% m; @. u& y! e; p9 Q! s& {
}
& m& b: l# R4 G! p6 Z4 f return 0;. c* J7 t" G: d' ~8 Y% N
}; S: l. ~, n* X
. T; h3 K z2 r4 }# e# N" P* U
: S9 [& i9 R9 [: w0 ~/ W//其中,base是根据基础解构造子棋盘的结构化Hamilton回路。3 l2 f8 Z, ~1 H
2 e& l% Q: W% e/ r+ ivoid Knight::base(int mm,int nn,int offx,int offy)& P6 t; x5 D x5 f
{
5 f o$ W# d1 g6 u t4 e if(mm==6&&nn==6)build(mm,nn,offx,offy,n,b66);
5 Q8 O+ G, A! B* Q5 f- K' Z+ D if(mm==6&&nn==8)build(mm,nn,offx,offy,n,b68);
% f. _) p# L3 q5 X# \ if(mm==8&&nn==6)build(mm,nn,offx,offy,n,b86);
3 s: ^2 w& ^" ?1 u2 w+ e if(mm==8&&nn==8)build(mm,nn,offx,offy,n,b88);
8 @: m( F& i1 } if(mm==8&&nn==10)build(mm,nn,offx,offy,n,b810);4 m( F9 m' S% y/ s
if(mm==10&&nn==8)build(mm,nn,offx,offy,n,b108);5 V& M4 B. h* ]
if(mm==10&&nn==10)build(mm,nn,offx,offy,n,b1010);
0 S3 L5 P7 `* g" o if(mm==10&&nn==12)build(mm,nn,offx,offy,n,b1012);
1 H$ M5 [2 p7 T9 u if(mm==12&&nn==10)build(mm,nn,offx,offy,n,b1210);
2 a! f+ H: W5 |& X0 `}: M: ?* r" x9 F
# U! E+ ~$ H! v9 U1 k
2 |2 R% ?" J& A7 d/ `6 _
//其实质性的构造由算法build来完成。
6 t; H+ D& c% l- S; z3 `- ]/ ?3 _1 W8 r$ g
void Knight::build(int m,int n,int offx,int offy,int col,grid *b)! {1 R3 V1 V4 q% S/ A
{
. E2 N& A) V0 b4 D, w- d int i,p,q,k=m*n;0 t; `, z% G' Z; v
for(i=0;i<k;i++){# \8 z$ v0 o0 ?- v7 ? I( |9 i8 N( r
int x1=offx+b[i].x,' P7 u, s) W9 n
y1=offy+b[i].y,
5 P6 e6 R: g$ X/ _4 i, e x2=offx+b[(i+1)%k].x,6 j5 P7 `# r, g" ~" C! t
y2=offy+b[(i+1)%k].y;2 E" m2 E9 G4 v( D6 B/ Q3 h- k
p=pos(x1,y1,col);q=pos(x2,y2,col);) M. @% F0 u+ V! @
link[x1][y1].x=q;link[x2][y2].y=p;0 _7 a9 [' N/ M$ T) }0 S0 F% Y
}
0 I: Z6 x- S4 M9 ~/ U, f: W* A% B}& Y7 H( l/ J. w, C0 [ ]
9 w$ t: P2 W% E) @ M
0 P" E* S' g1 P/ R//其中,pos用于计算棋盘方格的编号。棋盘方格各行从上到下,各列从左到右依次编号为0,1,....,mn-1.$ d7 Z2 L3 D& i2 U# A, v. v3 r
+ m* n1 R$ I3 x
int Knight::pos(int x,int y,int col)
* Y' l# p- j8 y1 r{
9 g" k8 m7 d6 T7 I* J3 G return col*x|y;
; _$ Q0 ]9 b% B+ A# z}1 G" ]+ B8 W. y, N8 @- e/ y: M
( A" ?3 g: B% x; g* D+ P' @% L$ R- I1 P% r+ N" F
//最后,由out按照要求输出计算出的结构化Hamilton回路。9 C' P5 v. l$ u
3 G4 Y: j1 G! K' R8 \/ e
void Knight:ut()
0 U9 e0 E3 T( B u7 ]) j+ L( T }{7 E1 ^4 Z3 ^; W$ v* }/ H
int i,j,k,x,y,p,**a;" Z% P2 W' W3 z- A T* l1 h
Make2DArray(a,m,n);" S& J$ O+ K) G: p4 ]& }* r
if(comp(m,n,0,0)) return;/ h* B1 \0 a8 [- F
for(i=0;i<m;i++)4 y( |1 o2 w: X5 R
for(j=0;j<n;j++) a[i][j]=0;
: u# F2 q$ s! }( }: i i=0;j=0;k=2;a[0][0]=1;, k2 n" ?* |# ~. g0 `* p( r
cout<<"(0,0)"<<"";
: R3 Z4 H; A$ i' S for(p=1;p<m*n;p++){6 a; d) U) z0 \2 s4 q; A4 W1 |
x=link[i][j].x;y=link[i][j].y;
0 `( U' M0 T4 M$ ?5 ?5 k i=x/n;j=k%n;
9 k/ Q. k g1 M6 b* ] if(a[i][j]>0){i=y/n;j=y%n;}
- k! t* n) l: r# p# \ a[i][j]=k++;
6 y: `1 x2 f) q" A3 _ cout<<"("<<i<<","<<j<<")";
. `/ a( L1 c. [* W* k. q. U0 a. s if((k-1)%n==0) cout<<endl;
. j: l8 R" f8 Z) Q }
! s- W; J: @* w cout<<endl;
/ P* o8 ?9 D/ D. M for(i=0;i<m;i++){. S2 E0 q C: \8 a' l
for(j=0;j<n;j++) cout<<a[i][j]<<"";
: m; j. h& r# c R cout<<endl;
. H( E; ^: U7 F4 Y/ K- S' ] }. y* u1 ~; S" i5 s& U( Q0 N
} |
|