原题网址:https://begin.lydsy.com/JudgeOnline/problem.php?cid=1311&pid=1
密码:20192019
本蒟蒻第二次发题解,依旧不好意思,若有错误欢迎各位神犇指出,本蒟蒻不胜感激。
题目描述如下:
Time Limit: 1 Sec Memory Limit: 128 MB
Description
一幅图由0和* 组成,编程计算由* 号所围成的图形的面积。面积的计算方法是统计* 号所围成的闭合曲线中0的数目。
Input
由0和组成的字符矩阵,行列数均不超过50。对于此种输入方式,输入完成后按ctrl+z结束。
Output
面积数
Sample Input
input 1
000000000
0000**000
0000000
0000000
000000
000000000
input 2
000000000000000
00000000000000000000000000000
000000*****************00000000
0000000000000000000000000000000
Sample Output
output 1
5
output 2
59
刚看到这题时,马上第一反应bfs,然而,由于本蒟蒻bfs很渣,所以用了一种dfs,也就是先让它外面包一圈0,然后从左上角开始搜起,时间复杂度比bfs还略少点,并且不需要搜一圈,请各位各位多看下题目,本题输入极其恶心,需要注意。
好了,本题C++代码如下:
#include <iostream>
using namespace std;char a;
int i,j,k,l,ans;
int v[52][52];void dfs(int x,int y) {if(v[x][y]==1) return;v[x][y]=1;if(x>1) dfs(x-1,y);if(y>1) dfs(x,y-1);if(x<=k) dfs(x+1,y);if(y<=l) dfs(x,y+1);
}int main()
{k=1,l=1;while(scanf("%c",&a)!=EOF) //ctrl+z停止读入{if(a=='\n') k++,l=j,j=0;else j++;if(a=='*') v[k][j]=1;}k-=1;dfs(0,0);for(int i=1;i<=k;i++)for(int j=1;j<=l;j++)if(v[i][j]==0) ans++;printf("%d",ans);return 0;
}
本代码为标程,请勿抄袭。
若有不善之处,还请各位神犇指出。
鸣谢!!!