POJ Project Summer

04E:Project Summer​​​​​​​

Total time limit : 

1000ms

Memory limit : 

65536kB

describe

Small I And small B Recently, I became addicted to a product called 《Project Summer》 The game of , Small I Play the innocent who need to escape in this game （Innocent), Small B Play this game to catch the innocent , The traitor who prevented his escape （Betrayer）.

The map of this game is a N That's ok M Column The rectangular , Each grid point represents a position . '#' Represent obstacles in the map ,'.' Represents the open space in the map , Besides , There are also... In the map Only the Betrayer To use the portal , In small letters 'a' - 'z' Mark , They appear in pairs on the map .

   Roles can cost 1 The unit time goes from one grid to the next 4 Another cell in a clearing （ Don't walk out of the map boundary or onto obstacles ）.

Besides , When small B When the Betrayer comes to a portal , He can spend 1 The unit time is transferred from the current grid to another portal with the same letter as the current grid （ He can also choose not to transmit , It doesn't take any time , Stay where you are ）. Transfer yes two-way Of . such as , Now small B Go to the mark as 'a' On the grid , Then he can choose to spend one unit of time to transfer to another marked 'a' On the grid , You can also choose not to transmit , Then he just stays where he is .

Now? , Small I Be small B The trap of , Cannot move . Give the small on the map B And small I In the grid （ They are all standing in the open space ）, Seek small B At least how much time will it take to get there I Catch him in the grid . If small I Unable to grasp the small B, Output -1

Input

One number in the first line T, Represents the number of data groups .
Next, describe T Group data , Each set of data starts with two positive integers N, M Indicates that the map is N That's ok M Column rectangle .
Next N That's ok , Each row M Characters , Represents a map . On the map , use '.' Representing vacant land ,'#' It means an obstacle ,'a'-'z' Indicates the portal ,'B' It means small B Initial position ,'I' It means small I Initial position .
For each set of data , Make sure that the same portal appears exactly twice on the map .
T,N,M <= 100

Output

T That's ok , The first i Line output 'Case #i: t', It means the first one i The answer to the set of data is t. Small B Minimum need t Unit time to go small I In the grid . If small I Unable to grasp the small B, Output -1

The sample input

3
5 5
Bx#..
#a.#.
.....
##..#
.x.aI
5 5
BIa.a
x#.x.
.#.##
.....
#####
2 2
B#
#I

Sample output

Case #1: 4
Case #2: 1
Case #3: -1

Tips

For the first set of data , Suppose the row is labeled from top to bottom 1 To 5, Columns are labeled from left to right 1 To 5, Small B The beginning is (1, 1). Small B The best route is ：

(1, 1) -> (1, 2) -> (2, 2) -> (5, 4) -> (5, 5). That is, go to the place marked with x The portal is ignored when the portal , Go to marked as a When using the portal of .

For the second set of data , Small B Direct costs 1 If you go one square to the right in unit time, you can catch the small I, Therefore, the output 1.

For the third set of data , Small B Can't walk to the small I Where you are , Therefore, the output -1.

answer

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int T, N, M;
int ii, jj;
int directs[4][2]{
   {1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char a[100][100];
int visited[100][100];

struct Data
{
    int i, j, t;
    Data(int _i, int _j, int _t) : i(_i), j(_j), t(_t) {}
};

Data gogogo(const Data &d)
{
    char c = a[d.i][d.j];
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (a[i][j] == c && !(d.i == i && d.j == j))
            {
                return Data(i, j, d.t + 1);
            }
        }
    }
    return d;
}

int main()
{
    cin >> T;
    for (int t = 1; t <= T; ++t)
    {
        cin >> N >> M;
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < M; ++j)
            {
                cin >> a[i][j];
                if (a[i][j] == 'B')
                {
                    ii = i;
                    jj = j;
                }
            }
        }
        queue<Data> q;
        memset(visited, -1, sizeof(visited));
        q.push(Data(ii, jj, 0));
        visited[ii][jj] = 0;
        bool flag = 0;
        while (!q.empty())
        {
            Data cur = q.front();
            if (a[cur.i][cur.j] == 'I')
            {
                flag = 1;
                break;
            }
            q.pop();
            int ni, nj, nt;
            for (int d = 0; d < 4; ++d)
            {
                ni = cur.i + directs[d][0];
                nj = cur.j + directs[d][1];
                nt = cur.t + 1;
                if (ni >= 0 && ni < N && nj < M && nj >= 0 && a[ni][nj] != '#' && (visited[ni][nj] == -1 || nt < visited[ni][nj]))
                {
                    visited[ni][nj] = nt;
                    q.push(Data(ni, nj, nt));
                }
            }
            //  gas ！isalpha Function in OJ Will be judged wrong 
            if (a[cur.i][cur.j] <= 'z' && a[cur.i][cur.j] >= 'a')
            {
                Data nd = gogogo(cur);
                if (visited[nd.i][nd.j] == -1 || nd.t < visited[nd.i][nd.j])
                {
                    visited[nd.i][nd.j] = nd.t;
                    q.push(nd);
                }
            }
        }
        cout << "Case #" << t << ": " << ((flag) ? q.front().t : -1) << endl;
    }
}