四叉樹
| 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( 0, 0, 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 ;
}