棋盘覆盖问题
程序员文章站
2022-06-03 17:00:15
...
棋盘覆盖问题
题目
在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
思想
利用分治法的思想,主要通过递归来实现。将棋盘分为大小相等的四部分,进行处理,一直到棋盘大小为1结束。
初始时,将棋盘分为大小相等的四部分之后,一定有亿部分中含有特殊方格,因此就可以从其他三部分中各取出一块组成L型骨牌,如图
蓝色的起特殊方格,绿色的为L型骨牌,将放置L型骨牌的地方也当作特殊方格,那没就可以将原问题分解为四个与原问题相同且相互独立的子问题,在分别处理这四个子问题,处理方法同上,因此可以通过递归实现
具体见代码
代码
#include<bits/stdc++.h>
using namespace std;
int cnt=0;//作为全局变量,记录L型骨牌的编号
int board[100][100];//棋盘
//tr:当前棋盘中左上角的行号
//tc:当前棋盘中左上角的列号
//x:当前棋盘中特殊标记所在位置行号
//y:当前期盼中特殊标记所在位置列号
//size:当前棋盘的大小
void ChessBoard(int tr,int tc,int x,int y,int size)
{
if(size==1)
return ;//相当于递归结束的条件
int t=++cnt;//当前要添加的L型骨牌编号
int s=size/2;//棋盘中间的行号和列号(因为行数等于列数,所以棋盘中间行号列号相等)
if(x<tr+s&&y<tc+s)//如果特殊方格在左上角的那四分之一部分内
{
ChessBoard(tr,tc,x,y,s);//说明此时不用放置L型骨牌,继续递归处理这四分之一棋盘
}
else//若这四分之一中没有特殊方格
{
board[tr+s-1][tc+s-1]=t;//这四分之一方格的最右下角作为L型骨牌的一部分
ChessBoard(tr,tc,tr+s-1,tc+s-1,s);//继续递归处理这四分之一棋盘
}
if(x<tr+s&&y>=tc+s)//操作原理同处理右上角那四分之一
{
ChessBoard(tr,tc+s,x,y,s);//这里是右上角那四分之一,所以此时的行号为tr,列号为tc+s
}
else
{
board[tr+s-1][tc+s]=t;
ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
}
if(x>=tr+s&&y<tc+s)
{
ChessBoard(tr+s,tc,x,y,s);
}
else
{
board[tr+s][tc+s-1]=t;
ChessBoard(tr+s,tc,tr+s,tc+s-1,s);
}
if(x>=tr+s&&y>=tc+s)
{
ChessBoard(tr+s,tc+s,x,y,s);
}
else
{
board[tr+s][tc+s]=t;
ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
}
return ;
}
int main()
{
int size;//方格的大小
int u,v;//记录特殊方格的位置
cin>>size;
cin>>u>>v;
ChessBoard(0,0,u,v,size);
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
cout<<board[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
上一篇: 因为两年前的性能劣化门:法国给苹果开出2500万欧元罚单
下一篇: 早上喝茶好不好?喝茶也是有讲究的
推荐阅读
-
php smarty truncate UTF8乱码问题解决办法
-
.Net与JS时间日期格式的转换问题对比分析
-
Ubuntu下MySQL中文乱码的问题解决
-
.Net获取URL中文参数值的乱码问题解决方法总结
-
基于Android SDK-在64位Linux中使用需要注意的问题
-
解决电脑光驱出仓时里面有响声但托盘伸不出来的问题
-
深入Android线程的相关问题解惑
-
Android开发笔记之:深入理解Cursor相关的性能问题
-
深入android中The connection to adb is down的问题以及解决方法
-
Android编程中TextView宽度过大导致Drawable无法居中问题解决方法