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

Input

Output

Sample Input

Sample Output