Time Limit: 2000MS Memory Limit: 32768KB 64bit IO Format: %I64d & %I64u

Description

Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.

Input

Output

Sample Input

1

3 3 4 20

0 1 1 1

0 0 1 1

0 1 1 1

1 1 1 1

1 0 0 1

0 1 1 1

0 0 0 0

0 1 1 0

0 1 1 0

Sample Output

11

AC代码：

#include <cstdio>
#include <queue>
using namespace std;
char map[55][55][55];
int a, b, c, t;
struct node
{
int x, y, z, step;
bool operator == (const node b) const
{
return x == b.x && y == b.y && z == b.z;
}
};
const int dx[] = {0, 0, 0, 0, 1, -1},
dy[] = {0, 0, 1, -1, 0, 0},
dz[] = {1, -1, 0, 0, 0, 0};
node start, goal;
queue <node> q;
void input()
{
scanf("%d%d%d%d", &a, &b, &c, &t);
for (int i = 0; i < a; i++)
for (int j = 0; j < b; j++)
for (int k = 0; k < c; k++)
scanf("%d", &map[i][j][k]);
}
bool check(int x, int y, int z)
{
if (x < 0 || x >= a || y < 0 || y >= b || z < 0 || z >= c || map[x][y][z])
return 0;
return 1;
}
int Abs(int x)
{
if (x > 0)
return x;
return -x;
}
int dis(node a, node b)
{
return Abs(a.x - b.x) + Abs(a.y - b.y) + Abs(a.z - b.z);
}
void solve()
{
while (!q.empty())
q.pop();
start = (node){0, 0, 0, 0};
goal = (node){a - 1, b - 1, c - 1, 0};
q.push(start);
while (!q.empty())
{
node u = q.front();
q.pop();
if (u.step > t)
break;
if (u == goal)
{
printf("%d\n", u.step);
return;
}
if (dis(u, goal) > t - u.step)
continue;
node next;
for (int i = 0; i < 6; i++)
{
next.x = u.x + dx[i];
next.y = u.y + dy[i];
next.z = u.z + dz[i];
if (!check(next.x, next.y, next.z))
continue;
map[next.x][next.y][next.z] = 1;
next.step = u.step + 1;
q.push(next);
}
}
printf("-1\n");
}
int main()
{
int K;
scanf("%d", &K);
while (K--)
{
input();
solve();
}
return 0;
}