1482.txt

自己AC的zju_acm上的若干个题目,都是自己辛辛苦苦AC的。

#include <stdio.h> 

struct part 
{ 
   struct part* father; 
   struct part* previous; 
   int line; 
   int id; 
   struct part* next; 
}grid[2002][2]; 

int nowline,lastline,total; 
int n,num; 
part* temp,*father,*father2; 

void del(int now,int line) 
{ 
   int i; 
   int flag; 
   for(i = 1;i <= n;i++) 
      if(grid[i][now].id != 0) 
      { 
         flag = 1; 
         father = grid[i][now].father; 
         num = father->id; 
         if(father->next != NULL) 
         { 
            temp = father->next; 
            while(temp->next != NULL) 
            { 
               if(temp->line != line) 
               { 
                  temp->next->previous = temp->previous; 
                  temp->id = 0; 
                  temp->previous->next = temp->next; 
                  --num; 
               } 
               else 
                  flag = 0; 
               temp = temp->next; 
            } 
            if(flag) 
            { 
               if(temp->line != line) 
               { 
                  if(father->line != line) 
                  { 
                     father->id = 0; 
                     ++total; 
                  } 
                  temp->id = 0; 
                  father->next = NULL; 
                  father->previous = father; 
                  father->id = 1; 
               } 
               else 
                  if(father->line != line) 
                  { 
                     father->id = 0; 
                     temp->previous = temp; 
                     temp->father = temp; 
                     temp->id = 1; 
                  } 
            } 
            else 
            { 
               flag = 1; 
               if(temp->line != line) 
               { 
                  temp->id = 0; 
                  temp->previous->next = NULL; 
                  father->id = num - 1; 
                  if(father->line != line) 
                  { 
                     father->id = 0; 
                     father = father->next; 
                     temp = father; 
                     while(temp->next != NULL) 
                     { 
                        temp->father = father; 
                        temp = temp->next; 
                     } 
                     temp->father = father; 
                     father->previous = temp; 
                     father->id = num - 2; 
                  } 
               } 
               else 
                  if(father->line != line) 
                  { 
                     father->id = 0; 
                     father = father->next; 
                     temp = father; 
                     while(temp->next != NULL) 
                     { 
                        temp->father = father; 
                        temp = temp->next; 
                     } 
                     temp->father = father; 
                     father->previous = temp; 
                     father->id = num - 1; 
                  } 
            } 
         } 
         else 
         { 
            father->id = 0; 
            ++total; 
         } 
      } 
} 

void link1(int row) 
{ 
   temp = father->previous; 
   temp->next = &grid[row][nowline]; 
   father->previous = temp->next; 
   ++father->id; 
   grid[row][nowline].father = father; 
   grid[row][nowline].next = NULL; 
   grid[row][nowline].previous = temp; 
} 

void connect(int row) 
{ 
   if(father->id < father2->id) 
   { 
      temp = father; 
      father = father2; 
      father2 = temp; 
   } 
   father->id += father2->id + 1; 
   temp = father2->previous; 
   temp->next = &grid[row][nowline]; 
   grid[row][nowline].next = NULL; 
   grid[row][nowline].previous = temp; 
   temp = father->previous; 
   father2->previous = temp; 
   temp->next = father2; 
   temp = father2; 
   while(temp->next != NULL) 
   { 
      temp->father = father; 
      temp = temp->next; 
   } 
   temp->father = father; 
   father->previous = temp; 
} 


int main() 
{ 
   int i,j; 
   int temp; 
   scanf("%d",&n); 
   nowline = 0; 
   total = 0; 
   for(i = 0;i < n + 1;i++) 
      grid[i][nowline].id = 0; 
   lastline = nowline; 
   nowline = 1 - nowline; 
   for(j = 1;j <= n;j++) 
   { 
      grid[0][nowline].id = 0; 
      for(i = 1;i < n + 1;i++) 
      { 
         scanf("%d",&temp); 
         if(!temp) 
         { 
            grid[i][nowline].line = j; 
            grid[i][nowline].id = 1; 
            if((grid[i][lastline].id != 0) && (grid[i - 1][nowline].id != 0)) 
            {    
               if(grid[i][lastline].father != grid[i - 1][nowline].father) 
               { 
                  father = grid[i][lastline].father; 
                  father2 = grid[i - 1][nowline].father; 
                  connect(i); 
               } 
               else 
               { 
                  father = grid[i][lastline].father; 
                  link1(i); 
               } 
            } 
            else 
            { 
               if(grid[i][lastline].id != 0) 
               { 
                  father = grid[i][lastline].father; 
                  link1(i); 
               } 
               else 
                  if(grid[i - 1][nowline].id != 0) 
                  { 
                     father = grid[i - 1][nowline].father; 
                     link1(i); 
                  } 
                  else 
                  { 
                     grid[i][nowline].father = &grid[i][nowline]; 
                     grid[i][nowline].next = NULL; 
                     grid[i][nowline].previous = &grid[i][nowline]; 
                  } 
            } 
         } 
         else 
            grid[i][nowline].id = 0; 
      } 
      del(lastline,j); 
      lastline = nowline; 
      nowline = 1 - nowline; 
   } 
   for(i = 0;i < n + 1;i++) 
      grid[i][nowline].id = 0; 
   del(lastline,j); 
   printf("%d\n",total); 
   return 0; 
}