HDU 2102 A计划

妖狐艹你老母 2022-03-30 04:22 167阅读 0赞

**题目链接**：[http://acm.hdu.edu.cn/showproblem.php?pid=2102][http_acm.hdu.edu.cn_showproblem.php_pid_2102]

**题解**：

BFS+剪枝

1.题意不是非常清楚，不太清楚S是否一定是（0,0,0），所以这里做了一次查找。

2.对于传送门的问题，假设两个传送门相对，那么骑士一定会被传送门华丽丽地玩死了；

3.剪枝。这里的剪枝因为两层之间传送不消耗时间，所以我们仅仅须要求：T(当前位置)+DIS(公主位置-当前位置)<=T才干继续进行，否则就要被剪掉

**代码**：

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <stack>
    #include <set>
    #include <map>
    using namespace std;
    #define Lowbit(x) ((x)&(-(x)))
    #define ll long long
    #define mp make_pair
    #define ff first
    #define ss second
    #define pb push_back
    #define mod 10000007
    //#define LOCAL
    #define MAXN 100010
    #define INF 1e9
    #define Max 100010
    
    int ty[]={0,1,0,-1};
    int tz[]={1,0,-1,0};
    
    char str[2][15][15];
    bool visit[2][15][15];
    int N,M,T;
    
    typedef struct node{
        int x,y,z;
        int cost;
    }NODE;
    
    bool check(int &x,int &y,int &z){
        if(y<0||y>=N||z<0||z>=M||str[x][y][z]=='*'||visit[x][y][z])
            return false;
        visit[x][y][z] = true;
        if(str[x][y][z]=='#')
            if(str[x^1][y][z]=='*'||str[x^1][y][z]=='#')
                return false;
            else
                x^=1;   //传送门进行层传递
        visit[x][y][z] = true;
    
        return true;
    }
    
    int main(){
        int C;
        scanf("%d",&C);
        while(C--){
            scanf("%d%d%d", &N, &M, &T);
            int i,j,k;
            for(i=0; i<2; ++i){
                for(j=0; j<N; ++j)
                    scanf("%s", str[i][j]);
            }
    
            NODE now;
            NODE target;
            //查找'S'\'P'点的位置
            for(i=0; i<2; ++i){
                for(j=0; j<N; ++j){
                    for(k=0; k<M; ++k){
                        if(str[i][j][k]=='S'){
                            now.x = i;
                            now.y = j;
                            now.z = k;
                        }
                        if(str[i][j][k]=='P'){
                            target.x = i;
                            target.y = j;
                            target.z = k;
                        }
                    }
                }
            }
    
            //BFS
            memset(visit, false, sizeof(visit));
            now.cost = 0;
            queue<NODE> que;
            que.push(now);
            visit[now.x][now.y][now.z] = true;
            bool flag = false;
            while(que.size()){
                now = que.front();
                que.pop();
    
                if(now.cost>T)  break;
                if(now.x==target.x&&now.y==target.y&&now.z==target.z){
                    flag = true;
                    break;
                }
                NODE next;
                for(i=0; i<4; ++i){
                    next.x = now.x;
                    next.y = now.y+ty[i];
                    next.z = now.z+tz[i];
                    next.cost = now.cost+1;
                    if(check(next.x,next.y,next.z)){
                        //剪枝
                        if(next.cost+
                           abs(target.y-next.y)+abs(target.z-next.z)>T)
                            continue;
                        que.push(next);
                    }
                }
            }
            printf("%s\n", flag?"YES":"NO");
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_2102]: http://acm.hdu.edu.cn/showproblem.php?