棋盘覆盖问题的算法实现-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

棋盘覆盖问题的算法实现

简介: 本文为原创,如需转载,请注明作者和出处,谢谢!    在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格,如何覆盖。
本文为原创,如需转载,请注明作者和出处,谢谢!

    在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格,如何覆盖。

    四各L型骨牌如下图1



      图1 


棋盘中的特殊方格如图2





图2

    实现的基本原理是将2^k * 2^k的棋盘分成四块2^(k - 1) * 2^(k - 1)的子棋盘,特殊方格一定在其中的一个子棋盘中,如果特殊方格在某一个子棋盘中,继续递归处理这个子棋盘,直到这个子棋盘中只有一个方格为止如果特殊方 格不在某一个子棋盘中,将这个子棋盘中的相应的位置设为骨牌号,将这个无特殊方格的了棋盘转换为有特殊方格的子棋盘,然后再递归处理这个子棋盘。以上原理 如图3所示。





图3

    将棋盘保存在一个二维数组中。骨牌号从1开始,特殊方格为0,如果是一个4 * 4的棋盘,特殊方格为(2,2),那么程序的输出为

2   2   3   3  
2   1   1   3  
4   1   0   5  
4   4   5   5

    
相同数字的为同一骨牌。
下面是棋盘覆盖问题的c语言实现。


#include <stdio.h>

#define BOARD_SIZE 4
int board[BOARD_SIZE][BOARD_SIZE];

// c1, r1: 棋盘左上角的行号和列号
// c2, r2: 特殊方格的行号和列号
// size = 2 ^ k
void chessboard(int r1, int c1, int r2, int c2, int size)
{
    
if(1 == size) return;
    
int half_size;
    
static int domino_num = 1;
    
int d = domino_num++;
    half_size 
= size / 2;   
   
    
if(r2 < r1 + half_size && c2 < c1 + half_size) //特殊方格在左上角子棋盘
    {
       chessboard(r1, c1, r2, c2, half_size); 
    }
    
else   // 不在此棋盘,将此棋盘右下角设为相应的骨牌号
    {
       board[r1 
+ half_size - 1][c1 + half_size - 1= d;
       chessboard(r1, c1, r1 
+ half_size - 1, c1 + half_size - 1, half_size);
    }
   
    
if(r2 < r1 + half_size && c2 >= c1 + half_size) //特殊方格在右上角子棋盘
    {
       chessboard(r1, c1 
+ half_size, r2, c2, half_size);
    }
    
else  // 不在此棋盘,将此棋盘左下角设为相应的骨牌号
    {
       board[r1 
+ half_size - 1][c1 + half_size] = d;
       chessboard(r1, c1 
+ half_size, r1 + half_size - 1, c1 + half_size, half_size);
    }
   
    
if(r2 >= r1 + half_size && c2 < c1 + half_size) //特殊方格在左下角子棋盘
    {
       chessboard(r1 
+ half_size, c1, r2, c2, half_size);
    }
    
else  // 不在此棋盘,将此棋盘右上角设为相应的骨牌号
    {
       board[r1 
+ half_size][c1 + half_size - 1= d;
       chessboard(r1 
+ half_size, c1, r1 + half_size, c1 + half_size - 1, half_size);
    }
   
    
if(r2 >= r1 + half_size && c2 >= c1 + half_size) //特殊方格在左上角子棋盘
    {
       chessboard(r1 
+ half_size, c1 + half_size, r2, c2, half_size);
    }
    
else   // 不在此棋盘,将此棋盘左上角设为相应的骨牌号
    {
       board[r1 
+ half_size][c1 + half_size] = d;
       chessboard(r1 
+ half_size, c1 + half_size, r1 + half_size, c1 + half_size, half_size);
    }   
}

int main()
{
    
int i, j;
    board[
2][2= 0;
    chessboard(
0022, BOARD_SIZE);
    
for(i = 0; i < BOARD_SIZE; i++)
    {
        
for(j = 0; j < BOARD_SIZE; j++)
        {
           printf(
"%-4d", board[i][j]);
        }
        printf(
"/n");
    }
}



国内最棒的Google Android技术社区(eoeandroid),欢迎访问!

《银河系列原创教程》发布

《Java Web开发速学宝典》出版,欢迎定购

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章
最新文章
相关文章