Oil Deposits

6586 ワード

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82828#problem/L
Oil Deposits
Time Limit:1000 MS     メモリLimit:32768 KB     64 bit IO Format:%I 64 d&%I 64 u
Submit 
Status
Description
The GeoSurvComp geologic survey company is reponsible for detecting undeground oid deposits.GeoSurvComp works with one large rectanglar of land at a time,and creates a gride a Dividers thenzers。お客様のニーズに対応しています。お客様のニーズニーズに対応しています。A plot containininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininmimimimimimimimimimimimimimicaled caled.Ipopotttttttaaaaaaaapocket.If.If.Iftttttttttttttttttttttttin a grid. 
 
Input
The input file contains one or more grids.Each grid begins with a line containing m and n,the number of rows and columns in the grid,separated by single space.If m=0 it signals the end the input。otherswise 1<=m==100 and 1<=n==100.Follwing this are m lineas of n characters each(not counting the end-off-line characters).Each character corecter corecter ponds to one plott,and is eigher',presentine able able@ 
 
Output
For each grid、output the number of distinct oil deposits.Two different pockets are parts of the same oil deposit if the y are horizontally、vertically、or diagonally.Anoil deposit witter nopockle 
 
Sample Input
1

3 5
*@@@*****
*@***
*@@@*****
1 8
@@***@@@@@@@@********
5
***@
*@@*@@@@
*@**@
@@@@*@
@@**@
0
 
Sample Output
0 1 2
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>

using namespace std;

#define N 110

char maps[N][N];
int m, n;

void DFS(int o, int p);
int dir[8][2] = { {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

int main()
{
    int i, j, cou;

    while(cin >> m >> n, m+n)
    {
        cou = 0;

        for(i = 0; i < m; i++)
            cin >> maps[i];

        for(i = 0; i < m; i++)
            for(j = 0; j < n; j++)
            {
                if(maps[i][j] == '@')
                {
                    cou++;
                    DFS(i, j);
                }
            }

        cout << cou << endl;
    }

    return 0;
}

void DFS(int o, int p)
{
    int i, q, w;

    maps[o][p] = '*';

    for(i = 0; i < 8; i++)
    {
        q = o + dir[i][0];
        w = p + dir[i][1];

        if(q >= 0 && q < m && w >= 0 && w < n && maps[q][w] == '@')
            DFS(q, w);
    }
}