沼跃鱼早已看穿了一切
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 593 Solved: 229
[Submit][Status][Web Board]
Description
沼跃鱼打开密码门后发现门后是一个像迷宫一样的房间，墙上的指示牌写着：房间内某处有一宝箱，但是宝箱被上锁了，钥匙在这个房间的某个角落。沼泽鱼对宝箱里有什么很感兴趣，但它必须先去拿到钥匙才可以打开宝箱。然而沼跃鱼早已看穿了一切，它看清了这个房间的布局，现在给出房间的布局图，问沼跃鱼拿到钥匙并打开宝箱最少需要走多少步。沼跃鱼每次只能向上、下、左、右中其中一个方向走一步，但若那个位置是墙时则不能往那个位置走（显然，沼跃鱼不能穿墙）。
Input
输入的第一行是一个整数T(0<T<20),代表接下来有T组数据。
每组数据的第一行有两个整数n,m(0<n,m≤10)，n代表房间的宽度，m代表房间的长度。
接下来n行，每行有m个字符，‘S’表示开始时沼跃鱼所处的位置，‘#’代表墙，‘*’代表空地，‘K’代表钥匙，‘B’表示宝箱。钥匙只有一把。
详情参看样例输入。
Output
对于每组数据，输出一行包含一个整数x，x代表沼跃鱼拿到钥匙并打开宝箱所需的最少步数。若沼跃鱼不能够拿到钥匙并打开宝箱（即到达不了钥匙或宝箱所在处）则输出-1。
Sample Input
1
5 6
***#B#
S**#*#
##***#
K#*#*#
***#*#
Sample Output
17
HINT
对于样例数据，房间宽5个单位，长6个单位。
从S出发到K需要的最少步数为8，而从K出发到B所需的最少步数为9.
所以答案为8 + 9 = 17.
请使用scanf("%s", s);或cin>> s;来读取字符串以避免出现漏读多读的情况。
BFS 广度优先搜索
CODE :
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int b[][];
void bfs(int n,int m,int num)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(b[i][j]==num)
{
if(b[i][j+]==)
{
b[i][j+]=num+;
}
if(b[i][j-]==){
b[i][j-]=num+;
}
if(b[i-][j]==){
b[i-][j]=num+;
}
if(b[i+][j]==){
b[i+][j]=num+;
}
}
}
}
}
int main()
{
int N;
cin>>N;
while(N--)
{
char a[][];
int n,m;
cin>>n>>m;
memset(b,-,sizeof(b));
int x0,y0,x1,y1;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
cin>>a[i][j];
if(a[i][j]!='#')
{
b[i][j]=;
}
if(a[i][j]=='S')
{
b[i][j]=;
}
if(a[i][j]=='K')
{
x0=i;
y0=j;
} }
}
int num=;
while(b[x0][y0]==&&num<)
{
bfs(n,m,num);
num++;
/*for(int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
cout<<b[i][j]<<'\t';
}
cout<<endl;
}
cout<<endl;*/
}
if(num>)
{
cout<<"-1"<<endl;
continue;
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(a[i][j]!='#')
{
b[i][j]=;
}
if(a[i][j]=='K')
{
b[i][j]=;
}
if(a[i][j]=='B')
{
x0=i;
y0=j;
}
}
}
/* for(int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
cout<<b[i][j]<<'\t';
}
cout<<endl;
}*/
int num0=;
while(b[x0][y0]==&&num0<)
{
bfs(n,m,num0);
num0++;
///*for(int i=1;i<=n;i++)
//{
// for (int j=1;j<=m;j++)
// {
// cout<<b[i][j]<<'\t';
// }
// cout<<endl;
//}*/
//cout<<endl;
}
if(num0>)
{
cout<<"-1"<<endl;
continue;
}
cout<<num+num0-<<endl;
}
}