计蒜客模拟赛D2T3 蒜头君救人：用bfs转移状压dp

题目链接：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[]={1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441};

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=0;
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])%3)*POW[k]+a*POW[k];
}

inline int query(int v,int k)
{
    return (v/POW[k])%3;
}

void read()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;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=0;i<cnt;i++)
    {
        char ch;
        int speed;
        cin>>ch>>speed;
        spd[i]=speed;
    }
}

int cal_spd(int state)
{
    int sum=k;
    for(int i=0;i<cnt;i++)
    {
        int val=query(state,i);
        if(val==1) sum+=spd[i];
    }
    return sum>=1?sum:1;
}

bool is_legal(int x,int y)
{
    return c[x][y]!='#' && x>0 && x<=n && y>0 && y<=m;
}

int set_part(int state)
{
    for(int i=0;i<cnt;i++)
    {
        if(spd[i]<=0) continue;
        int val=query(state,i);
        if(val==1) update(state,i,2);
    }
    return state;
}

int set_all(int state)
{
    for(int i=0;i<cnt;i++)
    {
        int val=query(state,i);
        if(val==1) update(state,i,2);
    }
    return state;
}

int pick_up(int state,int k)
{
    return update(state,k,1);
}

void init_dp()
{
    for(int state=0;state<POW[cnt];state++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                dp[state][i][j]=INF;
            }
        }
    }
    dp[0][start.x][start.y]=0;
}

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+1,y) && dp[state][x+1][y]>dp[state][x][y]+speed)
        {
            dp[state][x+1][y]=dp[state][x][y]+speed;
            insert(sta(state,x+1,y));
        }
        if(is_legal(x-1,y) && dp[state][x-1][y]>dp[state][x][y]+speed)
        {
            dp[state][x-1][y]=dp[state][x][y]+speed;
            insert(sta(state,x-1,y));
        }
        if(is_legal(x,y+1) && dp[state][x][y+1]>dp[state][x][y]+speed)
        {
            dp[state][x][y+1]=dp[state][x][y]+speed;
            insert(sta(state,x,y+1));
        }
        if(is_legal(x,y-1) && dp[state][x][y-1]>dp[state][x][y]+speed)
        {
            dp[state][x][y-1]=dp[state][x][y]+speed;
            insert(sta(state,x,y-1));
        }
        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(0,start.x,start.y));
}

void print()
{
    cout<<dp[POW[cnt]-1][over.x][over.y]<<endl;
}

int main()
{
    read();
    solve();
    print();
}