HDU 2102 A计划【三维BFS】-白红宇

HDU 2102 A计划【三维BFS】

阅读量：5818 次

发布时间：2019-06-18

本文共 3260 字，大约阅读时间需要 10 分钟。

A计划Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 28414    Accepted Submission(s): 7129Problem Description可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。 Input输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小N*M（1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况，后N*M表示迷宫第二层的布置情况。 Output如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。 Sample Input15 5 14S*#*..#........****....#...*.P#.*..***.....*.*.#.. Sample OutputYES

【分析】：遇到上下两层都是# 的，就把上下两层的这个位置都弄成墙就行。还有遇到一层是#一层是墙的，也直接把俩都弄城墙就行，省的要判断他撞死。首先开一个3维的空间，为方便，坐标设置为z、x、y（z用0或1表示，因为后面用起来会很方便）。

于是就是找坑点，#传送后不能是#或*，尤其注意#传送后可能直接是P，再就是#是不浪费时间的，这里经过处理后也不算是坑。还有就是对时间的把握。

【代码】：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define debug() puts("+++++++++++++++++++++++++++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<(n); i++)#define in freopen("in.in","r",stdin)#define out freopen("out.out","w",stdout)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                      
                        P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxn = 25;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = {0,0,1,-1,1,-1,1,-1};const int d[6][3]={ {0,0,1},{0,0,-1},{-1,0,0},{1,0,0},{0,1,0},{0,-1,0} };int dir[4][2]={0,1,0,-1,1,0,-1,0};const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int n,m,t,T;int ex,ey,ez,flag;char a[2][35][35];int v[2][35][35];struct node{ int x,y,z,s;}st,ed;bool check(int x,int y,int z){ if(x<0||x>=n||y<0||y>=m) return 0; else if(v[z][x][y]==1) return 0; else if(a[z][x][y]=='*') return 0; else if(a[z][x][y]=='#' && a[1^z][x][y]=='*') return 0; else if(a[z][x][y]=='#' && a[1^z][x][y]=='#') return 0; else return 1;}void bfs(){ queue
                       
                        q; st.x = st.y = st.z = st.s = 0; q.push(st); v[0][0][0]=1; while(!q.empty()) { st = q.front(); q.pop(); if(st.s > t) return ; if(a[st.z][st.x][st.y] == 'P') //z、x、y的先后顺序很容易写错，而且写错了显示的是MLE，有点奇怪 { printf("YES\n"); flag = 1; return ; } for(int i=0; i<4; i++) { ed.x = st.x + dir[i][0]; ed.y = st.y + dir[i][1]; ed.z = st.z; if(check(ed.x, ed.y, ed.z)) { if(a[ed.z][ed.x][ed.y]=='#') //遇到#穿越不花时间只改变 ed.z = !ed.z; ed.s = st.s + 1; //虽然上下楼不用时间，但是你走到#需要一步的时间 v[ed.z][ed.x][ed.y] = 1; q.push(ed); } } }}int main(){ scanf("%d",&T); while(T--) { flag=0; ms(v,0); ms(a,'*'); scanf("%d%d%d",&n,&m,&t); for(int i=0;i

转载于:https://www.cnblogs.com/Roni-i/p/9301652.html

你可能感兴趣的文章