时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
编程计算由“*”号围成的下列图形的面积。面积计算方法是统计*号所围成的闭合曲线中水平线和垂直线交点的数目。如下图所示，在10×10的二维数组中，有“*”围住了15个点，因此面积为15。
【输入】
10×10的图形。
【输出】
输出面积。
【输入样例】
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
【输出样例】
15
1. #include <iostream> 2. #include <cstring> 3. using namespace std; 4. int map[12][12]; 5. int xy_[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; 6. int deq[600][2]; 7. bool book[12][12]; 8. void bfs(int i,int j){ 9. int top,tail,x,y,xx,yy; 10. top=tail=0; 11. memset(deq,0,sizeof(deq)); 12. deq[tail][0]=i;deq[tail][1]=j;tail++; 13. while(tail>top){ 14. x=deq[top][0];y=deq[top][1];book[x][y]=true; 15. for(int k=0;k<4;k++){ 16. xx=x+xy_[k][0];yy=y+xy_[k][1]; 17. if(xx>=1&&xx<=10&&yy>=1&&yy<=10&&map[xx][yy]==0&&!book[xx][yy]){ 18. deq[tail][0]=xx;deq[tail][1]=yy;tail++;book[xx][yy]=true; 19. } 20. } 21. map[x][y]=1;top++; 22. } 23. } 24. int sun_(){ 25. int sum=0; 26. for(int i=1;i<=10;i++) 27. for(int j=1;j<=10;j++) 28. if(map[i][j]==0&&!book[i][j]) sum++; 29. return sum; 30. } 31. int main(int argc, char *argv[]) 32. { 33. for(int i=1;i<=10;i++) 34. for(int j=1;j<=10;j++) 35. cin>>map[i][j]; 36. for(int i=1;i<=10;i++){ 37. if(map[1][i]==0)bfs(1,i); 38. if(map[10][i]==0)bfs(10,i); 39. if(map[i][1]==0)bfs(i,1); 40. if(map[i][10]==0)bfs(i,10); 41. } 42. cout<<sun_()<<endl; 43. return 0; 44. }
