Gym101845L.L-shapes_牛客博客

http://codeforces.com/group/NVaJtLaLjS/contest/241861/problem/L
The Che square of the Universidad Nacional de Colombia is represented by an N × N matrix and is going to be remodeled. To achieve this goal, the engineers have one 1 × 1 square-tile and a lot of L-tiles (Enough to fill the entire Che square). Unfortunately, one of the workers have placed the square tile at location in row R and column C ignoring the fact that this could affect the positions of other tiles. Given the importance of the Che square, we need your help in order to know how to place the rest of the tiles so that all N2 positions of the Che square are covered by exactly tile.

The rotations of a L-tile are showed at the following figure, you can place each L-tile in the rotation you want.

Input
The first line contains N (1 ≤ N ≤ 2048, will be a power of 2), the size of the square matrix. The second line contains integers R and C (1 ≤ R, C ≤ N), the row and the column where the worker placed the square tile.

Output
Print a matrix of size N × N ]. The C-th character of the R-th line must be a dot (’.’), representing the 1 × 1 square tile. Every L-tiles must be represented by three uppercase letters. If two L-tiles are adjacent to each other (share more than a point), they must be represented by different letters. Since there are many possible answers, you can print any.

Example
inputCopy
8
3 4
outputCopy
BBCCBBCC
BAACBAAC
CAB.CCAB
CCBBACBB
BBCAABCC
BACCBBAC
CAABCAAB
CCBBCCBB

题意：有一个n*n的矩阵（n是2的幂次），含有1个‘.’，要求用给定的四种格子拼满所有的空缺。
思路：
有一个性质：将矩阵分成四份（左上，左下，右上，右下），则含有’.‘的那一块可以拼满，其余三块都拼不满，会空出来一个小格子。
我们对这个矩阵进行递归四分，对于不含’.‘的三块，在交界处直接放上3个相同字符(这样就转化为了假定那里放了’.’，于是四个小矩阵都可以拼满)。
设计dfs(x,y,l,p):左上角坐标第x行，第y列，边长为l，这个矩阵的左上/右上/左下/右下已经被填标记为1，2，3，4。

#include<bits/stdc++.h>
using namespace std;
#define maxn 2050

int n,r,c;
int a[maxn][maxn];

bool inside(int x,int y,int l){return r>=x&&r<=x+l-1&&c>=y&&c<=y+l-1;}

void dfs(int x,int y,int l,int p)
{
    if(l==2)
    {
        if(inside(x,y,l))
        {
            if(x!=r||y!=c)a[x][y]=p;
            if(x+1!=r||y!=c)a[x+1][y]=p;
            if(x!=r||y+1!=c)a[x][y+1]=p;
            if(x+1!=r||y+1!=c)a[x+1][y+1]=p;
        }
        else
        {
            if(p==1)a[x+1][y]=a[x][y+1]=a[x+1][y+1]=p;
            else if(p==2)a[x+1][y]=a[x][y]=a[x+1][y+1]=p;
            else if(p==3)a[x][y]=a[x][y+1]=a[x+1][y+1]=p;
            else if(p==4)a[x+1][y]=a[x][y+1]=a[x][y]=p;
        }
        return;
    }
    if(inside(x,y,l/2)||inside(x+l/2,y,l/2)||inside(x,y+l/2,l/2)||inside(x+l/2,y+l/2,l/2))
    {
        if(!inside(x,y,l/2))a[x+l/2-1][y+l/2-1]=5,dfs(x,y,l/2,4);
        else dfs(x,y,l/2,0);
        if(!inside(x+l/2,y,l/2))a[x+l/2][y+l/2-1]=5,dfs(x+l/2,y,l/2,2);
        else dfs(x+l/2,y,l/2,0);
        if(!inside(x,y+l/2,l/2))a[x+l/2-1][y+l/2]=5,dfs(x,y+l/2,l/2,3);
        else dfs(x,y+l/2,l/2,0);
        if(!inside(x+l/2,y+l/2,l/2))a[x+l/2][y+l/2]=5,dfs(x+l/2,y+l/2,l/2,1);
        else dfs(x+l/2,y+l/2,l/2,0);
    }
    else 
    {
        if(p==1)
        {
            a[x+l/2][y+l/2]=5;
            a[x+l/2][y+l/2-1]=5;
            a[x+l/2-1][y+l/2]=5;
            dfs(x,y,l/2,1);
            dfs(x,y+l/2,l/2,3);
            dfs(x+l/2,y,l/2,2);
            dfs(x+l/2,y+l/2,l/2,1);
        }
        else if(p==2)
        {
            a[x+l/2-1][y+l/2-1]=5;
            a[x+l/2][y+l/2]=5;
            a[x+l/2][y+l/2-1]=5;
            dfs(x,y,l/2,4);
            dfs(x,y+l/2,l/2,2);
            dfs(x+l/2,y,l/2,2);
            dfs(x+l/2,y+l/2,l/2,1);           
        }
        else if(p==3)
        {
            a[x+l/2-1][y+l/2-1]=5;
            a[x+l/2][y+l/2]=5;
            a[x+l/2-1][y+l/2]=5;
            dfs(x,y,l/2,4);
            dfs(x,y+l/2,l/2,3);
            dfs(x+l/2,y,l/2,3);
            dfs(x+l/2,y+l/2,l/2,1);
        }
        else if(p==4)
        {
            a[x+l/2-1][y+l/2-1]=5;
            a[x+l/2][y+l/2-1]=5;
            a[x+l/2-1][y+l/2]=5;
            dfs(x,y,l/2,4);
            dfs(x,y+l/2,l/2,3);
            dfs(x+l/2,y,l/2,2);
            dfs(x+l/2,y+l/2,l/2,4);
        }
    }
}

int main()
{
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
    cin>>n>>r>>c;
    if(n==1){cout<<"."<<endl;exit(0);}
    dfs(1,1,n,0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(r==i&&j==c)putchar('.');
            else putchar('A'+a[i][j]);
        }
        putchar('\n');
    }
    return 0;
}