1788

// 2007-02-13 23:21:10    Accepted    1788    C++    00:00.18    3236K // 用时1小时15分，读题时间 =0，第二次做 ，一次AC  /* 用数组存放4-树，Tree[0]为根Tree[i]的四个儿子是Tree[4*i+1],Tree[4*i+2],Tree[4*i+3],Tree[4*i+4]若i!=0，Tree[i]的父亲是Tree[(i-1)/4]设N是输入的矩阵阶数树的高度high=log(N)/log(2)树的总占空间大小为4^0+4^1+4^2+...+4^high=(4^(high+1)-1)/3=(4*N*N-1)/3当N=512时，上式=349525 */ #include  < iostream > #include  < vector > #include  < stack > using   namespace  std; int  Tree[ 349525 ],high,tree_size; int  a[ 512 ][ 512 ],N; int   * treep; void  dfs( int  size, int  i, int  j){     if (size == 1 ){         *-- treep = a[i][j];    }     else  {        dfs(size / 2 ,i + size / 2 ,j + size / 2 );        dfs(size / 2 ,i + size / 2 ,j);        dfs(size / 2 ,i,j + size / 2 );        dfs(size / 2 ,i,j);    }} bool  eq( int  a, int  b, int  c, int  d, int  e){     // printf("%d %d %d %d %d",a,b,c,d,e);      if (a != b) return   0 ;     if (b != c) return   0 ;     if (c != d) return   0 ;     if (d != e) return   0 ;     return   1 ;} int  main(){     int  k;    scanf( " %d " , & k);     while (k -- ){        scanf( " %d " , & N);        high = 0 ;         while (( 1 << high) != N){            high ++ ;        }        tree_size = ( 4 * N * N - 1 ) / 3 ;        treep = Tree + tree_size; // 定位在树的最后一个空间的后面一个位置          for ( int  i = 0 ;i < N;i ++ ){             for ( int  j = 0 ;j < N;j ++ ){                scanf( " %d " , & a[i][j]);            }        }                dfs(N, 0 , 0 ); // 初始化树的叶子结点                  /* 利用叶子结点计算整个树        结点和值的对应方法如下        (0,0)->0,(0,1)->1,1->2,    null->-1 */          int *  treep2 = Tree + tree_size;         while (treep != Tree){            treep2 -= 4 ;             if (eq(treep2[ 0 ],treep2[ 1 ],treep2[ 2 ],treep2[ 3 ], 1 )){                 *-- treep = 1 ;                treep2[ 0 ] = treep2[ 1 ] = treep2[ 2 ] = treep2[ 3 ] =- 1 ;            }             else   if (eq(treep2[ 0 ],treep2[ 1 ],treep2[ 2 ],treep2[ 3 ], 0 )){                 *-- treep = 0 ;                treep2[ 0 ] = treep2[ 1 ] = treep2[ 2 ] = treep2[ 3 ] =- 1 ;            }             else  {                 *-- treep = 2 ;            }        }                 // 将二进制串压入vector，顺序遍历Tree[]即为BFS         vector < int >  V;         for ( int  i = 0 ;i < tree_size;i ++ ){             switch (Tree[i]){             case   0 :                V.push_back( 0 );                                V.push_back( 0 );                 break ;             case   1 :                V.push_back( 0 );                V.push_back( 1 );                 break ;             case   2 :                V.push_back( 1 );                 break ;            }        }                 // 由二进制转换到16进制，压入栈         stack < char >  S;        vector < int > ::iterator p;         for (p = V.end() - 1 ;p >= V.begin();){             int  sum( 0 );             if (p >= V.begin()  &&   * p -- )sum += 1 ;             if (p >= V.begin()  &&   * p -- )sum += 2 ;             if (p >= V.begin()  &&   * p -- )sum += 4 ;             if (p >= V.begin()  &&   * p -- )sum += 8 ;             if ( 0 <= sum  &&  sum < 10 ){                S.push(sum + ' 0 ' );            }             else {                S.push(sum - 10 + ' A ' );            }        }         // 输出          while ( ! S.empty()){            putchar(S.top());            S.pop();        }        putchar( ' ' );    }}