棋盘覆盖(分治法)
2018-06-17 23:44:43来源:未知 阅读 ()
题目: 在一个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; }
运行截图:
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P1034 矩形覆盖 2020-03-10
- dfs/bfs专项训练 2019-08-16
- kuangbin专题 专题一 简单搜索 棋盘问题 POJ - 1321 2019-08-16
- 三类贪心区间覆盖问题 2019-08-16
- DFS(三):八皇后问题 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash