CCPC2019 Xiamen H. Zayin and Obstacles

题目

Recently, Zayin became obsessed with a tower defense game called Arknights. The most special level is the 5th level of chapter 4: Don’t panic. The most special thing about this level is that an enemy will continue taking radioactive damage after passing through the Active Originiums. As the most handsome man in the world, he tried to put obstacles in various positions, making all the enemies to be killed before reaching the end. After many attempts, he finally won the three stars clearance award.

Interestingly, that night Zayin dreamt that he had become the King Slayer (the leader of enemies). In the dream, the map of the tower defense game becomes a cube with edge length $n$. Zayin can take a step forward, backward, up, down, left or right from his current position every second, but can’t get out of the map or walk through a grid of obstacles.

As in the original game, the player, who wants to kill all the enemies, can put obstacles many times. In particular, in the dream, every time players can place obstacles at all the coordinates $(x,y,z)$ which satisfies $a \leq x \leq d$, $b \leq y \leq e$, $ c \leq z \leq f$, and has no obstacles yet.

Now, Zayin knows that the player will place obstacles $m$ times and the locations of each time. In order to avoid dying on the way, Zayin wants to go to the end as fast as possible. But unfortunately, Zayin got lost for so long that all the obstacles were placed. Now, Zayin asks you for help. Can you help him get out of the map as quickly as possible?

Input

The first line of input contains an integer $T (1 \leq T \leq 5)$, denoting the number of test cases.

Each test case starts with two integers $n$ and $m$ in a line, where $n$ is the size of the map and $m$ is the number of times the player puts obstacles. $(1 \leq n \leq 100, 1 \leq m \leq 1000)$

The next $m$ lines contain six integers $a,b,c,d,e,f$ in each line, denoting the range of obstacles the player puts. $(1 \leq a \leq d \leq n, 1 \leq b \leq e \leq n, 1 \leq c \leq f \leq n)$

Then there are six integers $x_1,y_1,z_1,x_2,y_2,z_2$. The first three integers represent where Zayin is now, and the last three integers represent where the end point is.

Output

For each testcase, output an integer in a line, denoting how many seconds at least Zayin need to go to the end. If Zayin can’t go to the end, output $-1$.

Sample

Input

1
2
3
4
5
6
7
8
9
10
11
3
3 0
1 1 1 3 3 3
3 1
2 1 1 2 3 3
1 1 1 3 3 3
3 3
2 1 1 2 2 3
1 1 2 2 3 2
1 2 2 3 3 2
1 1 1 1 1 3

Output

1
2
3
6
-1
14

题意简述

给定一个$n\times n \times n(n \leq 100)$的立方矩阵地图,其中有$m$个从$(a_i,b_i,c_i)$到$(d_i,e_i,f_i)$的长方体障碍物,给定起点$(x_1,y_1,z_1)$和终点$(x_2,y_2,z_2)$。求路径长度。

题解

使用三维前缀和处理障碍物,然后直接BFS,时间复杂度$O(N^3)$。

代码:

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <cstdio>
#include <queue>

using LL = long long;

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

const int inf = 0x7f7f7f7f;

const int maxn = 100 + 10;

const int dx[] = {1, 0, 0, -1, 0, 0};
const int dy[] = {0, 1, 0, 0, -1, 0};
const int dz[] = {0, 0, 1, 0, 0, -1};

int n, m;
int sx, sy, sz, tx, ty, tz;

struct PointNode
{
int x, y, z;
PointNode(int x, int y, int z) : x(x), y(y), z(z) {}
};

int sum[maxn][maxn][maxn];
int dis[maxn][maxn][maxn];

void init()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
dis[i][j][k] = inf;
sum[i][j][k] = 0;
}
}
}
}

void calc()
{
for (int i = 1; i <= n + 1; i++)
{
for (int j = 1; j <= n + 1; j++)
{
for (int k = 1; k <= n + 1; k++)
{
sum[i][j][k] +=(sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1])
-(sum[i-1][j-1][k]+sum[i-1][j][k-1]+sum[i][j-1][k-1])
+sum[i-1][j-1][k-1];
}
}
}
}

void bfs()
{
std::queue<PointNode> que;
dis[sx][sy][sz] = 0;
que.push(PointNode(sx, sy, sz));

while (!que.empty())
{
auto fr = que.front();
que.pop();
int x = fr.x, y = fr.y, z = fr.z;
for (int i = 0; i < 6; i++)
{
int xx = x + dx[i], yy = y + dy[i], zz = z + dz[i];
if (!(xx<1 || xx>n || yy<1 || yy>n || zz<1 || zz>n || sum[xx][yy][zz]))
{
if (dis[xx][yy][zz] > dis[x][y][z] + 1)
{
dis[xx][yy][zz] = dis[x][y][z] + 1;
que.push(PointNode(xx, yy, zz));
}
}
}
}
}

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
init();
for (int i = 1; i <= m; i++)
{
int a, b, c, d, e, f;
scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
sum[a][b][c]++;
sum[d+1][b][c]--;
sum[a][e+1][c]--;
sum[a][b][f+1]--;
sum[d+1][e+1][c]++;
sum[d+1][b][f+1]++;
sum[a][e+1][f+1]++;
sum[d+1][e+1][f+1]--;
}
scanf("%d%d%d%d%d%d", &sx, &sy, &sz, &tx, &ty, &tz);
calc();
bfs();
printf("%d\n", dis[tx][ty][tz] == inf ? -1 : dis[tx][ty][tz]);
}
return 0;
}