题目链接：https://nanti.jisuanke.com/t/16444
题意：
蒜头君是一个乐于助人的好孩子，这天他所在的乡村发生了洪水，有多名村民被困于孤岛上，于是蒜头君决定去背他们离开困境，假设蒜头君所在的村子是n*m的网格，网格中.号代表平地，#号代表该地已被洪水淹没，A、B……等大写字母表示该地有村民被困，s代表蒜头君的起点，t代表蒜头君的终点。
蒜头君的初始速度为 k秒一格，他每次可以向上下左右4个方向中的一个移动1格。在背上一个村民后，他的速度可能会降低，也可能会加快，但他的速度不能快于1秒每格，那么蒜头君想知道，他最快需要多长时间将所有村民救出？
注意：不能在终点以外的地方放下村民；可以同时背多个村民。
题解：
用dp[state][x][y]表示现在在(x , y)这个点，村民的状态为state。state是一个三进制数，每一位对应一个村民，0表示村民还在原地，1表示正在背着这个村民，2表示这个村民已经到达终点。
显然，应该先枚举村民状态state，再枚举当前位置(x , y)。但本题和一般的网格dp不同，起点并不一定在左上角(1 , 1)处，而且并不是只能走右和下两个方向，因此本题需要从起点开始bfs，对于每一个被更新dp值的状态，都需要加入队列中。
下面考虑如何转移。
如果当前地点为'.'（平地），那么state不变，向上下左右四个方向转移（不能是'#'），dp[state][...][...]（上下左右） = min(dp[state][...][...] , dp[state][x][y] + cal_spd(state))，cal_spd(state)计算的是在当前状态时自己的速度。
如果当前地点为大写字母（有村民要救），并且当前state中这个村民还在原地，那么可以背上这个村民，dp[state_pick][x][y] = min(dp[state_pick][x][y] , dp[state][x][y])，state_pick为在当前state下再背上这个村民时的状态。
如果现在在终点t，很明显只有两种选择，一种是放下所有会让我减速的村民（能让我加速的村民肯定要一直背到底），一种是放下全部的村民（结束救人）。两种转移后的状态分别为state_part和state_all，那么dp[state_part][x][y] = min(dp[state_part][x][y] , dp[state][x][y])，dp[state_all][x][y] = min(dp[state_all][x][y] , dp[state][x][y])。
AC Code：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <queue>
#define MAX_N 15
#define MAX_S 60000
#define MAX_A 30
#define INF 10000000 using namespace std; const int POW[]={,,,,,,,,,,,,}; struct Coor
{
int x;
int y;
Coor(int _x,int _y)
{
x=_x;
y=_y;
}
Coor(){}
}; struct sta
{
int state;
int x;
int y;
sta(int _state,int _x,int _y)
{
state=_state;
x=_x;
y=_y;
}
sta(){}
}; int n,m,k;
int cnt=;
int spd[MAX_A];
int dp[MAX_S][MAX_N][MAX_N];
char c[MAX_N][MAX_N];
bool vis[MAX_S][MAX_N][MAX_N];
Coor start;
Coor over;
queue<sta> q; inline int update(int &v,int k,int a)
{
return v=v-((v/POW[k])%)*POW[k]+a*POW[k];
} inline int query(int v,int k)
{
return (v/POW[k])%;
} void read()
{
cin>>n>>m>>k;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
cin>>c[i][j];
if(c[i][j]=='s') start=Coor(i,j);
if(c[i][j]=='t') over=Coor(i,j);
if(isupper(c[i][j])) cnt++;
}
}
for(int i=;i<cnt;i++)
{
char ch;
int speed;
cin>>ch>>speed;
spd[i]=speed;
}
} int cal_spd(int state)
{
int sum=k;
for(int i=;i<cnt;i++)
{
int val=query(state,i);
if(val==) sum+=spd[i];
}
return sum>=?sum:;
} bool is_legal(int x,int y)
{
return c[x][y]!='#' && x> && x<=n && y> && y<=m;
} int set_part(int state)
{
for(int i=;i<cnt;i++)
{
if(spd[i]<=) continue;
int val=query(state,i);
if(val==) update(state,i,);
}
return state;
} int set_all(int state)
{
for(int i=;i<cnt;i++)
{
int val=query(state,i);
if(val==) update(state,i,);
}
return state;
} int pick_up(int state,int k)
{
return update(state,k,);
} void init_dp()
{
for(int state=;state<POW[cnt];state++)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
dp[state][i][j]=INF;
}
}
}
dp[][start.x][start.y]=;
} sta get_front()
{
sta now=q.front();
q.pop();
vis[now.state][now.x][now.y]=false;
return now;
} void insert(sta now)
{
if(vis[now.state][now.x][now.y]) return;
q.push(now);
vis[now.state][now.x][now.y]=true;
} void bfs(sta start)
{
memset(vis,false,sizeof(vis));
insert(start);
while(!q.empty())
{
sta now=get_front();
int x=now.x;
int y=now.y;
int state=now.state;
int speed=cal_spd(state);
if(is_legal(x+,y) && dp[state][x+][y]>dp[state][x][y]+speed)
{
dp[state][x+][y]=dp[state][x][y]+speed;
insert(sta(state,x+,y));
}
if(is_legal(x-,y) && dp[state][x-][y]>dp[state][x][y]+speed)
{
dp[state][x-][y]=dp[state][x][y]+speed;
insert(sta(state,x-,y));
}
if(is_legal(x,y+) && dp[state][x][y+]>dp[state][x][y]+speed)
{
dp[state][x][y+]=dp[state][x][y]+speed;
insert(sta(state,x,y+));
}
if(is_legal(x,y-) && dp[state][x][y-]>dp[state][x][y]+speed)
{
dp[state][x][y-]=dp[state][x][y]+speed;
insert(sta(state,x,y-));
}
if(c[x][y]=='t')
{
int state_part=set_part(state);
if(dp[state_part][x][y]>dp[state][x][y])
{
dp[state_part][x][y]=dp[state][x][y];
insert(sta(state_part,x,y));
}
int state_all=set_all(state);
if(dp[state_all][x][y]>dp[state][x][y])
{
dp[state_all][x][y]=dp[state][x][y];
insert(sta(state_all,x,y));
}
}
if(isupper(c[x][y]))
{
int state_pick=pick_up(state,c[x][y]-'A');
if(dp[state_pick][x][y]>dp[state][x][y])
{
dp[state_pick][x][y]=dp[state][x][y];
insert(sta(state_pick,x,y));
}
}
}
} void solve()
{
init_dp();
bfs(sta(,start.x,start.y));
} void print()
{
cout<<dp[POW[cnt]-][over.x][over.y]<<endl;
} int main()
{
read();
solve();
print();
}