首页 > 代码库 > Problem -B DBZ的钥匙
Problem -B DBZ的钥匙
分析： 这个题其实不难，就是在常规的BFS上多了一个BFS，即两个BFS而已！使用一个for循环即可求出来！以前做过很多BFS的题，这道题其实和那些都差不多，就是在数据上需要自己做点功夫，将字符串的地图改变为整数型的地图即可！
思路：1.首先输入地图，然后设立两个int型的起点和终点数组用来存起点和终点；
同时在字符串的地图中，如果此处可走，在对应的整数型的地图中标记为1，不能走的地方标记为0；
2.由于题目要求：如果找不到钥匙或者或者找到了钥匙但是不能把钥匙给DBZ的话，同样视为不成功，即输出“DBZ cheat us”；
3.基于第二点，可以设立一个标记，在所写的for循环中，只要有一次ans[i]==0，那么表明失败！
4.这个就看自己的想法了，可以使用数组写队列，也可以使用C++标准模板库写队列，当然我觉得后者更简单咯！
5.剩下的就是细节方面了，这个多想想应该就没问题了！
代码如下：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
char Map[520][520];
int map[520][520];
int n,m,sx[2],sy[2],dx[2],dy[2],ans[2];
int xx[4]= {1,0,-1,0};
int yy[4]= {0,1,0,-1};
bool vis[520][520];
struct node
{
int x,y,ti;
};
bool bfs()
{
for(int ss=0; ss<2; ss++)
{
memset(vis,false,sizeof(vis));
vis[sx[ss]][sy[ss]]=true;
queue<node>Q;
node now;
now.x=sx[ss];
now.y=sy[ss];
now.ti=ans[ss];
Q.push(now);
while(!Q.empty())
{
node te=Q.front();
Q.pop();
if(te.x==dx[ss]&&te.y==dy[ss])
{
ans[ss]=te.ti;
break;
//cout<<"eee--->"<<ans[ss]<<endl;
}
for(int i=0; i<4; i++)
{
int X=xx[i]+te.x;
int Y=yy[i]+te.y;
if(map[X][Y]&&!vis[X][Y]&&X>=0&&X<n&&Y>=0&&Y<m)
{
vis[X][Y]=true;
node num;
num.x=X;
num.y=Y;
num.ti=te.ti+1;
Q.push(num);
}
}
}
if(!ans[ss])
return false;
}
return true;
}
int main()
{
while(cin>>n>>m)
{
ans[0]=ans[1]=0;
getchar();
memset(map,1,sizeof(map));
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
cin>>Map[i][j];
if(Map[i][j]=='.')
map[i][j]=1;
if(Map[i][j]=='*')
map[i][j]=0;
if(Map[i][j]=='S')
{
sx[0]=i;
sy[0]=j;
}
if(Map[i][j]=='X')
{
dx[0]=i;
dy[0]=j;
sx[1]=i;
sy[1]=j;
}
if(Map[i][j]=='E')
{
dx[1]=i;
dy[1]=j;
}
}
getchar();
}
if(bfs())
cout<<ans[0]+ans[1]<<endl;
else
cout<<"DBZ Cheat Us"<<endl;
}
return 0;
}
Description
古有富可敌国万三千，今有富可敌球DBZ。话说DBZ有一辆超级林肯加长，它的车头在都江堰，而车尾却在川大，经过数月之久她终于到达了咱们成都东软学院，引来无数人围观。可粗心的DBZ却不知道将车的钥匙丢在了车的何处，于是富可敌球的他悬赏50000000000万（当然这对于他来说都是小Case ^_^），公开悬赏找钥匙。作为咱东软学院平凡的你，肯定不想错失这一次难得变为高富帅、白富美的机会。若你想拿到奖金，那么你就需要用最快的方式找到钥匙，并且拿给DBZ。
Input
测试数据包含多组。
每组测试数据第一行包含2个数 n ( 1 < = n < = 500 ) , m ( 1 < = m < = n ) ，代表车的长和宽。
接下来包含n行，每行m个元素（ 其中 ‘.‘ 代表可以通过的路径， ‘X‘ 代表钥匙所在地， ‘*‘代表障碍物， ‘E‘ 代表DBZ锁在地， ‘S‘代表你所在的位置。 每次你只能上下左右进行移动。
Output
输出仅包含一行，即把钥匙交给DBZ的最小时间，如果无法成功找到钥匙或找到钥匙无法成功交给DBZ，则输出“DBZ Cheat Us"(没有引号)。
Sample Input
Sample Output
Problem -B DBZ的钥匙