棋盘覆盖----分治和递归

**棋盘覆盖问题**

**Time Limit:**1000ms, **Special Time Limit:**2500ms, **Memory Limit:**32768KB

**Total submit users:** 62, **Accepted users:**26

**Problem 10432 :**No special judgement

**Problem description**

在一个2k x 2k (即：2^k x 2^k )个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

![](http://acm.hunnu.edu.cn/online/images/10432.jpg)

**Input**

输入文件第一行是一个整数T,表示有多少组测试数据，接下来是T组测试数据，共2T行，每组第一行为整数n,是2的n次幂（1<=n<=64），表示棋盘的大小为n*n,第二行是两个整数，代表特殊方格所在行号和列号。

**Output**

先输出“CASE:i，然后按样例输出。数据间用制表符隔开(‘t’),每行最后一个数据后无制表符。

**Sample Input**

**Sample Output**

CASE:1
0       1
1       1
CASE:2
3       3       4       4       8       8       9       9
3       2       2       4       8       7       7       9
5       2       0       6       10      10      7       11
5       5       6       6       1       10      11      11
13      13      14      1       1       18      19      19
13      12      14      14      18      18      17      19
15      12      12      16      20      17      17      21
15      15      16      16      20      20      21      21

**Judge Tips**

要求遍历顺序按从左到右，从上到下。

1 /* 功能Function Description:   棋盘覆盖  
 2    开发环境Environment:        DEV C++ 4.9.9.1
 3    技术特点Technique:
 4    版本Version:
 5    作者Author:                 可笑痴狂
 6    日期Date:                   20120820
 7    备注Notes:
 8    题目来源：http://acm.hunnu.edu.cn/online/?action=problem&id=10432&type=show
 9    题解：
10    分治和递归
11    详解：http://blog.csdn.net/akof1314/article/details/5423608
12 */
13 
14 //不知道为啥不能提交，感觉没啥问题
15 #include<stdio.h>
16 int board[65][65];
17 int NUM;
18 //r1,c1:棋盘左上角的行号和列号
19 //rs,cs:特殊方格的行号和列号
20 //size=棋盘的边长
21 void putchess(int rl,int cl,int rs,int cs,int size)
22 {
23     if(size==1)
24         return;
25     int half=size/2;
26     int num=NUM++;      //注意这里的num  不能   用NUM直接代替然后在下边NUM自增  
27     if(rs<half+rl&&cs<half+cl)  //特殊方格在左上角的棋盘中
28         putchess(rl,cl,rs,cs,half);
29     else                       // 不在此棋盘，将此棋盘右下角设为相应的骨牌号
30     {
31         board[rl+half-1][cl+half-1]=num;
32         putchess(rl,cl,rl+half-1,cl+half-1,half);
33     }
34     if(rs<half+rl&&cs>=half+cl)  //特殊方格在右上角的棋盘中
35         putchess(rl,cl+half,rs,cs,half);
36     else                         // 不在此棋盘，将此棋盘左下角设为相应的骨牌号
37     {
38         board[rl+half-1][cl+half]=num;
39         putchess(rl,cl+half,rl+half-1,cl+half,half);
40     }
41     if(rs>=half+rl&&cs<half+cl)  //特殊方格在左下角的棋盘中
42         putchess(rl+half,cl,rs,cs,half);
43     else                         // 不在此棋盘，将此棋盘右上角设为相应的骨牌号
44     {
45         board[rl+half][cl+half-1]=num;
46         putchess(rl+half,cl,rl+half,cl+half-1,half);
47     }
48     if(rs>=half+rl&&cs>=half+cl)  //特殊方格在右下角的棋盘中
49         putchess(rl+half,cl+half,rs,cs,half);
50     else                         // 不在此棋盘，将此棋盘左上角设为相应的骨牌号
51     {
52         board[rl+half][cl+half]=num;
53         putchess(rl+half,cl+half,rl+half,cl+half,half);
54     }
55 }
56 
57 
58 
59 int main()
60 {
61     int T,n,a,b,i,j,k;
62     scanf("%d",&T);
63     for(k=1;k<=T;++k)
64     {
65         NUM=1;
66         scanf("%d",&n);
67         scanf("%d%d",&a,&b);
68         board[a][b]=0;
69         putchess(0,0,a,b,n);
70         printf("CASE:%d\n",k);
71         for(i=0;i<n;i++)
72         {
73             for(j=0;j<n-1;j++)
74                printf("%d\t", board[i][j]);
75             printf("%d\n",board[i][j]);
76         }
77     }
78     return 0;
79 }

原文链接: https://www.cnblogs.com/dongsheng/archive/2012/08/20/2648096.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/60342

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

棋盘覆盖—-分治和递归

相关推荐