小 S 正在玩一款寻宝游戏，这个游戏的目的是在有限的时间内寻到尽量多的宝藏。游

戏的地图是一个n行m列的网格，每个网格可能是“.”、“#”、“*”、“S”四种字符的一

种，分别表示空地、障碍、宝藏点和玩家位置。其中宝藏点一共有恰好k个，而玩家位置恰

好有一个。

小 S 控制的角色每秒可以向上下左右移动一格，不能走出边界或走到障碍上。当小 S

走到了一个宝藏点时，她可以瞬间收集这里的宝藏（这个宝藏点将变成空地）。

小 S 一共有T + 0.5秒时间行动，当时间截至游戏就会结束。小 S 想在游戏结束之前收

集尽量多的宝藏（即到达的不同的宝藏点尽量多），你能帮帮她吗？

---

 

让我考场心态爆炸的罪魁祸首，首先看一波数据范围

直接上BFS肯定过不了，然后发现k的值只有15，肯定从这里入手

先用bfs求出每两个点之间的距离，是O(nmk)的，OK没问题

然后来看如何转移，开始的时候我还是有一点想写DP的，但是死活没有想到状态该如何定义

然后就很弱智的写了一个全排列，还不够优秀，只拿了40分（常数小一点的话就是60）

考完之后听讲，发现自己就是个弟

请大家一定要记住下面的话

全排列是可以用状态压缩来优化的

首先定义数组dp[i][j]表示i状态的结尾是j的最小时间

这样很容易就得出了转移方程，每次选择一个还没有走过的点，然后枚举从哪里转移

具体看代码

然后再所有时间符合规范的里面选择宝藏数量最大的

下面给出代码：（注意，不是值越大的二进制数里的一就越多，被坑的很惨）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f;}inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ;}int n,m;int k,t;char map[506][506];struct node{ int x,y;}s[106];int cnt=1;int dis[106][106];int q1[1000006],q2[1000006];int v[1000006];int l=0,r=0;int book[506][506];int num[506][506];void bfs(int a){ l=0,r=0; memset(q1,0,sizeof(q1)); memset(q2,0,sizeof(q2)); memset(book,0,sizeof(book)); q1[++r]=s[a].x,q2[r]=s[a].y; book[s[a].x][s[a].y]=1; v[r]=0; while(l
            
             0&&!book[h1-1][h2]&&map[h1-1][h2]!='#'){ book[h1-1][h2]=1; q1[++r]=h1-1; q2[r]=h2; v[r]=v[l]+1; } if(h1+1<=n&&!book[h1+1][h2]&&map[h1+1][h2]!='#'){ book[h1+1][h2]=1; q1[++r]=h1+1; q2[r]=h2; v[r]=v[l]+1; } if(h2-1>0&&!book[h1][h2-1]&&map[h1][h2-1]!='#'){ book[h1][h2-1]=1; q1[++r]=h1; q2[r]=h2-1; v[r]=v[l]+1; } if(h2+1<=m&&!book[h1][h2+1]&&map[h1][h2+1]!='#'){ book[h1][h2+1]=1; q1[++r]=h1; q2[r]=h2+1; v[r]=v[l]+1; } } return ;}int p[106];int a[106];int dp[100006][20];int vis[10006];int ans=0;int f=0;int main(){ p[0]=1; for(int i=1;i<=20;i++) p[i]=p[i-1]*2; n=rd(),m=rd(),k=rd(),t=rd(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>map[i][j]; if(map[i][j]=='S'){ s[1].x=i,s[1].y=j; num[i][j]=1; } if(map[i][j]=='*'){ s[++cnt].x=i,s[cnt].y=j; num[i][j]=cnt; } } } for(int i=1;i<=k+1;i++) bfs(i); memset(dp,127,sizeof(dp)); dp[0][0]=0; for(int i=1;i<=k;i++) dp[1<<(i-1)][i]=dis[1][i+1]; for(int i=1;i<=p[k];i++){ for(int j=1;j<=k;j++){ if(i&1<
             
              =0;i--){ for(int j=1;j<=k;j++){ if(dp[i][j]<=t){ int h=i; int cnt=0; while(h){ if(h%2==1) cnt++; h/=2; } ans=max(ans,cnt); } } } write(ans); return 0;}