Problem

admin管理员组

文章数量:1794759

Problem

分析：  这个题其实不难，就是在常规的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;elsecout<<"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

4 4S.*...X.E.......4 4S.*..*X..***E...

Sample Output

6DBZ Cheat Us

本文标签： problem