LightOJ 1238-Power Puff Girls

 

The city of Townsville! This nice city is the home for the power puff girls - Blossom, Bubbles and Buttercup. To introduce their personality we can sing a song:

Blossom, commander and the leader;

Bubbles, she is the joy and the laughter;

Buttercup, she is the toughest fighter.

These super girls defend Townsville from monsters and super villains using their super powers, intelligence. They live in a home in Townsville with the professor who is like their father.

The girls are young now and they don't like to fight the monsters anymore. So, if they are outside their home, they are found shopping. And when they get back to home, they simply watch the TV serials. It's such a horrible fact that the super intelligent girls are wasting their time watching serials that consist of the rivalries between Wives and their Mother in Laws. And when they use computers they are usually found using the facenote (a dangerous¹ social networking site).

So, such wonderful girls just became lazy and useless. Often they are seen fighting each other, the comments that can be heard, are like, 'Tulsi is the best.', 'Gopi is better than Rashee.' The professor is quite upset with the girls, and he can't even watch any science show or sports because of these irritating serials.

So, the professor made a plan and asked the girls to go for shopping such that he can watch an important science show in the TV. The girls became very excited and they went out for shopping. But soon they realize that one of their favorite serials will start soon, and they need to get back home for that serial.

To be more specific let's consider the city as a 2D grid. In the grid there are some symbols, the meaning of them are:

1.      '.'         means an empty place

2.      'a'        denotes the position of Blossom

3.      'b'       denotes the position of Bubbles

4.      'c'        denotes the position of Buttercup

5.      'm'      denotes that there is a monster

6.      'h'       denotes their home

7.      '#'       denotes a wall and the girls can't pass through it

The three girls move simultaneously. And in each minute, from their current cells, they can move to any four adjacent cells (North, East, West, South) if the destination cell is neither a wall nor the cell contains a monster. Because they want to get home as soon as possible, they want to avoid the monsters. You can assume that they can move to a common cell if necessary.

Now you are given the information of the city and their positions. You have to find the minimum time when they all are in home.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing two integers: m and n (4 ≤ m, n ≤ 20), m denotes the number of rows and n denotes the number of columns of the modeled grid. Each of the next m lines contains n characters representing the city.

You can assume that 'a', 'b', 'c', 'h' will occur exactly once in the grid. The outer boundaries will always be marked by '#'.

Output

For each case, print the case number and the minimum time needed when they all are in their home. You can assume that a solution will always exist.

Sample Input	Output for Sample Input
2 6 8 ######## #...c..# #......# #.a.h.b# #......# ######## 5 9 ######### #mmm...c# #ma.h#### #m....b.# #########	Case 1: 2 Case 2: 4

Analysis:

As we have to find out minimum time, so we can apply bfs algorithm here. As one super girl can visit the path witch was visited by other super girl, everytime we have to set our memory of array, visit and array, dis to zero.  

Solution: 

#include<bits/stdc++.h>
using namespace std;
int xx[]= {1,-1,0,0};
int yy[]= {0,0,1,-1};
char s[50][50];
int r, c;
bool visit[50][50];
int dis[50][50];
queue <int> q1;
queue <int> q2;

int bfs(int ux, int uy)
{
    int ux1, uy1, vx1, vy1;
    q1.push(ux);
    q2.push(uy);
    visit[ux][uy]=1;
    while(!q1.empty() && !q2.empty())
    {
        ux1=q1.front();
        uy1=q2.front();
        q1.pop();
        q2.pop();
        if(s[ux1][uy1]=='h')
        {
            return dis[ux1][uy1]; //destination found
        }
        for(int i=0; i<4; i++)
        {
            int vx=ux1+xx[i];
            int vy=uy1+yy[i];
            if(vx<0 || vy<0 || vx>=r || vy>=c)
                continue;

            if(visit[vx][vy]==1 || s[vx][vy]=='#' || s[vx][vy]=='m')
                continue;

            visit[vx][vy]=1;
            q1.push(vx);
            q2.push(vy);
            dis[vx][vy]=dis[ux1][uy1]+1;
        }
    }
}


int main()
{

    int i, j, d1, d2, d3, ax, ay, bx, by, cx, cy, sum, t_case, kl=0;
    scanf("%d", &t_case);
    while(t_case--)
    {
        scanf("%d%d", &r, &c);
        sum=0;
        memset(s, 0, sizeof(s));
        for(i=0; i<r; i++)
        {
            scanf("%s",s[i]);
            for(j=0; j<c; j++)
            {
                if(s[i][j]=='a')
                {
                    ax=i;
                    ay=j;
                }
                if(s[i][j]=='b')
                {
                    bx=i;
                    by=j;
                }
                if(s[i][j]=='c')
                {
                    cx=i;
                    cy=j;
                }

            }
        }
        while(!q1.empty() && !q2.empty())
        {
            q1.pop();
            q2.pop();
        }
        memset(dis, 0, sizeof(dis));
        memset(visit, 0, sizeof(visit));
        d1=bfs(ax, ay);
        if(d1>sum)
            sum=d1;
        while(!q1.empty() && !q2.empty())
        {
            q1.pop();
            q2.pop();
        }
        memset(dis, 0, sizeof(dis));
        memset(visit, 0, sizeof(visit));
        d2=bfs(bx, by);
        if(d2>sum)
            sum=d2;
        while(!q1.empty() && !q2.empty())
        {
            q1.pop();
            q2.pop();
        }
        memset(dis, 0, sizeof(dis));
        memset(visit, 0, sizeof(visit));
        d3=bfs(cx, cy);
        if(d3>sum)
            sum=d3;
        printf("Case %d: %d\n", ++kl, sum);
    }

    return 0;
}