晴天的魔法乐园——棋盘覆盖问题

编辑:谯胜平      分类:程序与算法      标签:棋盘覆盖问题      发布时间:2019-09-03      浏览次数:733

Problem Description

给定一个大小为(2^k)×(2^k)(也就是2×2或4×4或8×8或16×16等,依次类推)的白色棋盘,其中有一个格子是黑色的。下图为k=2即4×4的棋盘示例。

ubang_image_20190903125449.png

现在想用一种大小占三个小方格的L形骨牌来覆盖整个棋盘,这种L形骨牌可以通过旋转得到下面四种形态:


注意,在覆盖的时候,骨牌之间不能相互覆盖,也不能覆盖初始状态下已经是黑色的那个格子。
请输出覆盖方案,下图是上面示例的覆盖方案(注:不同颜色只是用来区分不同的骨牌,与题意无关)。

Input

每个输入文件一组数据。
第一行为三个正整数k、cx、cy(k<=8、1<=cx,cy<=2^k),分别表示棋盘的边长是2^k、初始黑色的格子坐标是(cx,cy)。其中以最左下的方格坐标为(1,1),向右为x增加方向,向上为y增加方向。

Output

每行输出一块骨牌的信息,即该骨牌的拐角方格的坐标(x,y),题目描述中的四种形态的拐角方格分别是左上、右上、左下、右下的方格。输出骨牌的顺序为,优先输出x较小的骨牌,x相同的优先输出y较小的骨牌。

Sample Input 1

1 2 1

Sample Output 1

1 2

Sample Input 2

2 2 3

Sample Output 2

1 1
1 4
3 2
4 1
4 4

1、分析

这个博客:https://blog.csdn.net/qq_30268545/article/details/80600064, 分析得很到位,主要采用分治法,说白了就是分多个板块进行递归。代码又臭又长,等以后有空了再修改。

2、代码

#include<algorithm>
#include<vector>
#include<math.h>
#include<stdio.h>
using namespace std;
const int maxn = 260;
struct node{
    int x, y;
};
vector ans;
bool cmp(node &a, node &b){
    if(a.x != b.x){
        return a.x < b.x;
    }else{
        return a.y < b.y;
    }
}

//填充函数,n标识棋盘边长,x和y表示已经覆盖的点的坐标,sX,sY表示该棋盘左下角的坐标 
void fill(int n, int x, int y, int sX, int sY){
    if(n == 2){
        node temp;
        if(x == sX && y == sY){                //点在左下角 
            temp.x = x + 1; 
            temp.y = y + 1;
        }else if(x == sX && y == sY + 1){    //点在左上角 
            temp.x = x + 1; 
            temp.y = y - 1;
        }else if(x == sX + 1 && y == sY + 1){     //点在右上角 
            temp.x = x - 1; 
            temp.y = y - 1;
        }else{                                //点在右下角    
            temp.x = x - 1; 
            temp.y = y + 1;
        }
        ans.push_back(temp);
        return; 
    }else{
        //分别在四个方向进行填充 
        if(x < sX + n / 2 && y < sY + n / 2){                //左下角 
            fill(n / 2, x, y, sX, sY);                                    //左下角 
            fill(n / 2, sX + n / 2, sY + n / 2 - 1, sX + n / 2, sY);     //右下角
            fill(n / 2, sX + n / 2 - 1, sY + n / 2, sX, sY + n / 2);    //左上角
            fill(n / 2, sX + n / 2, sY + n / 2, sX + n / 2, sY + n / 2);//右上角 
            node temp;
            temp.x = sX + n / 2;
            temp.y = sY + n / 2;
            ans.push_back(temp);
        }else if(x >= sX + n / 2 && y < sY + n / 2){        //右下角 
            fill(n / 2, sX + n / 2 - 1, sY + n / 2 - 1, sX, sY);
            fill(n / 2, x , y, sX + n / 2, sY);
            fill(n / 2, sX + n / 2 - 1, sY + n / 2, sX, sY + n / 2);
            fill(n / 2, sX + n / 2, sY + n / 2, sX + n / 2, sY + n / 2);
            node temp;
            temp.x = sX + n / 2 - 1;
            temp.y = sY + n / 2;
            ans.push_back(temp);
        }else if(x < sX + n / 2 && y >= sY + n / 2){        //左上角 
            fill(n / 2, sX + n / 2 - 1, sY + n / 2 - 1, sX, sY);
            fill(n / 2, sX + n / 2, sY + n / 2 - 1, sX + n / 2, sY);
            fill(n / 2, x, y, sX, sY + n / 2);
            fill(n / 2, sX + n / 2, sY + n / 2, sX + n / 2, sY + n / 2);
            node temp;
            temp.x = sX + n / 2;
            temp.y = sY + n / 2 - 1;
            ans.push_back(temp);
        }else{                                                //右上角 
            fill(n / 2, sX + n / 2 - 1, sY + n / 2 - 1, sX, sY);
            fill(n / 2, sX + n / 2, sY + n / 2 - 1, sX + n / 2, sY);
            fill(n / 2, sX + n / 2 - 1, sY + n / 2, sX, sY + n / 2);
            fill(n / 2, x, y, sX + n / 2, sY + n / 2);
            node temp;
            temp.x = sX + n / 2 - 1;
            temp.y = sY + n / 2 - 1;
            ans.push_back(temp);
        }
    }
} 

int main(){
    int k, x, y;
    scanf("%d%d%d", &k, &x, &y);
    fill(pow(2, k), x, y, 1, 1);
    sort(ans.begin(), ans.end(), cmp);
    for(int i = 0; i < ans.size(); i++){
        printf("%d %d\n", ans[i].x, ans[i].y);
    }
    return 0;
}


看不清?换一个