BFS-小学期考核

红太狼 2022-09-25 14:20 120阅读 0赞

**题目大意：给你一个 n\*m 的地图，地图元素（ ‘S’ 代表你的起始位置，‘E’为终点位置，‘X’为力量之源，‘\*’为墙，‘.’为路），给你 T（时间），你必须在T时间内从起始位置找到力量之源，在从力量之源到终点--这里的时间不计！每移动一格时间为1，如果能到达终止位置就输出最小花费时间，负责输出 -1  **

**题目思路：这题为简单的BFS模板题，可以用两边BFS，第一遍从起始位置找到力量之源，若不能找到活时间超过T就直接输出-1并返回，若能就进行第二遍BFS找到终点，若能就输出最小的时间，不能就输出-1！**

**代码：**

#include<iostream>
    #include<stdio.h>
    #include<queue>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n,m,ans,sx,sy,flag;
    char Map[505][505];
    int vis[505][505];
    int fx[4][2]={1,0,-1,0,0,1,0,-1};
    void bfs1(int x,int y){
        ans=0;
        queue<int>q,q1;
        q.push(x);
        q.push(y);
        flag=0;
        vis[x][y]=1;
        A:printf("");
        while(!q.empty()){
            x=q.front(),q.pop();
            y=q.front(),q.pop();
            for(int i=0;i<4;i++){
                int h=x+fx[i][0],l=y+fx[i][1];
                if(h>=0&&h<n&&l>=0&&l<m&&!vis[h][l]&&Map[h][l]!='*'){
                    if(Map[h][l]!='X'){q1.push(h),q1.push(l);vis[h][l]=1;}
                    else {
                            sx=h,sy=l;
                            ans++;
                            flag=1;
                        return ;
                    }
                }
            }
    
        }if(!q1.empty()){
                ans++;
                swap(q,q1);
                while(!q1.empty())q1.pop();
                goto A;
            }
    }
    
    void bfs2(int x,int y){
        queue<int>q,q1;
        q.push(x);
        q.push(y);
        vis[x][y]=1;
        flag=0;
        B:printf("");
        while(!q.empty()){
            x=q.front(),q.pop();
            y=q.front(),q.pop();
            for(int i=0;i<4;i++){
                int h=x+fx[i][0],l=y+fx[i][1];
                if(h>=0&&h<n&&l>=0&&l<m&&!vis[h][l]&&Map[h][l]!='*'){
                    if(Map[h][l]!='E'){q1.push(h),q1.push(l);vis[h][l]=1;}
                    else {
                            ans++;
                            flag=1;
                            return ;
                    }
                }
            }
    
        }if(!q1.empty()){
                ans++;
                swap(q,q1);
                while(!q1.empty())q1.pop();
                goto B;
            }
    }
    
    
    int main()
    {
        int t;
        while(cin>>n>>m>>t){
            for(int i=0;i<n;i++){
                scanf("%s",Map[i]);
                for(int j=0;j<m;j++)
                    if(Map[i][j]=='S')sx=i,sy=j;
            }
            memset(vis,0,sizeof(vis));
            bfs1(sx,sy);
    
            memset(vis,0,sizeof(vis));
            if(flag)
            {
                 if(ans>t){
                        cout<<-1<<endl;
                        continue;
                 }
                 else
                 bfs2(sx,sy);
            }
    
            if(!flag)cout<<"-1"<<endl;
            else{
    
                 cout<<ans<<endl;
            }
        }
        return 0;
    }