程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1253 勝利大逃亡

HDU 1253 勝利大逃亡

編輯：C++入門知識

HDU 1253 勝利大逃亡

解析：

這道題目非常容易TLE，所以我們需要三維BFS+剪枝。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
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

typedef struct node{
    int x,y,z;
    int cost;
}NODE;

bool flag[55][55][55];  //標記是否訪問過
int p[55][55][55];      //記錄地圖
//六個方向
int tx[]={0,0,0,0,1,-1};
int ty[]={0,1,0,-1,0,0};
int tz[]={1,0,-1,0,0,0};
int A,B,C,T;

bool check(int x,int y,int z){
    if(x<0||x>=A||y<0||y>=B||z<0||z>=C||flag[x][y][z]||p[x][y][z])
        return false;
    return true;
}

int main(){
    int K;
    scanf(%d, &K);
    while(K--){
        queue que;
        scanf(%d%d%d%d, &A,&B,&C,&T);
        memset(flag, false, sizeof(flag));
        int i,j,k;
        for(i=0; iT)  break;
            if(now.x==A-1&&now.y==B-1&&now.z==C-1){
                ans = now.cost;
                break;
            }
            NODE tmp;
            for(i=0; i<6&&flag; ++i){
                tmp.x = now.x+tx[i];
                tmp.y = now.y+ty[i];
                tmp.z = now.z+tz[i];
                tmp.cost = now.cost+1;
                if(check(tmp.x,tmp.y,tmp.z)){
                    flag[tmp.x][tmp.y][tmp.z] = true;
                    //剪枝，當該點以最快速度都不能在規定時間到達時，去掉
                    if(tmp.cost+abs(tmp.x-A+1)+abs(tmp.y-B+1)+abs(tmp.z-C+1)>T)
                        continue;
                    que.push(tmp);
                }
            }
        }
        printf(%d
, ans);
    }
    return 0;
}