Luogu萃香抱西瓜
2017-08-04萃香抱西瓜
题目描述
萃香所处的环境被简化为一个长为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,否则输出一个整数，表示萃香需要移动的最少次数。
思路
状压，四维spfa（然而时间那一维可以压掉）
输入处理出每个时间点上的地图的情况，有瓜就把对应的瓜压成01串，没有就不管，有一个障碍（大西瓜）就打个标记（比如-1）
然后愉悦的spfa就好了
一个点能够转移到五个点，上下左右以及自己，到自己是不用移动（+距离）的，但是时间要+1（所以说时间是可以压掉的，就算压不掉开个2用开关滚动也已经很够用了）
判定合法除了越界还有目标点不能有一个大西瓜
然后愉♂悦的spfa就好了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 336860180
using namespace std;
int dis[7][7][110][2050],init[7][7][110][2050];
int map[7][7][110],h,w,n,m,t,sx,sy;
int js,ans=inf;
int tx[6]=
{
0,-1,0,1,0,0
};
int ty[6]=
{
0,0,-1,0,1,0
};
int len[6]=
{
0,1,1,1,1,0
};
struct node
{
int x,y,t,sta;
};
queue<node> q;
bool can(int nx,int ny,int nt)
{
if(nt>t) return false;
if(nx>w||nx<1) return false;
if(ny>h||ny<1) return false;
if(map[nx][ny][nt]==-1) return false;
return true;
}
void spfa()
{
memset(dis,20,sizeof(dis));
int bsta=0;
if(map[sx][sy][1]!=-1) bsta|=map[sx][sy][1];
else return;
dis[sx][sy][1][bsta]=0;
init[sx][sy][1][bsta]=1;
q.push((node){sx,sy,1,bsta});
while(!q.empty())
{
node now=q.front();q.pop();
init[now.x][now.y][now.t][now.sta]=0;
for(int i=1;i<=5;++i)
{
int tsta=now.sta,tox=now.x+tx[i],toy=now.y+ty[i],tt=now.t+1;
if(can(tox,toy,tt))
{
tsta=now.sta|map[tox][toy][tt];
if(dis[tox][toy][tt][tsta]>dis[now.x][now.y][now.t][now.sta]+len[i])
{
dis[tox][toy][tt][tsta]=dis[now.x][now.y][now.t][now.sta]+len[i];
if(!init[tox][toy][tt][tsta])
{
init[tox][toy][tt][tsta]=1;
q.push((node){tox,toy,tt,tsta});
}
}
}
}
}
}
int main()
{
scanf("%d%d%d%d%d",&h,&w,&t,&sx,&sy);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
int t1,t2,fl;
scanf("%d%d%d",&t1,&t2,&fl);
if(fl==0)
{
for(int j=t1;j<t2;++j)
{
int x,y;
scanf("%d%d",&x,&y);
map[x][y][j]=-1;
}
}
else
{
js++;
for(int j=t1;j<t2;++j)
{
int x,y;
scanf("%d%d",&x,&y);
map[x][y][j]=(1<<js);
}
}
}
int to=0;
for(int i=1;i<=m;++i) to|=(1<<i);
spfa();
for(int i=1;i<=w;++i)
{
for(int j=1;j<=h;++j)
{
ans=min(ans,dis[i][j][t][to]);
}
}
if(ans>=inf) ans=-1;
printf("%d",ans);
return 0;
}