题目

Description

地质探测公司负责探测地下石油资源，每次在一块矩形的区域上查找。探测人员用把这块矩形区域分成 了N X M个正方形小块，然后对每个正方形小块分别进行分析，经过分析之后，为每个小块都做了一个标记，如果一个小块地下发现有石油，则用“@”标记,否则用”.标记”。如果两个含有石油的小块是相邻的，那么它们属于同一块石油地，这里的相邻包括水平，垂直，或者对角相邻。给定一块已经标记过的矩形区域，你的任务是找出这块区域上的石油地的个数

Input

本题有多组输入数据。对于每一组输入数据，第一行输入两个数M，N，（1<=M,N<=100）,接下来是M行，每行含有N个字符,每个字符要么是“@”,要么是”*”。

Output

对于每组数据，输出一行，包含一个整数,它表示石油的地块数

Sample Input

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

Sample Output

0
1
2
2

题解

POJ 1562 Oil Deposits 的中文版

读入后遍历所有位置,如果从未访问过并且有油井,则记录
同时递归遍历其相邻所有位置放置访问标记

这道题在AOJ上的输入结束不是 0 0
应该使用 EOF 判断

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com
 
かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;
 
const int maxn = 105;
 
char Map[maxn][maxn];
int cnt;
int m,n;
 
void DFS(int i,int j) {
    Map[i][j] = '*';
    for(int d1 = -1;d1 <= 1;d1++)
        for(int d2 = -1;d2 <= 1;d2++)
            if(!(d1 == 0 && d2 == 0))
                if(i + d1 >= 0 && i + d1 < n &&
                    j + d2 >= 0 && j + d2 < m)
                    if(Map[i + d1][j + d2] == '@')
                        DFS(i + d1,j + d2);
}
 
bool Do() {
    if(scanf("%d%d",&n,&m) == EOF)
        return false;
    if(m == 0 || n == 0)
        return false;
 
    cnt = 0;
 
    for(int i = 0;i < n;i++)
        scanf("\n%s",&Map[i]);
 
    for(int i = 0;i < n;i++)
        for(int j = 0;j < m;j++)
            if(Map[i][j] == '@') {
                cnt++;
                DFS(i,j);
            }
 
    printf("%d\n",cnt);
    return true;
}
 
int main() {
    while(Do());
    return 0;
}