礼物（BFS）-白红宇

礼物（BFS）

阅读量：7199 次

发布时间：2019-06-29

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

礼物

时间限制: 1 Sec 内存限制: 64 MB

提交: 39 解决: 4

[][][]

题目描述

　　给出一个n行m列的点阵，“．”表示可通行格子，“#”表示不可通行格子，“K”表示国王的初始位置，“Q”表示王后的位置，“G”表示该格子有一个礼物。注意：国王、王后、礼物所在的格子可以认为是可通行格子。国王从开始位置出发，国王从当前格子可以走到上、下、左、右四个相邻格子，当然前提是可通行格子。国王从当前格子走到相邻格子的时间是变化的，这取决于国王手头上收集到的礼物的数量，假如当前国王手头上有y个礼物，那么他从当前格子移动到相邻格子的所用时间是y+l秒。一旦国王进入某个有礼物的格子，他可以选择取该格子的礼物，也可以选择不取该格子的礼物。取礼物这个动作可以认为是瞬间完成的，不需要时间。国王想收集到尽量多的礼物送给王后，但是他到达王后所在的格子不能超过T秒，王后不想等太长时间。注意：国王在收集礼物的途中可能多次走到相同的格子。

输入

　第1行：三个整数n、m、T。 1≤n，m≤50，1≤T≤109。

　接下来是n行m列的点阵，‘G’的数量不超过16。只有一个国王，一个王后。

输出

一个整数，国王在规定时间内，最多可以收集到多少个礼物送给王后？

样例输入

5 7 50#....G####G####K...Q####.####G..GG#

样例输出

4 【分析】威哥写的，表示并不懂，立个flag，日后再学，已经看晕了。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include
                    
                     #define mod 1000000007#define inf 0x3f3f3f3f#define pi acos(-1.0)using namespace std;typedef long long ll;const int N = (1<<16)+5;const int INF = 0x3f3f3f3f;char s[52][52];int n,m,T;struct Node { int x,y; Node(int a=0,int b=0) { x=a; y=b; }} st,ed;vector
                     
                      g;int d[18][18],dis[51][51],f[N][16];int dx[4]= { 0,0,-1,1};int dy[4]= {-1,1,0,0};void bfs(int pos) { queue
                      
                       q; memset(dis,INF,sizeof(dis)); dis[g[pos].x][g[pos].y]=0; q.push(g[pos]); while(!q.empty()) { Node u=q.front(); q.pop(); for(int i=0; i<4; ++i) { int x=u.x+dx[i],y=u.y+dy[i]; if(x<1||x>n||y<1||y>m||s[x][y]=='#')continue; if(dis[x][y]==INF) { dis[x][y]=dis[u.x][u.y]+1; q.push(Node(x,y)); } } } for(int i=0; i
                       
                        =INF)continue; for(int k=0; k
                        
                         =INF)continue; f[i|(1<
                         
                          <

View Code

转载于:https://www.cnblogs.com/jianrenfang/p/5726244.html

你可能感兴趣的文章