【寒假坚持学习鸭】2.5日 非二叉树(两种表示方法)

题目：Uva-806 Spatial Structures
tag：递归建树，进制转换
题目大意： 一个n * n(n <= 64) 的正方形网格可以映射成一颗四叉树， 根节点对应整个区域。如果当前点对应的区域全为黑格子或者白色格子，就没有子节点，节点颜色即为格子颜色， （当然题目中黑色是1白色是0）， 有黑有白就是灰色并且有4个子节点分别对应4个边长一半的正方形区域，由此形成一颗四叉树，然后 每个从每个子节点出发回到根的路径（每个节点的4个4节点的边编号为1,2,3,4）， 看做一个5进制数。现在有两种输入， 1），给你一颗树，让你输出所有黑色子节点对应路径的5进制数转换十进制然后排序之后的结果； 2）， 给你每个黑色子节点路径对应的十进制数，输出二位正方形图。

思路：图转树用dfs，传的参数是当前已经走的路径（避免全局变量的回溯）， 当前访问的正方形边长， 以及当前访问的正方形的左上角点的横纵坐标，有了边长和起点的横纵坐标就可以很容易的遍历当前的正方形从而判断该点是什么颜色以及是否有子节点； 至于树转图就比较简单了反过来就是，根据十进制转5进制就可以得出路径长度以及对应区域，然后标记01就是。
-来源于：https://blog.csdn.net/zz_black/article/details/48300019
https://www.cnblogs.com/20143605–pcx/p/4858658.html

# include<iostream>
# include<cstdio>
# include<vector>
# include<string>
# include<cstring>
# include<algorithm>
using namespace std;
 
char p[80][80];
int ans;
vector<int>v;
 
int get(int r,int c,int w)
{
   
    int cnt=0;
    for(int i=r;i<r+w;++i)
        for(int j=c;j<c+w;++j)
            if(p[i][j]=='1')
                ++cnt;
    return cnt;
}
 
int getVal(string path)
{
   
    int l=path.size();
    int res=0;
    for(int i=l-1;i>=0;--i)//注意顺序
        res=res*5+path[i]-'0';
    return res;
}
 
///查看以(r,c)为左上角，边长为w的子正方形。下同。
void f1(int r,int c,int w,string path)
{
   
    int k=get(r,c,w);
    if(k==0)
        return ;
    if(k==w*w){
   
        ++ans;
        v.push_back(getVal(path));
        return ;
    }
    f1(r,c,w/2,path+'1');
    f1(r,c+w/2,w/2,path+'2');
    f1(r+w/2,c,w/2,path+'3');
    f1(r+w/2,c+w/2,w/2,path+'4');
}
 
void f2(int r,int c,int w,int s)
{
   
    if(s==0){
   
        for(int i=r;i<r+w;++i)
            for(int j=c;j<c+w;++j)
                p[i][j]='*';
        return ;
    }
    int mod=s%5;
    if(mod==1)
        f2(r,c,w/2,s/5);
    else if(mod==2)
        f2(r,c+w/2,w/2,s/5);
    else if(mod==3)
        f2(r+w/2,c,w/2,s/5);
    else if(mod==4)
        f2(r+w/2,c+w/2,w/2,s/5);
}
 
int main()
{
   
    //freopen("UVA-806 Spatial Structures.txt","r",stdin);
    int n,cas=0,flag=0;
    while(scanf("%d",&n)&&n)
    {
   
        v.clear();
        if(flag)
            printf("\n");
        flag=1;
        if(n>0){
   
            for(int i=0;i<n;++i)
                scanf("%s",p[i]);
            printf("Image %d\n",++cas);
            ans=0;
            f1(0,0,n,"");
            sort(v.begin(),v.end());
            int l=v.size();
            for(int i=0;i<l;++i)
                printf("%d%c",v[i],(i%12==11||i==l-1)?'\n':' ');
            printf("Total number of black nodes = %d\n",ans);
        }
        if(n<0){
   
            n=-n;
            for(int i=0;i<n;++i)
                for(int j=0;j<n;++j)
                    p[i][j]='.';
            int a;
            while(scanf("%d",&a)&&a!=-1)
                v.push_back(a);
            printf("Image %d\n",++cas);
            int l=v.size();
            for(int i=0;i<l;++i)
                f2(0,0,n,v[i]);
            for(int i=0;i<n;++i)
                puts(p[i]);
        }
    }
    return 0;
}