UVa problem solution 572 - Oil Deposits

problem link:

Discuss: this is simple graph. if you know the fundamental algorithm of graph i mean bfs or dfs then it's pretty easy for you. when you found a node with '@' and it is not visited then just sent the index value to bfs function and increment the answer and in bfs function mark every connected node with it visited. your work done.


try yourself before see the code



#include<bits/stdc++.h>
using namespace std;
char str[111][111];
bool visited[111][111];
int m,n;
 int changex[10]={0,0,1,-1,1,-1,1,-1};
    int changey[10]={1,-1,0,0,1,1,-1,-1};
struct position
{
    int a;
    int b;
};
void bfs(int r,int s)
{
    int i,j,q;
    position cor;
    cor.a=r;
    cor.b=s;

    queue<position>que;
    que.push(cor);
    visited[r][s]=true;
    while(!que.empty())
    {
        cor=que.front();
        que.pop();
        for(i=0;i<8;i++)
        {
            int x=cor.a+changex[i];
            int y=cor.b+changey[i];
            for(j=0;j<n;j++)
            {
            if(x>=0&&x<m&&y>=0&&y<n&&!visited[x][y]&&str[x][y]=='@')
            {
                visited[x][y]=true;
                position nw;
                nw.a=x;
                nw.b=y;
                que.push(nw);
            }
            }
        }
    }
}
int main()
{
   // freopen("input.txt","r",stdin);
   // freopen("output.txt","w",stdout);
    while(cin >>m&&m)
    {
       int i,j,cnt=0,flag=0;
        cin >>n;
        memset(visited,false,sizeof visited);
        for(i=0;i<m;i++)
        {
            scanf("\n");
            cin >>str[i];
        }
        for(i=0;i<m;i++)
        {
            for(j=0;j<n;j++)
            {
                if(visited[i][j]==false&&str[i][j]=='@')
                {
                    cnt++;
                    bfs(i,j);
                }
            }
        }
        cout <<cnt<<endl;
    }
    return 0;
}