首页 > 代码库 > [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,否则输出一个整数，表示萃香需要移动的最少次数。
输入输出样例
5 5 10 3 31 11 1113 45 23 51 15 43 42 11 11 15 5
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][状态压缩]