首页 > 代码库 > 分治法-棋盘覆盖问题 C++代码实现
分治法-棋盘覆盖问题 C++代码实现
一个非常经典的题,用分治法来做。
每次将棋盘分割成4块,对于原本不存在空白格的棋盘要用一个L骨牌来构造空白格。
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<vector>#include<queue>#define LL long longusing namespace std;int num;int grid[100][100];inline bool judge(int sx,int sy,int size,int dx,int dy){ return (sx<=dx&&dx<=sx+size-1)&&(sy<=dy&&dy<=sy+size-1);}void dfs(int sx,int sy,int size,int dx,int dy){ if(size==1) return; int len=size/2; int s; //左上右上左下右下分别是1234 if(judge(sx,sy,len,dx,dy)) s=1; else if(judge(sx,sy+len,len,dx,dy)) s=2; else if(judge(sx+len,sy,len,dx,dy)) s=3; else if(judge(sx+len,sy+len,len,dx,dy)) s=4; int ex=sx+len,ey=sy+len; int c=++num; if(s!=1) { grid[ex-1][ey-1]=c; dfs(sx,sy,len,ex-1,ey-1); } else dfs(sx,sy,len,dx,dy); if(s!=2) { grid[ex-1][ey]=c; dfs(sx,sy+len,len,ex-1,ey); } else dfs(sx,sy+len,len,dx,dy); if(s!=3) { grid[ex][ey-1]=c; dfs(sx+len,sy,len,ex,ey-1); } else dfs(sx+len,sy,len,dx,dy); if(s!=4) { grid[ex][ey]=c; dfs(sx+len,sy+len,len,ex,ey); } else dfs(sx+len,sy+len,len,dx,dy);}int main(){ int n,dx,dy; //输入棋盘的边长,要求n是2的幂;再输入空白格子的坐标。棋盘左上角是(1,1) while(scanf("%d%d%d",&n,&dx,&dy)!=EOF) { memset(grid,0,sizeof(grid)); grid[dx][dy]=-1; num=0; dfs(1,1,n,dx,dy); for(int i=1; i<=n; ++i) { for(int j=1; j<=n; ++j) printf("%3d ",grid[i][j]); printf("\n"); } } return 0;}
分治法-棋盘覆盖问题 C++代码实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。