P1911 L国的战斗之排兵布阵

1、思路

①当n为1时，很简单直接输出；

②当n为2时，无非下边四种情况
其他情况可以通过旋转得到。而上图黑色框与n=1时的情况等价。
③当n为3时，

2、代码

#include<iostream>
using namespace std;
static int c = -1;
void solve(int **a, int temp1, int special, int x1, int y1, int x, int y){//注：输入指挥营位置下标从0开始
    if(temp1 == 2){
        a[x1][y1] = c;
        a[x1+1][y1] = c;
        a[x1][y1+1] = c;
        a[x1+1][y1+1] = c;
        a[x][y] = special;
        --c;
        return;
    }else if(temp1 == 4){
        if(x < x1 + 2){
            if(y < y1 + 2){
                solve(a, 2, special, x1, y1, x, y);
                a[x1][y1 + 2] = a[x1][y1 + 3] = a[x1 + 1][y1 + 3] = c;
                a[x1 + 1][y1 + 2] = a[x1 + 2][y1 + 1] = a[x1 + 2][y1 + 2] = c - 1;
                a[x1 + 2][y1] = a[x1 + 3][y1] = a[x1 + 3][y1 + 1] = c - 2;
                a[x1 + 3][y1 + 2] = a[x1 + 2][y1 + 3] = a[x1 + 3][y1 + 3] = c - 3;
            }else{
                solve(a, 2, special, x1, y1 + 2, x, y);
                a[x1][y1] = a[x1][y1 + 1] = a[x1 + 1][y1] = c;
                a[x1 + 1][y1 + 1] = a[x1 + 2][y1 + 1] = a[x1 + 2][y1 + 2] = c - 1;
                a[x1 + 2][y1] = a[x1 + 3][y1] = a[x1 + 3][y1 + 1] = c - 2;
                a[x1 + 3][y1 + 2] = a[x1 + 2][y1 + 3] = a[x1 + 3][y1 + 3] = c - 3;
            }
        }else{
            if(y < y1 + 2){
                solve(a, 2, special, x1 + 2, y1, x, y);
                a[x1][y1] = a[x1][y1 + 1] = a[x1 + 1][y1] = c;
                a[x1][y1 + 2] = a[x1][y1 + 3] = a[x1 + 1][y1 + 3] = c - 1;
                a[x1 + 1][y1 + 1] = a[x1 + 1][y1 + 2] = a[x1 + 2][y1 + 2] = c - 2;
                a[x1 + 3][y1 + 2] = a[x1 + 2][y1 + 3] = a[x1 + 3][y1 + 3] = c - 3;
            }else{
                solve(a, 2, special, x1 + 2, y1 + 2, x, y);
                a[x1][y1] = a[x1][y1 + 1] = a[x1 + 1][y1] = c;
                a[x1][y1 + 2] = a[x1][y1 + 3] = a[x1 + 1][y1 + 3] = c - 1;
                a[x1 + 1][y1 + 1] = a[x1 + 1][y1 + 2] = a[x1 + 2][y1 + 1] = c - 2;
                a[x1 + 2][y1] = a[x1 + 3][y1] = a[x1 + 3][y1 + 1] = c - 3;
            }
        }
        c -= 4;
        return;
    }else{
        int temp2 = temp1 / 2, temp3 = c;
        --c;
        if(x < x1 + temp2){
            if(y < y1 + temp2){
                solve(a, temp2, temp3, x1 + temp2, y1 + temp2, x1 + temp2, y1 + temp2);
                solve(a, temp2, temp3, x1, y1 + temp2, x1 + temp2 - 1, y1 + temp2);
                solve(a, temp2, temp3, x1 + temp2, y1, x1 + temp2, y1 + temp2 - 1);
                solve(a, temp2, special, x1, y1, x, y);
            }else{
                solve(a, temp2, temp3, x1, y1, x1 + temp2 - 1, y1 + temp2 - 1);
                solve(a, temp2, temp3, x1 + temp2, y1, x1 + temp2, y1 + temp2 - 1);
                solve(a, temp2, temp3, x1 + temp2, y1 + temp2, x1 + temp2, y1 + temp2);
                solve(a, temp2, special, x1, y1 + temp2, x, y);
            }
        }else{
            if(y < y1 + temp2){
                solve(a, temp2, temp3, x1, y1, x1 + temp2 - 1, y1 + temp2 - 1);
                solve(a, temp2, temp3, x1, y1 + temp2, x1 + temp2 - 1, y1 + temp2);
                solve(a, temp2, temp3, x1 + temp2, y1 + temp2, x1 + temp2, y1 + temp2);
                solve(a, temp2, special, x1 + temp2, y1, x, y);
            }else{
                solve(a, temp2, temp3, x1, y1, x1 + temp2 - 1, y1 + temp2 - 1);
                solve(a, temp2, temp3, x1, y1 + temp2, x1 + temp2 - 1, y1 + temp2);
                solve(a, temp2, temp3, x1 + temp2, y1, x1 + temp2, y1 + temp2 - 1);
                solve(a, temp2, special, x1 + temp2, y1 + temp2, x, y);
            }
        }
    }
}
int main(){
    int n, x, y, i, j, temp1 = 2, count = 1;
    cin>>n>>x>>y;

    while(--n > 0) temp1 = temp1 << 1;
    
    int **a = new int *[temp1];
    int **mask = new int *[temp1];
    for(i = 0; i < temp1; ++i){
        a[i] = new int [temp1];
        mask[i] = new int [temp1]();//全部初始化为0
    }
    mask[x - 1][y - 1] = 1;
    
    solve(a, temp1, 0, 0, 0, x - 1, y - 1);

    for(i = 0; i < temp1; ++i){//重新排序并输出
        for(j = 0; j < temp1; ++j){
            if((i == x - 1 && j == y - 1) || mask[i][j] != 0){
                cout<<a[i][j]<<" ";
                continue;
            }
            if(i + 1 < temp1 && mask[i + 1][j] == 0 && a[i + 1][j] == a[i][j]){
                if(j - 1 >= 0 && mask[i + 1][j - 1] == 0 && a[i + 1][j - 1] == a[i][j]){
                    a[i + 1][j] = a[i][j] = a[i + 1][j - 1] = count;
                    mask[i + 1][j] = mask[i][j] = mask[i + 1][j - 1] = 1;
                }else if(mask[i + 1][j + 1] == 0 && a[i + 1][j + 1] == a[i][j]){
                    a[i + 1][j] = a[i][j] = a[i + 1][j + 1] = count;
                    mask[i + 1][j] = mask[i][j] = mask[i + 1][j + 1] = 1;
                }else{
                    a[i + 1][j] = a[i][j] = a[i][j + 1] = count;
                    mask[i + 1][j] = mask[i][j] = mask[i][j + 1] = 1;
                }
            }else{
                a[i][j + 1] = a[i][j] = a[i + 1][j + 1] = count;
                mask[i][j + 1] = mask[i][j] = mask[i + 1][j + 1] = 1;
            }
            ++count;
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    for(int i = 0; i < temp1; ++i)//释放内存空间
    {
        delete [] a[i]; 
        delete [] mask[i]; 
    }
    return 0;
}

3、可改进

我这个解法相当于把n=2当作递归的边界，其实n=2也可以划分为四个n=1的情况，所以可以进一步将n=1作为递归的边界；可以不用静态变量；