题目描述
编程计算由"1"围成的下列图形的面积。面积计算方法是统计"1"所围成的闭合曲线中"0"点的数目。如图所示，在10*10的二维数组中，"1"围住了15个点，因此面积为15。
提示：queue
输入
测试次数t
每组测试数据格式为：
数组大小m,n
一个由0和1组成的m*n的二维数组
输出
对每个二维数组，输出符号"1"围住的"0"的个数，即围成的面积。假设一定有1组成的闭合曲线，但不唯一。
输入样例1
2 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 5 8 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0
输出样例1
15 5
思路分析
我看了一下，好像有两种思路，一个是用BFS，一个是到处走。但都是把0变1实现的。我没看出来这道题和图有什么关系？
用BFS的，是在外围扩大一圈0，这样可以走进去。
我用的是到处乱走法（思路并非我首创，但名字应该是），我从四面八方开始走，只要我能到达的地方，通通由0变1，直到碰到1，即使碰到1，我也会上下左右乱窜。
之后数一下0的个数，输出即可。
AC代码
代码语言：javascript复制#include<iostream>
using namespace std;
const int max_len=100;
class Map{
int m,n,area=0;
int volume[max_len][max_len]={0};
public:
Map(){
cin>>m>>n;
for(int i=0;i<m;i )
for(int j=0;j<n;j )
cin>>volume[i][j];
}
void ToFullPath(int x,int y){
if(x<0||y<0||x>=m||y>=n||volume[x][y])
return;
volume[x][y]=1;
ToFullPath(x,y 1);
ToFullPath(x,y-1);
ToFullPath(x-1,y);
ToFullPath(x 1,y);
}
void AllPathCount(){
for(int i=0;i<m;i ){
ToFullPath(i,0);
ToFullPath(i,n-1);
}
for(int i=0;i<n;i ){
ToFullPath(0,i);
ToFullPath(m-1,i);
}
for(int i=0;i<m;i )
for(int j=0;j<n;j )
if(!volume[i][j])
area ;
cout<<area<<endl;
}
};
int main() {
int t;
cin>>t;
while(t--){
Map test;
test.AllPathCount();
}
return 0;
}
