分治

一、棋盘覆盖问题

题意：在一个2^k×2k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有4^{k种情形.因而对任何k≥0,有4}k种不同的特殊棋盘.将 2^k x 2^k 的特殊棋盘化成
4个 2^(k-1) x 2^(k-1)
4个中必然存在一个特殊棋盘，和三个没有特殊棋子的棋盘，为了成为相同的子问题，于是将这 三个棋盘 处理成 特殊棋盘，即加一个特殊棋子。
原来 4x4,1 表示特殊棋子
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

分为
1 0 0 0
0 0 0 0

0 0 0 0
0 0 0 0
-》其他三个变为 特殊棋盘 *

1 0 0 0
0 0 * 0

0 * * 0
0 0 0 0
星号组成的 图形 刚好可以 用 题目给出的 覆盖

#include <string.h>
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include<cstdio>
using namespace std;
int mapp[20][20];
int t = 1;
void fun(int x, int y, int dx, int dy, int size)
{
    if (size == 1)
    {
        return;
    }
    int tt = t++;
    int m = size / 2;
    if (x + m > dx&&y + m > dy)//1 象限
    {
            fun(x, y, dx, dy, m);
    }
    else
    {
        mapp[x + m - 1][y + m - 1] = tt;
        fun(x, y, x + m - 1, y + m - 1, m);
    }



    if (x + m > dx&&y + m <= dy)// 2 象限
    {
        fun(x, y+m, dx, dy, m);
    }
    else
    {
        mapp[x + m-1][y + m] = tt;
        fun(x, y+m, x + m-1, y + m , m);
    }


    if (x + m <= dx&&y + m > dy)//3 象限
    {
        fun(x+m, y, dx, dy, m);
    }
    else
    {
        mapp[x +m][y + m-1 ] = tt;
        fun(x+m, y, x + m , y + m-1 , m);
    }
    if (x + m <= dx&&y + m <= dy)//4 象限
    {
        fun(x+m, y+m, dx, dy, m);
    }
    else
    {
        mapp[x + m ][y + m ] = tt;
        fun(x+m, y+m, x + m , y + m , m);
    }
}
int main()
{
    int k;
    int x, y;
    cin >> k >> x >> y;
    mapp[x][y] = 0;
    fun(0,0, x, y, k);
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < k; j++)
        {
            printf("%4d", mapp[i][j]);
        }
        cout << endl;
    }
    return 0;
}