首页 > 代码库 > [luogu P3786]萃香抱西瓜 [spfa][状态压缩]

[luogu P3786]萃香抱西瓜 [spfa][状态压缩]

题目背景

技术分享

伊吹萃香(Ibuki Suika)正在魔法之森漫步,突然,许多西瓜(Suika)从四周飞来,划出了绚丽的轨迹。虽然阵势有点恐怖,但她还是决定抱走一些西瓜。

题目描述

萃香所处的环境被简化为一个长为h,宽为w的网格平面。X坐标范围为[1,w],y坐标范围为[1,h]。

她初始(第1个时刻)站在坐标为sx,sy的方格。

西瓜可能在任意一个方格出现,在每个时间单位,它们可能向任何一个方向移动,也可能静止不动。西瓜的位置和移动的轨迹是已知的。西瓜的总数为n个,但只有m个西瓜可以被萃香抱走,因为其他都太大了,可能会砸伤她。

整个过程会持续T个时刻。萃香希望可以抱走全部的m个西瓜,并且在任何时候避免与任何一个过大的西瓜处在同一位置。抱走的方式为在某个时刻,与该西瓜处于同一位置。另外,由于萃香不愿耗费过多体力到处乱跑,她每个时刻可以选择静止不动,也可以选择移动到相邻的四个格子之一,只要不越出环境边界。如果选择移动到相邻格子,则算作移动了一次。(第1个时刻萃香刚站定,无法移动)

在每个时刻,如果萃香选择移动,可以认为萃香与西瓜同时从原来的位置移到了新的位置,没有先后顺序。

萃香想要知道,不被任何一个大西瓜砸中,并得到所有的m个小西瓜的情况下,最少需要移动多少次。

输入输出格式

输入格式:

第一行五个整数h,w,T,sx,sy,含义见题目描述。

第二行两个整数n,m,含义见题目描述。

接下来n段数据,每一段描述了一个西瓜的出现位置,时间,移动方式,是否可以被抱走等内容,具体如下:

首先一行,两个整数t1,t2,表示西瓜在t1时刻出现, t2时刻消失。若t2=T+1,表示西瓜在最后一个时刻也不消失。保证西瓜至少存在一个时刻。

接下来一行一个整数a,只能为0或1,0表示这个西瓜需要避开,1表示这个西瓜需要抱走。数据保证需要抱走的西瓜恰好有m个。

接下来t2-t1行,每一行两个整数x,y,顺序描述了从t1时刻到t2-1时刻,该西瓜的坐标。西瓜的移动不一定是连续的,并且是一瞬间完成的,所以无需考虑萃香是否站在了移动路径上。

输出格式:

如果萃香在整个T时刻内无法避免被大西瓜砸中或者无法收集到所有m个小西瓜,输出-1,否则输出一个整数,表示萃香需要移动的最少次数。

输入输出样例

输入样例#1:
5 5 10 3 31 11 1113 45 23 51 15 43 42 11 11 15 5
输出样例#1:
1

说明

样例说明:第2~4个时刻萃香站着不动,在第6个时刻,西瓜出现在萃香旁边,萃香移动到(3,4)位置即可抱走这个西瓜。

数据范围和提示:

子任务可能出现两种特殊性质A和B

A: 所有西瓜t1=1,t2=T+1

所有西瓜全程都静止在原地,不会发生移动。

B:m=0

共有10个子任务。

对于子任务1,具有特殊性质A和B

对于子任务2~3,仅具有特殊性质A

对于子任务4~5,仅具有特殊性质B

对于子任务6~10,不具有任何一个特殊性质。

对于全部子任务

1<=所有横坐标范围<=w1<=所有纵坐标范围<=h1<=h,w<=51<=T<=1001<=t1<=T2<=t2<=T+1t1<t21<=n<=200<=m<=10m<=n

一个位置不会同时出现两个或以上西瓜。


有趣的状压spfa

以及一开始感到神秘的   !!i

偷一波orangebird的官方题解

**********************************************************

子任务1:所有西瓜始终出现且不动,并且没有要抱走的。

解法:只需要判断初始位置是否被大西瓜挡住,挡住输出-1,否则输出0即可

子任务2~3:所有西瓜始终出现且不动。

解法:由于要抱走的西瓜最多为10个,考虑用长度为10的0/1串来表示某个西瓜是否已经获取。状压spfa或dp即可解决。

子任务4~5:没有需要抱走的西瓜

解法:将时间看做一个维度,构建好三维的地图,把西瓜看做障碍,做三维的最短路或dp即可。

正解:

结合子任务2~3和4~5的做法,做一个四维的状压最短路或dp即可解决。

**********************************************************

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<queue> 5 using namespace std; 6 #define inf 0x3f3f3f3f 7  8 inline int read(){ 9     int re=0;10     bool flag=0;11     char ch;12     while((ch=getchar())!=-&&(ch<0||ch>9));13     ch==-?flag=1:re=ch-0;14     while((ch=getchar())>=0&&ch<=9)  re=(re<<1)+(re<<3)+ch-0;15     return flag?-re:re;16 }17 18 struct node{19     int nows,nowt,nowx,nowy;20     node(int nows=0,int nowt=0,int nowx=0,int nowy=0):21         nows(nows),nowt(nowt),nowx(nowx),nowy(nowy){}22 };23 24 const int maxm=10,maxsize=6,maxt=101;25 26 int mp[maxsize][maxsize][maxt];27 int dis[maxsize][maxsize][maxt][1<<maxm];28 bool vis[maxsize][maxsize][maxt][1<<maxm];29 const int dirx[5]={0,1,-1,0,0},diry[5]={0,0,0,1,-1};30 const int stop=32;31 int mx,my,T,sx,sy;32 int n,m,cnt=-1;33 queue<node> que;34 35 void init(){36     memset(mp,inf,sizeof mp);37     mx=read();  my=read();  T=read();  sx=read();  sy=read();38     n=read();  m=read();39     for(int i=1;i<=n;i++){40         int t1=read(),t2=read(),a=read();41         if(!a)  a=stop;42         else  a=++cnt;43         for(int i=t1;i<t2;i++){44             int x=read(),y=read();45             mp[x][y][i]=a;46         }47     }48 }49 50 void spfa(){51     que.push(node(0,1,sx,sy));52     memset(dis,inf,sizeof dis);53     dis[sx][sy][1][0]=0;54     while(!que.empty()){55         node now=que.front();  que.pop();56         vis[now.nowx][now.nowy][now.nowt][now.nows]=0;57         if(now.nowt==T)  continue;58         for(int i=0;i<5;i++){59             int nexx=now.nowx+dirx[i];60             int nexy=now.nowy+diry[i];61             int next=now.nowt+1;62             int nexs;63             if(nexx<1||nexx>mx||nexy<1||nexy>my)  continue;64             if(mp[nexx][nexy][next]==stop)  continue;65             if(mp[nexx][nexy][next]==inf)  nexs=now.nows;66             else  nexs=now.nows|(1<<mp[nexx][nexy][next]);67             if(dis[nexx][nexy][next][nexs]<=dis[now.nowx][now.nowy][now.nowt][now.nows]+!!i)  continue;68             dis[nexx][nexy][next][nexs]=dis[now.nowx][now.nowy][now.nowt][now.nows]+!!i;69             if(!vis[nexx][nexy][next][nexs]){70                 vis[nexx][nexy][next][nexs]=1;71                 que.push(node(nexs,next,nexx,nexy));72             }73         }74     }75 }76 77 void solve(){78     spfa();79     int ans=inf;80     for(int i=1;i<=mx;i++)81         for(int j=1;j<=my;j++)82             ans=min(ans,dis[i][j][T][(1<<m)-1]);83     if(ans==inf)  ans=-1;84     printf("%d\n",ans);85 }86 87 int main(){88     //freopen("temp.in","r",stdin);89     init();90     if(mp[sx][sy][1]==stop){91         puts("-1");92         return 0;93     }94     solve();95     return 0;96 }

 

[luogu P3786]萃香抱西瓜 [spfa][状态压缩]