1238 - Power Puff Girls

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1238

Solution :

#include<bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

int cell[22][22];
int visited[22][22];
int dis[22][22];

int fx[]= {1,-1,0,0};
int fy[]= {0,0,1,-1};

int r,c;

int bfs(pii s,pii d)
{
    memset(visited,0,sizeof(visited));

    memset(dis,0,sizeof(dis));

    visited[s.first][s.second]=1;
    dis[s.first][s.second]=0;

    queue<pii>q;
    pii u,a;
    int x,y,cnt=0;
    q.push(s);

    while(!q.empty())
    {
        u=q.front();
        q.pop();

        for(int i=0; i<4; i++)
        {
            x=fx[i]+u.first;
            y=fy[i]+u.second;

            if(x>=0 and x<r and y>=0 and y<c and cell[x][y]!=2 and visited[x][y]==0)
            {
                visited[x][y]=1;
                dis[x][y]=dis[u.first][u.second]+1;
                cnt++;
                a.first=x;
                a.second=y;
                q.push(a);
            }
        }

    }
    return dis[d.first][d.second];

}

int main()
{
    int t,ans;
    char ch;
    pii s,s1,s2,d;
    scanf("%d",&t);


    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d%d",&r,&c);
        getchar();
        memset(cell,-1,sizeof(cell));
        for(int i=0; i<r; i++)
        {
            for(int j=0; j<c; j++)
            {
                scanf("%c",&ch);
                if(ch=='.') cell[i][j]=1;
                else if(ch=='#') cell[i][j]=2;
                else if(ch=='c')
                {
                    cell[i][j]=3;
                    s1.first=i;
                    s1.second=j;
                }
                else if(ch=='a')
                {
                    cell[i][j]=4;
                    s2.first=i;
                    s2.second=j;
                }
                else if(ch=='b')
                {

                    cell[i][j]=5;
                    s.first=i;
                    s.second=j;
                }
                else if(ch=='h')
                {
                    cell[i][j]=6;
                    d.first=i;
                    d.second=j;
                }
                else
                {
                    cell[i][j]=2;
                }

            }
            getchar();
        }

        ans=bfs(s,d);
        ans=max(ans,bfs(s1,d));
        ans=max(ans,bfs(s2,d));

        printf("Case %d: %d\n",ca,ans);
    }

}