首页 > 代码库 > 分治法-棋盘覆盖问题 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++代码实现