算法：位图填充

题目：这是一道用于解决图形处理上的一个算法实例，要求占用最小的空间和最高的效率来实现。

假设有N×N的一个数字矩阵，矩阵中的每一个元素可能为0或者1。初始化状态下，整个矩阵都为0。现在要对矩阵中的N个元素赋值为1，这N个元素的选取方法如下：从矩阵最中间的4个元素组成的小正方形左上角的那个元素开始，依次顺时针旋转，所经元素均赋值为1，直到经过了N个元素为止。
一圈旋转完之后继续接着它旋转，具体示例如下：

Input N: 4             Input N: 6          Input N: 7
0 0 0 0 0 0 0 0     0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0     0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0     0 0 0 0 0 0 0 0   0 0 1 0 0 0 0 0
0 0 0 1 1 0 0 0     0 0 1 1 1 0 0 0   0 0 1 1 1 0 0 0
0 0 0 1 1 0 0 0     0 0 1 1 1 0 0 0   0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0     0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0     0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0     0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0

/* ---------------------------------------------------------------*
* luoxuan.cpp                                                     *
* author: smileonce                                               * 
* my email: smileonce126com                              *
* date : 2004-9-19                                                *
*----------------------------------------------------------------*/ 

#include  
using namespace std; 

#define MAX 8 
typedef char BYTE; 

void clearMatrix(BYTE*); 
void printMatrix(BYTE*); 
void makeMatrix(BYTE*, int); 


int main() 
{ 
   BYTE a[MAX] = {0}; 
   int n = 0; 
   while( n < 64 ) 
   { 
       clearMatrix(a); 
       cout << "Input N: "; 
       cin >> n; 
       makeMatrix(a, n); 
       printMatrix(a); 
   } 
   return 0; 
} 


void makeMatrix(BYTE * a, int n) 
{ 
   int i, j, k; 

   int o_left, o_right, i_left, i_right; // find the area that we want filled. 
                                         // o_ is for outside, i_ is for inside 
                                         // _left is for leftside, _right is for rightside 
    int i_size;                          // the inside area size 
 
   for( i=2; i*i<=n; i+=2) 
       ; 
   i_size  = (i-2) * (i-2);              // remember the size of inside square 
 
   i_left  = MAX/2 - i/2 +1; 
   i_right = MAX - i_left - 1; 
   o_left  = i_left - 1; 
   o_right = i_right + 1; 

   //------ fill inside area of the matrix 
   //-- set the mask 
    for (i=0, j=0x01; i <= i_left - 1; i++, j <<= 1) 
       ; 
   for (i=0, k=0; i<i_right-i_left+1; i++, j<<=1 ) 
       k += j; 
   //-- fill by using mask 
    for (i=i_left; i<=i_right; i++) 
       *(a+i) = *(a+i) | k; 

   //------ fill outside area of the matrix 
    n -= i_size ;                                //this is the count of outside print steps 
   //---- left 
    for (k= 0x01<<o_left, i=i_right; n >0 && i>o_left; i--, n--) 
     *(a+i) |= k; 
   //---- top     
    if (n==0) return; 
   for (j = 0x01<<o_left, i=o_left, k=0; n >0 && i<o_right; i++, j<<=1, n--) 
       k+=j; 
   *(a+o_left) |= k; 
   //---- right         
    for (k = 0x01<<o_right, i=o_left; n >0 && i<o_right; i++, n--) 
       *(a+i) |= k; 
   //---- bottom 
    if (n==0) return; 
   for (j = 0x01<<o_right, i=o_right, k=0 ; n >0 && i>o_left; i--, j>>=1, n--) 
       k+=j; 
   *(a+o_right) |= k; 

} 


// print the matrix, for testing. 
void printMatrix(BYTE *a) 
{ 
   int i, j, k; 
   for (i=0; i<MAX; i++) 
   { 
       for (j=0, k= 0x01; j<MAX; j++, k<<=1) 
           if ( *(a+i) & k ) 
               cout << "1" << " "; 
           else cout << "0" << " "; 
       cout << endl; 
   }     
   cout << endl; 
} 


//initialize the matrix, make every bit is 0 
void clearMatrix(BYTE *a) 
{ 
   int i; 
   for (i=0; i<MAX; i++) 
       *(a+i) = 0x00; 
} 

--------------------next---------------------