gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks

四叉树
Memory: 492K Time: 110MS
Language: C++ Result: Accepted

没能分析出数据的隐藏信息,处理的时候显得很笨重,速度又慢
#include <stdio.h>
#include 
<string>
using namespace std ;

const int MAXN = 520 ;
const int SIZE = 300000 ;

const char TABLE[16= '0''1''2''3''4''5''6',
            
'7''8''9''A''B''C''D''E''F' }
 ;
//四叉树节点结构
struct NODE
{
    
char m_flag ; //状态
    int m_fpos ;  //四个儿子的位置
    int m_spos ;
    
int m_tpos ;
    
int m_fopos ;
}
Msg[SIZE];

int g_MP ;
int N ;
char map[MAXN][MAXN] ;
string RMsg ;
char hexArray[65000] ;
//判断子孙节点的状态
int Analyse( const int& a, const int& b )
{
    
int mark = 0 ;
    
if ( a == 1 ){
        mark 
= 5 ;
    }

    
else if ( b == 1 )
    
{
        mark 
= 1 ;
    }


    
return mark ;
}

//对图像进行分割,记录四叉树的节点信息
int Divide( const int& lx, const int& ly, const int& rx, const int& ry, int& _a, int& _b )
{
    _a 
= _b = 0 ;

    
if ( lx >= rx ){
        Msg[g_MP
++].m_flag = '0' ;
        
if ( map[lx][ly] == '1' )
        
{
            _b 
= 1 ;            
            Msg[g_MP
++].m_flag = '1' ;
        }

        
else {
            Msg[g_MP
++].m_flag = '0' ;
        }

        
return g_MP - 2;
    }

    
else {
        
int a , b , c , d , t , midx , midy ;
        
int pos = g_MP ;
        g_MP
++ ;

        midx 
= (( rx + lx ) >> 1) ;
        midy 
= (( ry + ly ) >> 1) ;

        Msg[pos].m_fpos 
= Divide( lx, ly, midx, midy, _a, _b ) ;
        a 
= Analyse( _a, _b ) ;

        Msg[pos].m_spos 
= Divide( lx, midy + 1, midx, ry, _a, _b ) ;
        b 
= Analyse( _a, _b ) ;

        Msg[pos].m_tpos 
= Divide( midx + 1, ly, rx, midy, _a, _b ) ;
        c 
= Analyse( _a, _b ) ;

        Msg[pos].m_fopos 
= Divide( midx + 1, midy + 1, rx, ry, _a, _b ) ;
        d 
= Analyse( _a, _b ) ;

        t 
= a + b + c + d ; 

        
if ( t == 4 )  //全为1
        {
            _a 
= 0 ;
            _b 
= 1 ;
            Msg[pos].m_flag 
= '0' ;
            Msg[pos 
+ 1].m_flag = '1' ;
            g_MP 
= pos + 2 ;
        }

        
else if ( t == 0 ) //全为0
        {
            _a 
= _b = 0 ;
            Msg[pos].m_flag 
= '0' ;
            Msg[pos 
+ 1].m_flag = '0' ;
            g_MP 
= pos + 2 ;
        }

        
else if ( t != 0 ) //有分支
        {
            _a 
= 1 ;
            _b 
= 0 ;
            Msg[pos].m_flag 
= '1' ;
        }


        
return pos ;
    }

}

//转化成四叉树表达式
void Reverse( )
{
    
const int MAX = 5000 ;
    
int Q[MAX], h = 0 , t = 1 ;

    Q[
0= 0 ;

    
while ( h != t )
    
{
        
int x = Q[h] ;
        h 
= ( h + 1 ) % MAX ;

        
if ( Msg[x].m_flag == '1' )
        
{
            RMsg 
= '1' + RMsg ;
            Q[t] 
= Msg[x].m_fpos ;
            t 
= ( t + 1 ) % MAX ;
            Q[t] 
= Msg[x].m_spos ;
            t 
= ( t + 1 ) % MAX ;
            Q[t] 
= Msg[x].m_tpos ;
            t 
= ( t + 1 ) % MAX ;
            Q[t] 
= Msg[x].m_fopos ;
            t 
= ( t + 1 ) % MAX ;

        }

        
else {
            RMsg 
= Msg[x].m_flag + RMsg ;
            RMsg 
= Msg[x + 1].m_flag + RMsg ;
        }

    }

}

//用16进制表示
void Turn()
{
    
int i , j , k , m , t ;
    
    k 
= 0 ;
    
for ( i = 0 ; i < g_MP ; i += 4 )
    
{
        m 
= 1 ;
        t 
= 0 ;
        
for ( j = i ; m <= 8 && j < g_MP ; ++j )
        
{
            t 
= t + (RMsg.at(j) - '0'* m ;
            m 
= ( m << 1 ) ;
        }


        hexArray[k
++= TABLE[t] ;
    }


    
for ( i = k - 1 ; i >= 0 ; --i )
    
{
        printf(
"%c", hexArray[i]) ;
    }

    printf(
"\n") ;
}


void Init()
{
    g_MP 
= 0 ;
    Msg[
0].m_flag = 0 ;
    RMsg 
= "\0" ;
}


void Work()
{
    
int a, b ;

    Divide( 
00, N - 1, N - 1 , a, b ) ;

    Reverse() ;

    Turn() ;
}


int main()
{
    
int t , i , j ;

//    freopen("in.txt", "r", stdin) ;

    scanf(
"%d"&t) ;

    
while ( t != 0 )
    
{
        scanf(
"%d"&N) ;
        getchar() ;

        Init() ;

        
for ( i = 0 ; i < N ; ++i )
        
{
            
for ( j = 0 ; j < N ; ++j )
            
{
                scanf(
"%c "&map[i][j]) ;
            }

        }

        
        Work() ;
        t
-- ;
    }

    
return 0 ;
}
posted on 2008-11-01 20:47 阅读(264) 评论(0)  编辑 收藏 引用 所属分类: 与Tree相关的题

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理