acm勘探油田描述某石油勘探公司正在按计划勘探地下油田资源.他们工作在一片长方形的地域中,首先将该地域划分为许多小正方形区域,然后使用探测设备分别探测每一块小正方形区域是否有

Question

acm 勘探油田
描述某石油勘探公司正在按计划勘探地下油田资源.他们工作在一片长方形的地域中,首先将该地域划分为许多小正方形区域,然后使用探测设备分别探测每一块小正方形区域是否有油.若在一块小正方形区域中探测到有油,则标记为’@’,否则标记为’*’.如果两个相邻区域都为1,那么它们同属于一个石油带,一个石油带可能包含很多小正方形区域,而你的任务是要确定在一片长方形地域中有多少个石油带.所谓相邻,是指两个小正方形区域上下、左右、左上右下或左下右上同为’@’.输入输入数据将包含一些长方形地域数据,每个地域数据的第一行有两个正整数m和n,表示该地域为m*n个小正方形所组成,如果m为0,表示所有输入到此结束.否则,后面m（1≤m≤100）行数据,每行有n（1≤n≤100）个字符,每个字符为’@’或’*’,表示有油或无油.每个长方形地域中,’@’的个数不会超过100.输出每个长方形地域,输出油带的个数,每个油带值占独立的一行.油带值不会超过100.样例输入3 5 *@*@* **@** *@*@* 0 0 样例输出1 解题报告

Answer 1

简单的搜索题,可以用DFS解决.以下是我的代码,LZ可以看一下： #include
#includeusing namespace std;const int N=105;char s[N][N];
bool map[N][N];
int d[8][2]={1,0,0,1,-1,0,0,-1,1,1,1,-1,-1,1,-1,-1};
int n,m;void dfs(int x,int y)
{
int i,tx,ty;
map[x][y]=false;
i=0;
while(i=0&&ty>=0&&tx