#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("%dn",total); return 0; }
