sicily 1152 简单的马周游问题 and sicily 1153 马的周游问题

1152:

Description

在一个5 * 6的棋盘中的某个位置有一只马，如果它走29步正好经过除起点外的其他位置各一次，这样一种走法则称马的周游路线，试设计一个算法，从给定的起点出发，找出它的一条周游路线。

为了便于表示一个棋盘，我们按照从上到下，从左到右对棋盘的方格编号，如下所示：

1 2 3 4 5 6

7 8 9 10 11 12

13 14 15 16 17 18

19 20 21 22 23 24

25 26 27 28 29 30

马的走法是“日”字形路线，例如当马在位置 15 的时候，它可以到达 2 、 4 、 7 、 11 、 19 、 23 、 26 和 28 。但是规定马是不能跳出棋盘外的，例如从位置 1 只能到达 9 和 14 。

Input

输入有若干行。每行一个整数 N(1<=N<=30) ，表示马的起点。最后一行用 -1 表示结束，不用处理。

Output

对输入的每一个起点，求一条周游线路。对应地输出一行，有 30 个整数，从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。

Sample Input

4
-1

Sample Output

注意：如果起点和输入给定的不同，重复多次经过同一方格或者有的方格没有被经过，都会被认为是错误的。

分析：

本题集体思路为深度搜索方法。可以将本题棋盘各点组成一张无向图，图的边表示马的一步行走路线，两点连通即表示马可以由一点走“日”字到另外一点。这样建模后，题目所求解即为给定起点的一条“图遍历”路径（不是所有），明显深度搜索（DFS）更加合适。

同时又要注意：1152数据量较小，测试数据也不多，可能会出现选择特定的移动向量，直接搜索即可通过的情况，但是1153则不行。所以还是老老实实进行剪枝，剪枝思路是优先遍历出度较少的子节点，可以大幅减少计算量。具体操作是计算并存储子节点出度，再对子节点按照出度排序，由低到高进行遍历，特别注意子节点的存储空间要在DFS函数中动态申请，否则会出错。

PS：1152的题目数据很巧，其实是可以成环的，所以找到一条路径之后打表也是可以的，不过太偷懒了，就不这么做了。

代码：

 1 // Problem#: 1152
 2 // Submission#: 1774802
 3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
 4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
 5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University
 6 #include <iostream>
 7 #include <cstring>
 8 #include <vector>
 9 #include <algorithm>
10 using namespace std;
11 
12 bool flag[5][6];
13 int ans[30];
14 int dir[8][2] = {-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};
15 
16 inline bool judge(int x, int y){
17     return x>=0 && x<5 && y>=0 && y <6 && !flag[x][y];
18 }
19 
20 inline int degree(int a, int b){
21     int re = 0;
22     int x,y;
23     for(int i = 0;i < 8;i++){  
24         x = a + dir[i][0];  
25         y = b + dir[i][1];  
26         if(judge(x,y)) re++;  
27     }  
28     return re;
29 }
30 
31 struct node{
32     int x,y,c;
33     node(){
34     x = y = c = -1;
35     }
36     node(int a, int b){
37     x = a;
38     y = b;
39     c = degree(a,b);
40     }
41 };
42 
43 
44 inline bool cmp(node a, node b){
45     return a.c<b.c;
46 }
47 
48 inline node find(int n){
49     node re;
50     int x = (n-1) / 6;
51     int y = (n-1) % 6;
52     re = node(x,y);
53     return re;
54 }
55 
56 inline node calcu(node a,int c){
57     node re;
58     int x = a.x + dir[c][0];
59     int y = a.y + dir[c][1];
60     re = node(x,y);
61     return re;
62 }
63 
64 bool dfs(node a, int c){
65     node t;
66     vector<node> buffer;
67     flag[a.x][a.y] = true;
68     ans[c] = 6*a.x + a.y + 1;
69     if( c == 29 ) return true;
70     for( int i=0 ; i<8 ; i++ ){
71     t = calcu(a,i);
72     if(judge(t.x,t.y)) buffer.push_back(t);
73     }
74     sort(buffer.begin(),buffer.end(),cmp);
75     for( int i=0 ; i<buffer.size() ; i++ )
76     if( dfs(buffer[i],c+1) ) return true;
77     flag[a.x][a.y] = false;
78     return false;
79 }
80 
81 int main(){
82     int n;
83     while( cin>>n && n>0 ){
84     memset(flag,0,sizeof(flag));
85     node s = find(n);
86     dfs(s,0);
87     cout << n;
88     for( int i=1 ; i<30 ; i++ )
89         cout << " " << ans[i];
90     cout << endl;
91     }
92     return 0;
93 }

1153与1152的问题相似，只是问题规模不同，不再重复叙述，只要改一下部分数组和函数的数据就可以，只附上代码即可。

1153代码：

 1 // Problem#: 1153
 2 // Submission#: 1774794
 3 // The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
 4 // URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
 5 // All Copyright reserved by Informatic Lab of Sun Yat-sen University
 6 #include <iostream>
 7 #include <cstring>
 8 #include <vector>
 9 #include <algorithm>
10 using namespace std;
11 
12 bool flag[8][8];
13 int ans[64];
14 int dir[8][2] = {-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};
15 
16 inline bool judge(int x, int y){
17     return x>=0 && x<8 && y>=0 && y <8 && !flag[x][y];
18 }
19 
20 inline int degree(int a, int b){
21     int re = 0;
22     int x,y;
23     for(int i = 0;i < 8;i++){  
24         x = a + dir[i][0];  
25         y = b + dir[i][1];  
26         if(judge(x,y)) re++;  
27     }  
28     return re;
29 }
30 
31 struct node{
32     int x,y,c;
33     node(){
34     x = y = c = -1;
35     }
36     node(int a, int b){
37     x = a;
38     y = b;
39     c = degree(a,b);
40     }
41 };
42 
43 
44 inline bool cmp(node a, node b){
45     return a.c<b.c;
46 }
47 
48 inline node find(int n){
49     node re;
50     int x = (n-1) / 8;
51     int y = (n-1) % 8;
52     re = node(x,y);
53     return re;
54 }
55 
56 inline node calcu(node a,int c){
57     node re;
58     int x = a.x + dir[c][0];
59     int y = a.y + dir[c][1];
60     re = node(x,y);
61     return re;
62 }
63 
64 bool dfs(node a, int c){
65     node t;
66     vector<node> buffer;
67     flag[a.x][a.y] = true;
68     ans[c] = 8*a.x + a.y + 1;
69     if( c == 63 ) return true;
70     for( int i=0 ; i<8 ; i++ ){
71     t = calcu(a,i);
72     if(judge(t.x,t.y)) buffer.push_back(t);
73     }
74     sort(buffer.begin(),buffer.end(),cmp);
75     for( int i=0 ; i<buffer.size() ; i++ )
76     if( dfs(buffer[i],c+1) ) return true;
77     flag[a.x][a.y] = false;
78     return false;
79 }
80 
81 int main(){
82     int n;
83     while( cin>>n && n>0 ){
84     memset(flag,0,sizeof(flag));
85     node s = find(n);
86     dfs(s,0);
87     cout << n;
88     for( int i=1 ; i<64 ; i++ )
89         cout << " " << ans[i];
90     cout << endl;
91     }
92     return 0;
93 }