- 在线时间
- 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:394037668
& h9 E7 t6 q4 w, t9 K2 V0 }) ]/ z1 ~
Hamilton周游路线问题. L# X5 I: c- a# ]% ]
5 R( V. e- ]9 q1 [0 [+ [7 l
8×8 的国际象棋棋盘上的一只马,恰好走过除起点外的其它63 个位置各一次,最后回到起点。这条路线称为一条马的Hamilton 周游路线。对于给定的m×n 的国际象棋棋盘,m和n均为大于5 的偶数,且|m-n|≤2,试设计一个分治算法找出一条马的Hamilton周游路线。8 V8 Q& F; `4 q' t
7 ?$ c) P, j+ `( l: K) R# h; L对于给定的偶数m,n≥6,且|m-n|≤2,编程计算m×n 的国际象棋棋盘一条马的Hamilton周游路线。' _2 x$ E) B! d9 ~
5 X0 M1 `* o! u( t/ w8 p* a' ^( r: A3 x# X& F, L$ s; D9 N8 l
0 h' E: d, [5 k
//算法实现:- v" w) D- k9 y5 E/ a2 C
5 z* y8 G7 h& r& u/ b0 ?
#include <iostream>* ~2 r( s/ X9 E% K" `% x3 N, b
#include <fstream>" f2 V4 N! I) t* X2 L( b `/ f* Z
#include <stdlib.h>) O9 x; n4 [% j3 s7 k- F: H6 ?: a5 Q
#include <afxtempl.h> 2 v2 K$ g8 e; b$ E( v0 [
using namespace std;1 g3 R3 [# l4 {! ~0 l- Z8 L/ Y& b
template<class T>4 y% d$ E0 Q( ?2 S# W* y# E' A l
0 J$ I# I: ]# J. V( N9 Q& zvoid Make2DArray(T** &x , int rows , int cols ) & a7 o# a, e" C z/ m
{
/ u1 @" ?, q6 a6 A. L( | //创建行指针 7 B' A `: t9 V5 ~
x = new T*[rows] ;
0 h3 t& f3 z; p; g9 f- L1 ~ //为每一行分配空间
$ q3 c) i) `; G; x. D$ o8 j for( int i= 0 ; i<rows; i++ ) 8 ^- t I9 u1 C
{
* }1 G; Z& K; e! l/ e7 w x[i] = new int[cols] ; 9 D9 e# ~+ N# c' G: l
}
. w$ h5 [( N% g}
" ~' H* X% @& {. u8 Ytemplate<class T># V# R1 b$ }# M: x, E' x* L
+ b+ c7 G2 P$ a7 j1 M' Q
void Delete2DArray(T** &x , int rows) % u, i/ S% f. L) l# ?: A
{
- P) S: X0 e) _ F. W/ A+ k6 l( z //释放为每一行所分配的空间 # Y" V3 g! u. Y$ Y8 s) ?
for( int i = 0 ; i < rows ; i++ )
9 [: f" t4 \$ {% {5 a {
1 S6 \8 N. Z: A6 }, o! P delete[] x[i] ;
* [ M) A( s4 s @3 ]0 D }
. J H( C5 A7 l# I4 U. H // 释放行指针 - ~* a1 f! ^& X2 I
delete[] x ; 1 N3 e+ ]; m$ W/ S$ |% d, i
x = 0 ;
/ R4 c* P9 P0 ~+ r. I}
, Q" l. i' O/ L' l! U0 c, h
0 ^- T6 ?, c# P" Y' a) u6 \0 y" Y//其中,grid是表示整数对的结构。% O( m5 l4 i9 v! |* A
typedef struct5 o. i( o* m* `6 w. Z' Z5 L+ T
{# [* F# j: V4 \5 [1 H
int x;
+ P9 q5 e- A7 @# Z int y;% }/ C2 b$ M7 U# _% S& E
}grid;
; T ?( [ B) w) m: L( T
) c. p9 u! j( D u) [. z! e( ~1 J//用一个类Knight实现算法。- ?! B" ^% c. y/ v9 y
) E n% f+ S1 I7 y/ B
2 ^ H- `0 [2 H* _4 e* ^! g$ g- tclass Knight
* o4 G6 V3 s* k6 ~. L4 i5 @9 X{; D- G) l; j1 r( V& ~
public:) [1 w7 ]2 q; G l" f4 n- Q
Knight(int m,int n);; B5 Z" k* ?' I# i: s+ c% W
~Knight(){};0 Y, i$ D, m" j A
void out();
4 Z) h, K6 s' m5 w. ^private:
2 j$ Y% t# D4 T int m,n;3 b+ e# y; e4 Y& i( \2 ?
grid *b66,*b68,*b86,*b88,*b810,*b108,*b1010,*b1012,*b1210,**link;; ^* s, [2 C/ w3 V) _
int pos(int x,int y,int col);3 I7 C; c+ N4 a6 l
void step(int m,int n,int **a,grid *b);
% B0 I8 x% E* w1 C' Q8 i6 [1 A# ^( B void build(int m,int n,int offx,int offy,int col,grid *b);- ~ b4 M2 [! g4 P9 |" i
void base(int mm,int nn,int offx,int offy);% a$ @ X# e( C* a
bool comp(int mm,int nn,int offx,int offy );' ]. T% K G/ K; |( h1 [
};
: M" n* g* C& Y, w" J3 b9 d" L4 V9 @( N3 r, ^
( ]& Z- B5 ?1 R2 x, L: l
/ {% v, S1 j3 ~/ ]9 c
3 E# s7 O2 [1 P4 h5 ?& y V//m和n分别表示棋盘的行数和列数。二维数组link用来表示Hamilton回路。
# G) I. r. j8 M% |# @ |//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回路。: q2 I- A7 ?" t) p+ D8 w: a1 Q( r; |
; R' D. d X8 d6 E+ ~$ j1 Q v. u3 D, | ]1 l
//构造函数读入基础数据,初始化各数组。; s! O+ Q, g# ^3 c, [) h" R
' C7 v9 n2 Y s* O3 RKnight::Knight(int mm,int nn)
8 N4 b; t+ U" t7 ]/ w, `0 ~( h0 j{
2 V1 Q6 B6 u# P% C9 a; O8 ^ int i,j,**a;
8 x4 s" Z" N: Z7 P) W ifstream fin0;
6 N( r4 K. n0 D9 m/ v7 U m=mm;n=nn;
9 D! `5 Q, S2 I9 n) G7 N1 ^1 } b66=new grid[36];7 `7 s! z7 z! ~' n
b68=new grid[48];
1 {' \3 y# S/ K$ ?& }. b1 ^ b86=new grid[48];
& o# E* q% y( A+ ~ b88=new grid[64];7 H2 @: R1 R: t# x* W
b810=new grid[80];# {/ w; m* ~3 P, |0 N3 h* u
b108=new grid[80];' E z1 w! c$ c9 f h: M. c/ n
b1010=new grid[100];# Y8 c. u( A% z) Y
b1012=new grid[120];
8 x& F' V3 b+ F- c2 z, X b1210=new grid[120]; ~0 Q$ v! b1 L8 y; m8 O: [
Make2DArray(link,m,n);
y4 L$ l4 h) c7 i4 L7 s Make2DArray(a,10,12);
0 _5 C" |9 R9 D0 X- a' D' Q ) o. W! P$ ?- I% [0 r( S8 o5 X# T
for(i=0;i<6;i++)
9 _& {/ Y9 i9 O( h7 Z$ ]; h3 B8 B for(j=0;j<6;j++) 5 J# e5 I' l% B
fin0>>a[i][j];
" `, R1 r# J4 \: g! `8 u6 S step(6,6,a,b66);
8 Y5 ~! {# }5 e! e* u* I5 N2 F for(i=0;i<6;i++)) z8 _8 B5 b1 P" U2 I( M( l. w( }( Z
for(j=0;j<8;j++) , h) L3 t/ y8 ^
fin0>>a[i][j];9 C- c3 }6 t6 p8 _( c
step(6,8,a,b68);+ ]4 Z0 N7 x* _& n9 Z6 o
step(8,6,a,b86);0 A- r3 c' o9 b7 }3 x
for(i=0;i<8;i++)
* w* `3 u* O( N. G0 e. N for(j=0;j<8;j++)
- ?) V U; E, \ fin0>>a[i][j];
: D, e9 @* f2 v# r9 Z) _8 ^ step(8,8,a,b88);+ `3 y8 K M* J! g* ^
for(i=0;i<8;i++)
$ i% i! u* g2 J: ~ for(j=0;j<10;j++)
& ~/ `7 T4 ^0 c& b8 ] fin0>>a[i][j]; G1 ~1 [2 y1 r# X% t: {9 L
step(8,10,a,b810);
$ I! H' t f3 x step(10,8,a,b108);3 J) n2 H: y6 K9 V
for(i=0;i<10;i++)
. f' a3 v, j: I- E. v6 m/ D# X* l3 [9 I for(j=0;j<10;j++) ( ?, n5 O. D# g: z- V6 n
fin0>>a[i][j];
, @( G- q1 M1 |* P4 H1 y step(10,10,a,b1010);" ^+ _& i8 w+ y/ a- T- s& O
for(i=0;i<10;i++)
( V9 B9 g& G+ j/ X for(j=0;j<12;j++) + A: f9 e3 Y) ], J( z
fin0>>a[i][j];
0 ], G; p: h+ y7 J; R* k step(10,12,a,b1012);
4 [4 }3 G5 ^. d step(12,10,a,b1210);8 L0 h/ ^( P2 U) H( `! v" a2 R
" a3 i2 j" Q7 B' P- _% [- [}
1 M J" N% U9 q' _8 o
7 W" I8 m$ v& L3 f4 x$ D, I( {$ ^, Z
//其中,step用于将读入的基础棋盘的Hamilton回路转化为网格数据。" E+ h T! Z2 J/ R; {
3 t* `' S: i+ y9 l
void Knight::step(int m,int n,int **a,grid *b)
3 l, c- d1 U' }8 C+ ]5 m{! y; F3 M) j/ b* P8 ~
int i,j,k=m*n;
* c% m# O4 W' P5 c0 ~- k$ t if(m<n)
8 w6 L, s0 O+ M( X8 ?8 l+ T& S {; v& S7 ]& K$ t1 s- D. R% ^9 `
for(i=0;i<m;i++)
' y5 l0 T! _, c# J0 m8 S4 r9 W# Y for(j=0;j<n;j++): ]) y2 B+ d b
{
$ {, ^' g+ c5 s int p=a[i][j]-1;
/ I" h" P; `# I/ Z b[p].x=i;b[p].y=j;
, \: ~9 x9 X% ?: w }5 B/ u6 X5 t$ o9 d7 ^" ?
}
, A% ~& @% P9 d% s- A else{8 y" s- b* X' Q0 ^
for(i=0;i<m;i++)
- z3 S$ H) B9 I for(j=0;j<n;j++){
$ ]+ Y! o* W. r+ Q6 d int p=a[j][i]-1;
* @' e" U4 R! F$ h% u4 V b[p].x=i;b[p].y=j;
* S$ A% j h+ N5 w# j5 b+ }8 y+ \' r9 Q }
' R' ^6 W* Z0 l. b, z/ i' m# g }
' s7 X' i$ I! N8 F" w- M( J}
8 L4 ~5 k, x* q1 i6 K/ g7 g' {2 \* u$ V0 t S
$ b4 j. A) w% V5 E//分治法的主体由如下算法comp给出。7 ^. {$ o; J" n O' g8 e' l
bool odd(int data)
V0 B. K+ q5 v8 k1 z# N{
1 C4 u) g0 F" A6 N8 X" p" ] if (data%2 ==0)9 {8 Y% V" O, N2 G/ S) i
{0 \9 }" |, N) P x
return false;
, ]( N* v& e3 K9 ]7 Y+ N: X }
1 K. I# q6 C9 v% W return true;
6 i' W9 f$ Y* ~4 `- ?}
/ J' m$ o- w2 e! z/ ~. y: Y7 t+ c) {* ?+ o4 _! m8 P
5 n# W3 ^) O7 d! ^7 M; g& p
bool Knight::comp(int mm,int nn,int offx,int offy)
0 R/ C6 c7 ~3 S7 M! J+ k9 H) }{; ^/ H' v* I. N( m
int mm1,mm2,nn1,nn2;
8 k- s- Y( v7 }, f int x[8],y[8],p[8];
/ a P0 A0 g1 Z# b' u. r if(odd(mm)||odd(nn)||mm-nn>2||nn-mm>2||mm<6||nn<6)return 1;8 t3 G; Z8 b! B5 I& H6 q
if(mm<12||nn<12){base(mm,nn,offx,offy);return 0;} //基础解" a! w7 Y2 ~6 X: ^: y; l
mm1=mm/2;
8 p% E, k- u5 \, v1 [3 } if(mm%4<0)mm1--;
% p( A) R* J5 k8 F8 j3 K+ I mm2=mm-mm1; X3 W! t. v$ O+ c/ R+ Q
nn1=nn/2;; b: X7 [! |* L2 J7 m0 ~
if(nn%4>0)nn1--;7 w0 c- R6 |3 m0 s. A; t
nn2=nn-nn1;
* m" ~$ u% |. L7 Z' ` //分割步8 ^; \3 `, E( G* e5 Y3 Y* K
comp(mm1,nn1,offx,offy);
5 j: B4 a% n7 Q1 F comp(mm1,nn2,offx,offy+nn1);
9 e( M) z. r( T3 D+ R comp(mm2,nn1,offx+mm1,offy);% p% W7 Z1 F. Y, E4 C
comp(mm2,nn2,offx+mm1,offy+nn1);
- [9 G; @+ A6 K+ g7 F; R //合并步 O# W! T2 I9 ^) _1 X. D/ @+ v, ^
x[0]=offx+mm1-1;y[0]=offy+nn1-3;5 b, X( p) i% u$ m5 R% `1 U
x[1]=x[0]-1;y[1]=y[0]+2;# K `: x y2 e3 O5 a
x[2]=x[1]-1;y[2]=y[1]+2;. a& s/ y/ y$ |0 v( S9 c; A
x[3]=x[2]+2;y[3]=y[2]-1;( _! g) P1 Q8 x8 ^. F: Y" F
x[4]=x[3]+1;y[4]=y[3]+2;' \+ p. i( Q6 ?
x[5]=x[4]+1;y[5]=y[4]-2;1 T/ u) w" M0 a- z! m3 p) @
x[6]=x[5]+1;y[6]=y[5]-2;
- W+ o' C6 I% O2 ~) u! q3 a9 ^' B x[7]=x[6]-2;y[7]=y[6]+1;
5 r* k/ F0 U% k ~ 9 w0 ]( u" S5 ~( I+ P
for(int i=0;i<8;i++) p[i]=pos(x[i],y[i],n);
; k$ I! C# l6 W1 D% q for(i=1;i<8;i+=2){ d5 S0 g, L* H# e. B$ E
int j1=(i+1)%8,j2=(i+2)%8;/ Q% z! z2 F1 J" R" O( N& [
if(link[x[i]][y[i]].x==p[i-1]) link[x[i]][y[i]].x=p[j1];+ U- M) {6 i2 ^9 a4 Z$ N5 e
else link[x[i]][y[i]].y=p[j1];
8 U* h0 s$ C; @; P2 O- L$ G- J if(link[x[j1]][y[j1]].x==p[j2]) link[x[j1]][y[j1]].x=p[i];
H1 S& G* R0 n5 d" l0 r1 e else link[x[j1]][y[j1]].y=p[i];0 J2 D6 i+ y) q" M
}
4 |, e- \, `8 ^9 i i" e* {7 G return 0;
" L A1 k, v! n- J% n}
x. b& q" k* q$ Z: M1 W* `' J) D2 ~& L* N" y
3 h' U3 J# ~0 f9 P
//其中,base是根据基础解构造子棋盘的结构化Hamilton回路。7 E( L. y) i, _4 N- P7 p& ^- B& \4 F
$ j" C7 l$ J i, t& a l' m% J
void Knight::base(int mm,int nn,int offx,int offy)
( J5 h+ X2 D3 F{) C8 ?. u6 D" f
if(mm==6&&nn==6)build(mm,nn,offx,offy,n,b66);
5 `- ]: u$ ]" D; S( p if(mm==6&&nn==8)build(mm,nn,offx,offy,n,b68);8 f" ]' ?6 A8 W: K
if(mm==8&&nn==6)build(mm,nn,offx,offy,n,b86);
. F/ r3 i* a- g9 Y* ~* _' [' u if(mm==8&&nn==8)build(mm,nn,offx,offy,n,b88);. L: J3 R y; O9 A; S* K! a+ D- ~6 C3 m
if(mm==8&&nn==10)build(mm,nn,offx,offy,n,b810);) s* O3 M6 M$ i* Z4 L) r
if(mm==10&&nn==8)build(mm,nn,offx,offy,n,b108);
[4 B0 d2 M7 J o" J4 e" a2 k5 H if(mm==10&&nn==10)build(mm,nn,offx,offy,n,b1010);/ \9 {6 a& Z! ]4 i# j x
if(mm==10&&nn==12)build(mm,nn,offx,offy,n,b1012);
' i5 ^7 s3 v; v/ {* Q; n0 z- i if(mm==12&&nn==10)build(mm,nn,offx,offy,n,b1210);
+ a8 P- j; Q# c; c}# t3 s' `& h1 W! f
. T w3 g R/ A, h5 U5 D* O8 V/ `$ e, f/ o2 S4 M
//其实质性的构造由算法build来完成。
) { {; Z/ z# v% v& D
% c2 N7 S3 C" ~void Knight::build(int m,int n,int offx,int offy,int col,grid *b)
9 w' U( K/ K; _, j{% k" \) J$ y* B$ g9 L9 ~
int i,p,q,k=m*n;
: T( r% o( U5 G, N% M for(i=0;i<k;i++){
2 P% K9 @5 `8 q8 R; N7 e# c2 V int x1=offx+b[i].x,
0 k! B9 ? s& X% x$ F! ?4 x; A: ? y1=offy+b[i].y,
/ C4 x s* |. \0 U4 h e x2=offx+b[(i+1)%k].x,
0 G" Y6 ~' E) q2 I y2=offy+b[(i+1)%k].y;
* n5 l$ _* k8 C/ E; C: P2 y r8 @0 M p=pos(x1,y1,col);q=pos(x2,y2,col);
5 T) m% h4 {- E* A& u* B link[x1][y1].x=q;link[x2][y2].y=p;
1 u1 O, X8 q, _" a" b% \5 s }
% V7 m- H! h P! Y# X( |/ W}
4 ^; H# V) y* ?# z% C* ^
7 } M# {6 h2 z; M+ |: L0 Z8 i' u& S
8 N3 Q. S6 T4 g2 W//其中,pos用于计算棋盘方格的编号。棋盘方格各行从上到下,各列从左到右依次编号为0,1,....,mn-1.& E2 w$ I5 T! l
5 x# ~3 I/ j) r) S j( D
int Knight::pos(int x,int y,int col)6 }# y6 R S/ n- ~
{
( t7 i7 h) ~7 P5 s1 J+ @ return col*x|y;9 I; S: ~1 Q) {/ d7 Y
}7 L" f( q( G1 k$ L+ q% f
+ z5 ]6 \$ t$ k/ R
3 ]5 E% Q( B7 r& \
//最后,由out按照要求输出计算出的结构化Hamilton回路。
) U! U; D9 R! R- |5 v4 U: R5 n
0 G& y1 `2 \, ]8 x) Tvoid Knight: ut(). o4 _0 n0 W u2 V2 o6 N% Z( J
{
g8 {3 _) V1 s( P- K8 i int i,j,k,x,y,p,**a;+ |! r% B* F% G6 [2 |. Q
Make2DArray(a,m,n);4 U& z9 j: M5 ]) n- |
if(comp(m,n,0,0)) return;* _% `* a9 u# V* Q6 F" N% q* j
for(i=0;i<m;i++)1 l3 f5 R. L! m& p6 x
for(j=0;j<n;j++) a[i][j]=0;' ~$ H8 ?+ {2 w9 }
i=0;j=0;k=2;a[0][0]=1;+ p. y( [$ s8 o) M% ]3 u
cout<<"(0,0)"<<"";. p* [1 x" n+ `7 `. O- {/ c
for(p=1;p<m*n;p++){
4 o/ _, v8 K3 N9 B" ]8 V, j x=link[i][j].x;y=link[i][j].y;
2 [7 ]0 \# m ?$ E( ` n+ i i=x/n;j=k%n;2 [8 k: c `# D2 S
if(a[i][j]>0){i=y/n;j=y%n;}, \! i$ y5 Q9 ?; e
a[i][j]=k++;8 e, E) b. @) r# Y o' o; d
cout<<"("<<i<<","<<j<<")";
q; o7 s/ N1 W2 ? if((k-1)%n==0) cout<<endl; }' ?5 h1 s% U( X
}+ X) q; A7 h/ P4 k( S' k( D
cout<<endl;4 G, k9 n! u; S u
for(i=0;i<m;i++){
* D) d' W1 [" V1 F$ X' D for(j=0;j<n;j++) cout<<a[i][j]<<"";8 A) `, \$ U, D; A% v
cout<<endl;
6 y+ M5 N# C. d2 D! d6 V }( l; H. Z, P, r) k- V+ S& t
} |
|