UVa problem solution 871 - Counting Cells in a Blob

problem link:

Discuss:this is simple graph problem.you can use bfs to solve.just count how much node visited in a call of bfs function and store it in maximum.you can use getline to take input.and push it to your 2d string and if string is empty just break input.there is no tricky part in this problem

try yourself,before see the code



#include<bits/stdc++.h>
using namespace std;
string str[26];
bool visited[26][26];
 int changex[10]={0,0,1,-1,1,-1,1,-1},n,m;
int changey[10]={1,-1,0,0,1,1,-1,-1};
struct bolb
{
    int a;
    int b;
};
int bfs(int r,int s)
{
    bolb p;
    p.a=r;
    p.b=s;
    queue<bolb>que;
    que.push(p);
    visited[r][s]=true;
    int cnt=1,i,j,x,y;
    while(!que.empty())
    {
        p=que.front();
        que.pop();
        for(i=0;i<8;i++)
        {
            x=p.a+changex[i];
            y=p.b+changey[i];
            for(j=0;j<26;j++)
            {
                if(x>=0&&x<m&&y>=0&&y<n&&!visited[x][y]&&str[x][y]=='1')
                {
                    visited[x][y]=true;
                    bolb nw;
                    nw.a=x;
                    nw.b=y;
                    cnt++;
                    que.push(nw);
                }
            }
        }
    }
  // cout <<cnt<<endl;
    return cnt;
}
int main()
{
   // freopen("input.txt","r",stdin);
   // freopen("output.txt","w",stdout);
    int t;
    cin >>t;
    for(int k=0;k<t;k++)
    {
         string s;
        int i=0,j,flag=0,mx=0;
        memset(visited,false,sizeof visited);
        scanf("\n");
        while(getline(std::cin, s))
        {
            if(s.empty())
                break;
         str[i]=s;
            i++;
            s.clear();
        }
        m=i;
        n=str[0].size();
       // cout <<n<<endl;
      for(i=0;i<m;i++)
        {
            //m=str[i].size();
            for(j=0;j<n;j++)
            {
                if(!visited[i][j]&&str[i][j]=='1')
                {
                    mx=max(mx,bfs(i,j));
                   // cout <<'y'<<' '<<bfs(i,j);
                }
            }
        }
        cout <<mx<<endl;
        for(i=0;i<26;i++)
        {
            //cout <<str[i]<<' ';
        str[i].clear();

        }
        if(k!=t-1)
            cout <<endl;

    }
    return 0;
}