首页 > 代码库 > 棋盘覆盖（分治法）
棋盘覆盖（分治法）
题目： 在一个2^k x 2^k 个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊棋盘。现在要用4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格，且任意2个L型骨牌不得重叠覆盖。 解释一下什么是L型骨牌：就是由三个方格组成的一个角，可知有四种；
思路：将一个棋盘均分成四个小的棋盘，沿各边的中点切分，特殊方格必定位于4个较小的棋盘之一中，其余的3个子棋盘中无特殊方格。为了将这3个无特殊子棋盘的子棋盘转化为特殊棋盘，我们可以用一个L型骨牌覆盖这3个较小棋盘的会合出，递归下去，当棋盘边长为1时终止；
代码如下：
#include <iostream>#include <algorithm>#include <stdio.h>#include <string.h>#include <math.h>#include <stdlib.h>#include <set>#include <queue>#include <vector>using namespace std;int tot;int board[105][105];void chessboard(int tr,int tc,int dr,int dc,int size){ if(size==1) return ; int t=tot++; int s=size/2; if(dr<tr+s&&dc<tc+s) chessboard(tr,tc,dr,dc,s); else{ board[tr+s-1][tc+s-1]=t; chessboard(tr,tc,tr+s-1,tc+s-1,s); } if(dr<tr+s&&dc>=tc+s) chessboard(tr,tc+s,dr,dc,s); else{ board[tr+s-1][tc+s]=t; chessboard(tr,tc+s,tr+s-1,tc+s,s); } if(dr>=tr+s&&dc<tc+s) chessboard(tr+s,tc,dr,dc,s); else{ board[tr+s][tc+s-1]=t; chessboard(tr+s,tc,tr+s,tc+s-1,s); } if(dr>=tr+s&&dc>=tc+s) chessboard(tr+s,tc+s,dr,dc,s); else{ board[tr+s][tc+s]=t; chessboard(tr+s,tc+s,tr+s,tc+s,s); }}int main(){ int dr,dc,s; printf("输入格式为： 特殊方格横坐标、纵坐标 棋盘边长\n"); while(scanf("%d%d%d",&dr,&dc,&s)!=EOF) { tot=1; memset(board,0,sizeof(board)); chessboard(0,0,dr,dc,s); for(int i=0;i<s;i++) { for(int j=0;j<s;j++) printf("%-2d ",board[i][j]); cout<<endl; } } return 0;}
运行截图：
棋盘覆盖（分治法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。