- 在线时间
- 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
" N0 \7 V' ?1 g9 \( p3 S2 S% N
/ w9 |7 t% m* y- _7 O3 J Hamilton周游路线问题. t8 k/ N! s8 o, S% m
- o& X+ v1 D- E/ d( H
8×8 的国际象棋棋盘上的一只马,恰好走过除起点外的其它63 个位置各一次,最后回到起点。这条路线称为一条马的Hamilton 周游路线。对于给定的m×n 的国际象棋棋盘,m和n均为大于5 的偶数,且|m-n|≤2,试设计一个分治算法找出一条马的Hamilton周游路线。
8 n$ b. M! O( d2 z
. Z9 E6 d: a+ w7 Y& w" F) n对于给定的偶数m,n≥6,且|m-n|≤2,编程计算m×n 的国际象棋棋盘一条马的Hamilton周游路线。$ Y8 s. e& |% }' `% s4 p- n( ]
* d& e: A; S' C# E6 D* H6 s' X
$ W, @# W9 d% P
( Q' z3 W* I, h- T//算法实现:7 y0 r" [$ a) m; v* [# W: |
# H0 j* p( \; }% A
#include <iostream>8 T( ~( z, z9 h" J8 Z# ]0 m
#include <fstream>) p. c* _) y/ G
#include <stdlib.h>3 ?9 M; O' X# G; ?, o
#include <afxtempl.h> $ V: x8 u3 y# T7 H( _" c
using namespace std;- U- Z2 ~2 ]$ M1 i. A
template<class T>1 ~. _( a# S* d+ x
; ~& X% g9 t$ _5 n8 I
void Make2DArray(T** &x , int rows , int cols )
3 I* ]0 T8 e- J6 O. q- N$ L6 s{ ) e0 E! [% S6 \; P; E b; M$ C
//创建行指针 ! ^6 l# A1 o H. ~5 p
x = new T*[rows] ; 8 _6 Q( Y, }2 a+ A
//为每一行分配空间 1 N5 q/ U. p+ w# D& @8 H% Y1 Q
for( int i= 0 ; i<rows; i++ ) $ F" y# L6 K( c ^0 h2 ?, y
{ 4 `; {8 Z6 b) F7 a2 d) H+ Y& N5 {0 l2 e* d
x[i] = new int[cols] ; $ t8 a1 D9 S* f! [
} ( u( B4 a% u0 G( g) D0 ~5 N
} . C% z3 o% P) J( l* {) n% o" v; M0 p
template<class T> x4 y( @1 P' ?
m! d' S- J6 M* B V6 d" G( u' g
void Delete2DArray(T** &x , int rows) 7 K* P. L$ |3 n5 V+ J
{
( ]3 h8 V8 f) Z0 ?2 o, E //释放为每一行所分配的空间 3 L4 x7 W- ?" ~5 D7 v
for( int i = 0 ; i < rows ; i++ ) 2 V4 w: O8 a: X4 {0 r- P
{
( k3 X$ a3 w- L* e5 G+ W" S7 u$ b delete[] x[i] ; / h: `& l: u5 W+ X& f
}
* U1 {7 R" A, ~2 o // 释放行指针 ! ~* C/ A- j! D: S6 }% ]1 _
delete[] x ;
: d6 a. |6 Q! }8 P) U x = 0 ; " S: l: d9 d' Z
}* w5 i5 \$ G+ a1 P* a7 ^
, z0 c1 a% h$ r! W# Q$ k//其中,grid是表示整数对的结构。, P6 A- e8 h1 }0 Y: h5 }# ]% O5 u W
typedef struct0 ]* u9 ?8 y! p4 p) |
{9 z' m. i, a9 y$ w
int x;
l9 W+ g! y" u/ E/ d8 x int y;
: Z3 @, `6 ^1 c6 s}grid;# O( D# Y4 ?4 k6 |
c, g+ J8 S/ W$ U//用一个类Knight实现算法。
( y. y& S' v/ q1 x+ C1 B% K- t# V5 s4 }, ~' f* m* @: W
% C% Q0 T! O3 t1 H7 v+ B4 Cclass Knight y4 k7 Z9 M; `1 w5 I
{
9 D3 g: i1 Q6 j: d2 i, K6 Gpublic:
4 U& c8 T: h5 [$ F; l8 w+ O7 ]& W( }1 f Knight(int m,int n);
3 m/ Y, T0 D, C6 u, o ~Knight(){};1 A+ _. ^6 W5 n4 r: R/ K
void out();0 ?* h7 g# T2 N
private:/ P; H' V; o% L$ s$ x# v
int m,n;
3 B- a5 a$ T6 D grid *b66,*b68,*b86,*b88,*b810,*b108,*b1010,*b1012,*b1210,**link;
% J' h# x; i% o: ` int pos(int x,int y,int col);# \3 V' a$ T( \
void step(int m,int n,int **a,grid *b);
' _4 a9 V) N. X6 q$ V void build(int m,int n,int offx,int offy,int col,grid *b);
. h6 {, x; c8 @; z0 f3 h( ] void base(int mm,int nn,int offx,int offy);) m0 @9 S& ?7 Y. W O3 C/ J
bool comp(int mm,int nn,int offx,int offy );
1 u% J. u3 H6 M- M};
7 J4 f V$ t) v' i1 u& h! w
* G# P* K j* h8 \ p/ g" k
" q1 Z* s! @, t* h& A+ ?6 M
2 |; {; P1 b' b/ p# q
: V# _5 v) D2 ?: }, u1 c//m和n分别表示棋盘的行数和列数。二维数组link用来表示Hamilton回路。
+ ^. x7 _8 a0 {//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回路。
, ?* `; F$ D8 k' }% |" I8 P5 o! G4 Y2 z' [) V' }' m# J
+ \$ U3 F" m' B$ I+ V5 B# o
//构造函数读入基础数据,初始化各数组。
: H- u8 R$ k6 J+ f
( @6 M; J2 M) fKnight::Knight(int mm,int nn)- G p) _% R" R1 n( U/ K% ]9 G
{' J0 @5 h, V1 z: O0 e: l
int i,j,**a;% k1 C/ d+ h7 s- W- b1 n
ifstream fin0;! g! R9 P6 K' `# E" F! K
m=mm;n=nn;
' `, X8 t; e- S9 n7 J b66=new grid[36];
. S) p, Q) l' R# A, |" R" s b68=new grid[48];
8 Q8 k& _+ h9 P. {5 u) T& e+ o b86=new grid[48];
* v; a1 W4 {! m' |% s7 N; {4 [! i/ n b88=new grid[64];% K- g& z( d9 |" ~, m
b810=new grid[80];
) t; ?, N* l* B5 Y b108=new grid[80];
3 c6 X# T* x0 n# e! R3 X b1010=new grid[100];
5 Y2 E- H, M4 s2 a$ L b1012=new grid[120];9 t T0 T4 N. ^; {+ h8 p" I, a
b1210=new grid[120];
* D( J" o- B x5 q; W0 ^: o Make2DArray(link,m,n);* q% |) y6 v% \- G3 q' U
Make2DArray(a,10,12);0 N# S/ O% b* D, i; \# D8 {! y
' a2 V" A! i: \. H6 n, T' v; n for(i=0;i<6;i++)
/ I9 K0 ?2 k3 Q6 f for(j=0;j<6;j++)
; d! h( Z, `1 q3 m5 Q3 H fin0>>a[i][j];
1 k. p4 H" y8 P1 A/ r step(6,6,a,b66);
$ ~* @. O0 _8 a8 h; v for(i=0;i<6;i++)2 z4 [. V! ] Q# C
for(j=0;j<8;j++)
4 F+ N( O! G/ Q fin0>>a[i][j];
8 m" e. Y" R) F" b" b0 e step(6,8,a,b68);& _: N! J: ]0 N% Q2 Y' i
step(8,6,a,b86);
|2 i; h2 g9 O4 e) d4 q( i for(i=0;i<8;i++)6 a0 @- K8 S7 t: }" R
for(j=0;j<8;j++)
/ v8 b4 a4 j, Z3 _ fin0>>a[i][j];& e0 c- \6 O/ A' V! p
step(8,8,a,b88);
4 g+ o8 R" L9 f& n% \4 D for(i=0;i<8;i++)2 U. `$ e$ S) |2 c* [$ Z" E6 i
for(j=0;j<10;j++)
2 A0 K' q" W% c. L" l! ]5 g; i fin0>>a[i][j];; Z$ @8 ]- d2 @
step(8,10,a,b810);9 k0 |3 V4 d' _
step(10,8,a,b108);
+ E% G" H$ M2 }' A2 D, f for(i=0;i<10;i++)9 c5 P0 b* H2 a( E1 k
for(j=0;j<10;j++) 3 Q9 O" I- ]: M2 I4 a/ \3 x
fin0>>a[i][j];8 V, e, l! g% y
step(10,10,a,b1010);
2 ~9 p% d0 D+ d3 W+ l for(i=0;i<10;i++)( d; X0 T! e) v+ L
for(j=0;j<12;j++) % p- t. s# N% i3 ]# I0 O
fin0>>a[i][j];
# @2 b! S; s8 h1 {5 g8 H step(10,12,a,b1012);4 {) l$ A; C" E" D4 z$ D3 H: ~
step(12,10,a,b1210);
6 h# |" V: f- h) R# B * I& Y: S$ }2 ?: T
}
% l3 r* e1 M: S) j% ?$ f6 P- C2 c: Z: O: ]1 E" f3 I D5 ~
6 Y8 t* ~0 O3 u' k( v* u
//其中,step用于将读入的基础棋盘的Hamilton回路转化为网格数据。
! ~7 y% O! ]9 B; [
' W$ T8 Q t& G$ uvoid Knight::step(int m,int n,int **a,grid *b)1 w2 c$ B3 m0 @. ]
{
/ o- @# k0 N" {- y1 L' o1 z int i,j,k=m*n;* L& p$ I/ m6 j; v, F, p) h: S
if(m<n)
! d! f7 s3 t5 q9 b1 A2 d8 Z {$ e7 @4 K0 \8 s
for(i=0;i<m;i++)
9 n4 W8 R0 m! e- D' Q% X for(j=0;j<n;j++)
" g0 O4 {5 z; Y$ X {
2 M! W/ U V, U5 Y6 p int p=a[i][j]-1;$ U* n2 Y3 V, v& M
b[p].x=i;b[p].y=j;
$ I1 V, B9 u( H% _' i }: o7 g, K0 u$ P3 z8 D( b
}
$ R* F1 y; {$ X' t$ G else{- b3 A/ T, f* c2 P ~$ J2 l! d6 p
for(i=0;i<m;i++)3 h# p' d* f% p M
for(j=0;j<n;j++){
/ V# K2 \9 p# V int p=a[j][i]-1;( k- }8 s( C1 C. t/ D8 W( _, `5 x
b[p].x=i;b[p].y=j;
$ M8 r1 d# {5 f8 }8 U, O }/ y6 [* w5 G) D# f3 c+ d
}
) v# I; j" i! @}& c( Q2 U$ o' y
4 }3 {- A- G7 K1 W# m
, A0 J, C8 R/ g: d+ q* Q//分治法的主体由如下算法comp给出。
8 J! Y7 Q8 H) @. q \4 |- fbool odd(int data)* m3 J" N) a8 C- E; c
{) d* k4 z0 _7 N" q( G
if (data%2 ==0), X7 ?& w* ?2 Z9 ~! U9 \; b
{' O) w: L! R5 {5 n6 h% R9 g
return false;
5 {/ S$ O6 @$ ^) F }! m8 x9 Y% v* x+ b
return true;
% G3 ?, q+ w( A1 \}/ {- l- ~* I2 R: c
% C; k5 Z+ b% K# R+ J) G7 \
( b5 j/ i/ Q0 e1 A0 z
bool Knight::comp(int mm,int nn,int offx,int offy)* J$ _" h" M3 A3 ^, p
{8 a" ~1 d9 [. E5 |
int mm1,mm2,nn1,nn2;
M! ^; _$ Y7 b9 p int x[8],y[8],p[8];2 a6 |1 K" i F# Y1 Q W, C$ J
if(odd(mm)||odd(nn)||mm-nn>2||nn-mm>2||mm<6||nn<6)return 1;& V# M. {" j F& v: W$ O1 \& i
if(mm<12||nn<12){base(mm,nn,offx,offy);return 0;} //基础解
3 o; `# ?/ ?+ r7 Y$ A# G2 P mm1=mm/2;0 h1 t/ w: J( Z' ]- q, A# K) H
if(mm%4<0)mm1--;
/ `( @' ]* I, M' w# A% C8 E! b mm2=mm-mm1;
$ M9 h* \* x. I& Q1 M- Y& \! ? nn1=nn/2;
/ q! v' _' O( N3 c if(nn%4>0)nn1--;! U& @% i$ A& ?. E0 ?
nn2=nn-nn1;
- R8 i" P1 p3 \0 x! M //分割步
% M8 @. u! U- e comp(mm1,nn1,offx,offy); u6 c2 w G; M! \+ k5 u: [
comp(mm1,nn2,offx,offy+nn1);
3 o( u# {! w, I# P# X$ K comp(mm2,nn1,offx+mm1,offy);
2 v! S4 d* t& P# q# |2 @1 z& J7 Q) X comp(mm2,nn2,offx+mm1,offy+nn1);
H, k- E% {% O% } //合并步
, E" J/ q( ^, s x[0]=offx+mm1-1;y[0]=offy+nn1-3;( Q1 e: v7 N" G2 i( W0 a
x[1]=x[0]-1;y[1]=y[0]+2;
" k& z; p }( w x[2]=x[1]-1;y[2]=y[1]+2;8 K5 ^2 `& G8 S G1 d. J5 D
x[3]=x[2]+2;y[3]=y[2]-1;
' i+ H6 v" l! X T+ I# o5 Z% c x[4]=x[3]+1;y[4]=y[3]+2;
0 t9 x# W1 o' Q: O/ q' t x[5]=x[4]+1;y[5]=y[4]-2;
3 Y* Y( O, O, u5 a5 z x[6]=x[5]+1;y[6]=y[5]-2;
9 x" I6 a3 c$ Q- b) f: I3 Q" L- t; } x[7]=x[6]-2;y[7]=y[6]+1;. p* g# J% M) N- e7 X3 b7 D5 `) r S& D
3 J2 a% |) |1 W5 P4 v) s
for(int i=0;i<8;i++) p[i]=pos(x[i],y[i],n);
0 h* U6 z$ f' w3 f- {5 [ for(i=1;i<8;i+=2){- y& p7 x; W6 r, m' L
int j1=(i+1)%8,j2=(i+2)%8;: }% A1 f9 q4 N4 P
if(link[x[i]][y[i]].x==p[i-1]) link[x[i]][y[i]].x=p[j1];
3 b/ J# X: {0 a/ c; |7 W, S else link[x[i]][y[i]].y=p[j1];
u! r* S' c5 F- L% e4 P if(link[x[j1]][y[j1]].x==p[j2]) link[x[j1]][y[j1]].x=p[i];
/ j7 V- c& n& ?2 R# M1 f else link[x[j1]][y[j1]].y=p[i];
9 O- `- M" P- q( j- I/ g# C }! F8 x6 t7 v( ]) [/ A( m% B
return 0;
% V* I& b: P) P. f: u ?% l5 M5 q}4 i7 k# R1 Q- X8 C L& C# ~- q
8 l" q V- P" b( |: Y( \
! V4 B5 U3 a8 |/ `' a' x8 G" T//其中,base是根据基础解构造子棋盘的结构化Hamilton回路。
- _$ x( l3 ?0 k! w; D1 q8 u8 s6 M! X, j! `
void Knight::base(int mm,int nn,int offx,int offy)
0 ]* |# T) @( @& p1 G{( _# d- b& i: I
if(mm==6&&nn==6)build(mm,nn,offx,offy,n,b66);
1 f# r( D! o5 H9 c3 w8 E8 e if(mm==6&&nn==8)build(mm,nn,offx,offy,n,b68);6 c1 a7 {2 l# E e, }. J
if(mm==8&&nn==6)build(mm,nn,offx,offy,n,b86);
9 K8 D6 {, c; r$ ]- S if(mm==8&&nn==8)build(mm,nn,offx,offy,n,b88);
: c9 P5 V- n+ q) O+ u) T if(mm==8&&nn==10)build(mm,nn,offx,offy,n,b810);. b: J+ x! Y2 e/ ^) Q6 c- l1 K2 ~
if(mm==10&&nn==8)build(mm,nn,offx,offy,n,b108);
. }5 p, |7 p5 x- H4 _: `" u if(mm==10&&nn==10)build(mm,nn,offx,offy,n,b1010);
* v, t( Y. x. }) f if(mm==10&&nn==12)build(mm,nn,offx,offy,n,b1012);8 c9 q7 C: Q; B* [6 Q4 p3 j
if(mm==12&&nn==10)build(mm,nn,offx,offy,n,b1210);
. S) ^" S% o) |. F+ R}) t2 d) q0 a! z
& Q7 ~5 i; N) J$ q# ^/ @! T9 T7 M) |/ P7 h( C, H4 T6 T. p
//其实质性的构造由算法build来完成。4 y" V D8 ?7 Y# e
- [ i7 G$ P9 W$ w! S
void Knight::build(int m,int n,int offx,int offy,int col,grid *b)
8 n L6 D7 i; p( u5 q; N{
# O* Y H& |" H2 Z3 Z& m7 e int i,p,q,k=m*n;
% m6 O9 j( i# ?( M+ Y for(i=0;i<k;i++){- q% s S, i; T1 {, i8 h( g. F* C
int x1=offx+b[i].x,' ]/ d) B8 L- Q. H) ^2 l2 d
y1=offy+b[i].y,, S- \+ ~) J0 Z
x2=offx+b[(i+1)%k].x,
- i! Z6 @$ y2 ^: f7 v6 X3 _/ Z y2=offy+b[(i+1)%k].y;5 A5 d3 p4 R, i
p=pos(x1,y1,col);q=pos(x2,y2,col);
, v; | F) c# b, M" Q link[x1][y1].x=q;link[x2][y2].y=p;
: ]) ^0 V( O9 k- N }
0 L2 v9 D: v' j- b; Z/ n0 s}( s+ f1 y7 o& g1 M! o; r$ |6 e' I
: A3 b5 z" q3 R) p* N# D X! S
: I' z% f1 j6 l% c0 H# H9 p5 |//其中,pos用于计算棋盘方格的编号。棋盘方格各行从上到下,各列从左到右依次编号为0,1,....,mn-1. Y6 b) P/ `9 H
. l/ l6 S! j' b9 y! r i2 k8 ~) sint Knight::pos(int x,int y,int col)+ u) ?6 c( O, L* Z ?! O
{1 o( d* t( W5 z/ x: }
return col*x|y;8 @5 C* P) _0 P& d- i
}
4 C5 N# n# `7 y. n! \2 T: J6 T V, W8 u$ ^2 t
& P1 _, X( p+ G7 J* q8 [7 M//最后,由out按照要求输出计算出的结构化Hamilton回路。
8 o1 E: m6 q' }$ _8 W1 j/ {: z
* v: [* S. t, s* O; [ J5 F4 dvoid Knight: ut()
9 u3 ~1 b2 H# M- L4 P1 W6 k0 [8 \{
( h/ H, Y" A- t int i,j,k,x,y,p,**a;
6 v2 X- ^7 [, ?% e4 V- R Make2DArray(a,m,n);5 H9 N; G6 O6 V0 c
if(comp(m,n,0,0)) return;
5 F. r( ?0 s: Z D for(i=0;i<m;i++)6 D+ U+ l0 N' S# }3 z) H
for(j=0;j<n;j++) a[i][j]=0;
% q4 }0 E0 @( F1 @8 P# B' z i=0;j=0;k=2;a[0][0]=1;8 |9 d8 F) |. u* S
cout<<"(0,0)"<<"";# l x- b8 u9 l* G+ h3 D9 t3 N
for(p=1;p<m*n;p++){/ p6 f+ G/ Q, z# Q8 C. O
x=link[i][j].x;y=link[i][j].y;
* `) X: L- p5 H7 Q | i=x/n;j=k%n;1 [- N2 F1 O/ l! T5 P
if(a[i][j]>0){i=y/n;j=y%n;}
% u7 |5 c+ T; S( d a[i][j]=k++;$ D W; ?3 X" p+ d1 O g/ U
cout<<"("<<i<<","<<j<<")";
1 ^, _2 }6 Y4 ^$ P0 } if((k-1)%n==0) cout<<endl;0 h4 ?7 c$ g/ l
}* g4 p; v# d2 }# ?) Q
cout<<endl;5 |" v6 W2 U7 {0 T/ M' G
for(i=0;i<m;i++){
, ^/ G5 d. g) I2 R1 {' b/ g for(j=0;j<n;j++) cout<<a[i][j]<<"";( X/ q' ?$ a0 q3 [
cout<<endl;
$ k6 g' T' p F& G* r, Z( o }. W4 l% U( c& {- I2 P. c
} |
|