Saturday, August 30, 2014

uva : 572 - Oil Deposits


#include<cstdio>
#include<queue>
using namespace std;
int main()
{
    //freopen("input.txt","r",stdin);
    int row,col;
    while(scanf("%d %d\n",&row,&col)==2&&(row+col)!=0)
    {
        int number[row+1][col+1];
        for(int i=1;i<=row;i++)
        {
            for(int j=1;j<=col;j++)
            {
                char ch=getchar();
                if(ch=='*')number[i][j]=0;
                else if(ch=='@')number[i][j]=1;
            }
            getchar();
        }
        int count=0;
        for(int i=1;i<=row;i++)
        {
            for(int j=1;j<=col;j++)
            {
                if(number[i][j]==1)
                {
                    count++;
                    queue<int>r,c;
                    r.push(i);
                    c.push(j);
                    while(!r.empty())
                    {
                        int x=r.front(),y=c.front();
                        r.pop();c.pop();
                        if(x-1>0&&number[x-1][y]==1)
                        {
                            r.push(x-1);c.push(y);number[x-1][y]=0;
                        }
                        if(y-1>0&&number[x][y-1]==1)
                        {
                            r.push(x);c.push(y-1);number[x][y-1]=0;
                        }
                        if(x+1<=row&&number[x+1][y]==1)
                        {
                            r.push(x+1);c.push(y);number[x+1][y]=0;
                        }
                        if(y+1<=col&&number[x][y+1]==1)
                        {
                            r.push(x);c.push(y+1);number[x][y+1]=0;
                        }
                        if(x-1>0&&y-1>0&&number[x-1][y-1]==1)
                        {
                            r.push(x-1);c.push(y-1);number[x-1][y-1]=0;
                        }
                        if(x-1>0&&y+1<=col&&number[x-1][y+1]==1)
                        {
                            r.push(x-1);c.push(y+1);number[x-1][y+1]=0;
                        }
                        if(x+1<=row&&y-1>0&&number[x+1][y-1]==1)
                        {
                            r.push(x+1);c.push(y-1);number[x+1][y-1]=0;
                        }
                        if(x+1<=row&&y+1<=col&&number[x+1][y+1]==1)
                        {
                            r.push(x+1);c.push(y+1);number[x+1][y+1]=0;
                        }
                    }
                }
            }
        }
        printf("%d\n",count);
    }
    return 0;
}

No comments:

Post a Comment