P1911

loverintime · 2021-12-18 21:04:27 · 题解

这是一道简单分治题， 但是大部分人的代码都在 2k 左右。 而我的代码只有 743B。 至少现在看来， 我的代码长度是完全比其他所有人少一大截的。

如何减短代码长度？ 有一点很重要： 尽量少写重复的部分。 现在所有的题解都是枚举中心点在哪里。 其实， 仔细想想， 不管中心点在哪里， 其他三块的处理方式是一样的， 所以没有必要打四遍， 只需要依次处理四个部分即可。

还有最后重新编码， 根本不需要再搜索一次， 只需要按顺序遍历， 用一个数组映射即可。

有人会问， 代码短一点有什么好处。 这倒题比较简单， 但做到后来更难， 码量更大的时候， 代码段的好处就体现出来了： 更好调试。

本题解并不说明这道题怎么去做（想知道的话看其他人写的）， 只是希望大家养成比较好的代码习惯， 这样在调试更难的题的时候才可以更加轻松。

放上我的代码：

#include<bits/stdc++.h>
const int N=(1<<10)+5;
int n,x,y;
int A[N][N],cnt,p[N*N],tot;
const int dx[4]={0,1,0,1},dy[4]={0,0,1,1},cox[4]={1,0,1,0},coy[4]={1,1,0,0};
void dfs(int x,int y,int c,int a,int b){
    if(c==0) return;c--;int t=++cnt;
    for(int i=0; i<4; i++){
        int nx=x+(dx[i]<<c),ny=y+(dy[i]<<c),f=nx+(cox[i]<<c)-cox[i],g=ny+(coy[i]<<c)-coy[i];
        if(a>=nx&&a<nx+(1<<c)&&b>=ny&&b<ny+(1<<c)) dfs(nx,ny,c,a,b);
        else dfs(nx,ny,c,f,g),A[f][g]=t;
    }
}
int main(){
    scanf("%d%d%d",&n,&x,&y);
    dfs(1,1,n,x,y);
    for(int i=1; i<=1<<n; i++) for(int j=1; j<=1<<n; j++){
        if(i!=x||j!=y){
            if(!p[A[i][j]]) p[A[i][j]]=++tot;
            printf("%d ",p[A[i][j]]);
        }
        else printf("0 ");
        if(j==(1<<n)) puts("");
    } 
    return 0;
}