萃香抱西瓜

题目

萃香所处的环境被简化为一个长为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 3

1 1

1 11

1

3 4

5 2

3 5

1 1

5 4

3 4

2 1

1 1

1 1

5 5

输出样例

1

思路

将当前已经得到的西瓜进行状压 用01串表示存起来

记录当前位置 x y

记录到达当前位置所需时间

将以上状态作为下标跑四维spfa即可

用 dis[i][j][k][l] 表示到达位置(i, j)耗时k时间并且已摘西瓜状态为l 需要移动多少次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define INF 1 << 30
using namespace std;
struct node{
int x, y, time, state;
};
int h, w, T, sx, sy, n, m, NO;
/*x<=w y<=h 持续T时间 最初位置为(sx,sy) 共有n个西瓜 能收集的有m个西瓜*/
int map[6][6][103], dis[6][6][103][1024], vis[6][6][103][1024], cnt = -1;
queue<node> q;
int dx[5] = {0,0,1,0,-1};
int dy[5] = {0,1,0,-1,0};
inline void spfa()
{
q.push((node){sx, sy, 1, 0});
memset(dis, 127, sizeof(dis));
dis[sx][sy][1][0] = 0;
while(!q.empty())
{
node now = q.front();q.pop();
vis[now.x][now.y][now.time][now.state] = 0;
if (now.time == T) continue;
for (int i=0; i<5; i++)
{
int nx = now.x + dx[i], ny = now.y + dy[i];
int nt = now.time + 1;int ns;
if (nx<1 || nx>w) continue;
if (ny<1 || ny>h) continue;
if (map[nx][ny][nt] == INF) continue;
if (map[nx][ny][nt] == NO) ns = now.state;
else ns = now.state|(1<<map[nx][ny][nt]);
if (dis[nx][ny][nt][ns] > dis[now.x][now.y][now.time][now.state] + !!i)
dis[nx][ny][nt][ns] = dis[now.x][now.y][now.time][now.state] + !!i;
if (!vis[nx][ny][nt][ns])
{
vis[nx][ny][nt][ns] = 1;
q.push((node){nx,ny,nt,ns});
}
}
}
}
int main()
{
scanf("%d%d%d%d%d", &h, &w, &T, &sx, &sy);
scanf("%d%d", &n, &m);
memset(map, 127, sizeof(map));
NO = map[0][0][0];
for (int i=1; i<=n; i++)
{
int t1, t2, a;
scanf("%d%d%d", &t1, &t2, &a);
if (a == 0) a = INF;
else a = ++cnt;
for (int j=t1; j<t2; j++)
{
int x, y;
scanf("%d%d", &x, &y);
map[x][y][j] = a;
}
}
if (map[sx][sy][1] == INF) {printf("-1\n"); return 0;}
spfa();
int ans = INF;
for (int i=1; i<=w; i++)
for (int j=1; j<=h; j++)
ans = min(ans, dis[i][j][T][(1<<m)-1]);
ans = ans==INF ? -1 : ans;
printf("%d\n", ans);
return 0;
}