沼跃鱼打开密码门后发现门后是一个像迷宫一样的房间，墙上的指示牌写着：房间内某处有一宝箱，但是宝箱被上锁了，钥匙在这个房间的某个角落。沼泽鱼对宝箱里有什么很感兴趣，但它必须先去拿到钥匙才可以打开宝箱。然而沼跃鱼早已看穿了一切，它看清了这个房间的布局，现在给出房间的布局图，问沼跃鱼拿到钥匙并打开宝箱最少需要走多少步。沼跃鱼每次只能向上、下、左、右中其中一个方向走一步，但若那个位置是墙时则不能往那个位置走（显然，沼跃鱼不能穿墙）。

输入的第一行是一个整数T(0<T<20),代表接下来有T组数据。

 每组数据的第一行有两个整数n,m(0<n,m≤10)，n代表房间的宽度，m代表房间的长度。

接下来n行，每行有m个字符，‘S’表示开始时沼跃鱼所处的位置，‘#’代表墙，‘*’代表空地，‘K’代表钥匙，‘B’表示宝箱。钥匙只有一把。

详情参看样例输入。

 对于每组数据，输出一行包含一个整数x，x代表沼跃鱼拿到钥匙并打开宝箱所需的最少步数。若沼跃鱼不能够拿到钥匙并打开宝箱（即到达不了钥匙或宝箱所在处）则输出-1。

对于样例数据，房间宽5个单位，长6个单位。

从S出发到K需要的最少步数为8，而从K出发到B所需的最少步数为9.

所以答案为8 + 9 = 17.

请使用scanf("%s", s);或cin>> s;来读取字符串以避免出现漏读多读的情况。

“美图杯”第二届新生赛，Author：13凌嘉威

 1 #include <cstdio> 2 #include <cstring> 3 #include <deque> 4 #define INF 2147483647 5   6 const int MAX = 32; 7 const int cx[] = { -1, 0, 1, 0 }; 8 const int cy[] = { 0, 1, 0, -1 }; 9 char arr[MAX][MAX];10 int vis[MAX][MAX];11  12 struct POINT{13     int x, y;14 };15  16 int BFS(POINT a, POINT b)17 {18     POINT c, tmp;19     memset(vis, 0, sizeof(vis));20 21     std::deque<POINT> qu;    // 建立队列22     qu.clear();23     qu.push_back(a);24 25     while (!qu.empty())26     {27         c = qu.front();        //    取出队头元素28         qu.pop_front();        //    队头元素出队29         for (int i = 0; i < 4; i++)        //    4个方向遍历30         {31             if ((arr[c.x + cx[i]][c.y + cy[i]] != ‘#‘) && !vis[c.x + cx[i]][c.y + cy[i]])32             {33                 vis[c.x + cx[i]][c.y + cy[i]] = vis[c.x][c.y] + 1;34                 tmp.x = c.x + cx[i]; tmp.y = c.y + cy[i];35                 qu.push_back(tmp);36             }37         }38     }39     if (vis[b.x][b.y])        //    若可以到达，则返回到该点的距离40         return vis[b.x][b.y];41     return -INF;            //    否则返回一个不存在的值42 }43  44 int main()45 {46 #ifdef CDZSC_OFFLINE47     freopen("in.txt", "r", stdin);48     freopen("out.txt", "w", stdout);49 #endif50     int t, n, m, t1, t2;51     POINT a, b, c;52     scanf("%d", &t);53     while (t--)54     {55         scanf("%d%d", &n, &m);56         memset(arr, ‘#‘, sizeof(arr));57         for (int i = 1; i <= n; i++)58         {59             scanf("%s", arr[i] + 1);60             arr[i][m + 1] = ‘#‘;61         }62         for (int i = 1; i <= n; i++)        // 寻找起点，钥匙位置，宝箱位置63         {64             for (int j = 1; j <= m; j++)65             {66                 if (arr[i][j] == ‘S‘)67                 {68                     a.x = i; a.y = j;69                 }70                 else if (arr[i][j] == ‘K‘)71                 {72                     b.x = i; b.y = j;73                 }74                 else if (arr[i][j] == ‘B‘)75                 {76                     c.x = i; c.y = j;77                 }78             }79         }80         if (((t1 = BFS(a, b)) != -INF) && ((t2 = BFS(b, c)) != -INF))81         {82             printf("%d\n", t1 + t2);83         }84         else85         {86             printf("-1\n");87         }88     }89     return 0;90 }