admin 管理员组

文章数量: 1184232

棋盘覆盖问题（分治法）

问题描述

有一个 x （k>0）的棋盘，恰好有一个方格与其他方格不同，称之为特殊方格。现在要用如下图所示的L形骨牌覆盖除了特殊方格以外的其他全部方格，骨牌可以任意旋转，并且任何两个骨牌不能重复。请给出一种覆盖方式。

下面给出两个例子： (假设特殊方格是白色的）

  • k=2

 

  • k=3 

 

问题求解

 因为方格数=x=，L形骨牌个数=（-1—）/ 3 。以上面的第2个例子举例说明：特殊方格在第8行，第3列，因此特殊方格的右下角（即绿色的L形骨牌）仅一种表示形式——（大家可以尝试一下，其他方法左边两列能否正确处理）。绿色放置之后对于左下角的4x4的正方形来说，特殊方格位于它的第四象限，所以橙色的L形骨牌仅一种表现形式。对于其他的三个象限来说可以将橙色作为它们的特殊方格，以此类推，所有的排列方式即可确定。

因此将原问题分为四个象限求解，且若象限的大小超过4个小方格，即可继续划分（可进行递归调用）。将原棋盘大小设为 size=x,每次划分后的棋盘大小设为 s=size/2  ; 特殊方格的坐标记为(dr,dc) ; 象限的起点（即左上角）记为 (tr,tc)  ！！！牢记这一点！！！接着我们将其特殊格子所在的位置分为四种情况： 

当其在第一象限（即右上象限）：将右上象限填满之后，以左下角作为特殊方格进行处理

 

if(dr<tr+s && dc>=tc+s)Solve(tr,tc+s,dr,dc,s);
else{board[tr+s-1][tc+s]=t;Solve(tr,tc+s,tr+s-1,tc+s,s);
}

 

当其在第二象限（即左上象限）：将左上象限填满之后，以右下角作为特殊方格进行处理

 

if(dr<tr+s && dc<tc+s)Solve(tr,tc,dr,dc,s);
else{board[tr+s-1][tc+s-1]=t;Solve(tr,tc,tr+s-1,tc+s-1,s);
}

当其在第三象限（即左下象限）：将左下象限填满之后，以右上角作为特殊方格进行处理

if(dr>=tr+s && dc<tc+s)Solve(tr+s,tc,dr,dc,s);
else{board[tr+s][tc+s-1]=t;Solve(tr+s,tc,tr+s,tc+s-1,s);
}

 

 

当其在第四象限（即右下象限）：将右下象限填满之后，以左上角作为特殊方格进行处理

 

if(dr>=tr+s && dc>=tc+s)Solve(tr+s,tc+s,dr,dc,s);
else{board[tr+s][tc+s]=t;Solve(tr+s,tc+s,tr+s,tc+s,s);
}

 

 代码

#include <iostream>
#include <cmath>
#include <iomanip>     //setw()所在的头文件
#define MAX 1025
using namespace std;int k;
int x,y;               //输入的特殊方格的位置
int tile=1;
int board[MAX][MAX];   //记录L形骨牌的编号void Solve(int tr,int tc,int dr,int dc,int size)
{if(size==1) return;int t = tile;int s = size/2;tile++;//考虑左上象限if(dr<tr+s && dc<tc+s)Solve(tr,tc,dr,dc,s);else{board[tr+s-1][tc+s-1]=t;Solve(tr,tc,tr+s-1,tc+s-1,s);}//考虑右上象限if(dr<tr+s && dc>=tc+s)Solve(tr,tc+s,dr,dc,s);else{board[tr+s-1][tc+s]=t;Solve(tr,tc+s,tr+s-1,tc+s,s);}//考虑左下象限if(dr>=tr+s && dc<tc+s)Solve(tr+s,tc,dr,dc,s);else{board[tr+s][tc+s-1]=t;Solve(tr+s,tc,tr+s,tc+s-1,s);}//考虑右下象限if(dr>=tr+s && dc>=tc+s)Solve(tr+s,tc+s,dr,dc,s);else{board[tr+s][tc+s]=t;Solve(tr+s,tc+s,tr+s,tc+s,s);}
}int main()
{cout << "Input k(k<=10): ";cin>>k;cout<<"Input x,y: ";cin>>x>>y;int size = pow(2,k);Solve(0,0,x,y,size);for(int i=0; i<size; i++){for(int j=0; j<size; j++)cout<<setw(4)<<setfill(' ')<<board[i][j];cout<<endl;}return 0;
}

 

参考资料：《算法设计与分析》第2版  

 

 

本文标签： 棋盘覆盖问题（分治法）

版权声明：本文标题：棋盘覆盖问题（分治法） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.roclinux.cn/p/1698029945a283544.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。