# De men phieu luu ky

unknown
c_cpp
16 days ago
3.0 kB
2
Indexable
Never
```#define DEBUG freopen("input.txt", "r", stdin)

#ifdef DEBUG
#include <time.h>
#endif

#include <iostream>
#include <stdio.h>
using namespace std;

#define f(i, a, b, d) for (int i = a; i < b; i += d)
#define fr(i, a, b, d) for (int i = a; i <= b; i += d)
#define rf(i, a, b, d) for (int i = a; i >= b; i -= d)

template <typename T = int, int N = 999999>
class Queue {
private:
T arr[N];
int front, tail;

public:
Queue() {
clear();
}

void clear() {
front = tail = -1;
}

bool isEmpty() {
return front == -1;
}

bool isFull() {
return (tail + 1) % N == front;
}

void push(T x) {
if (isFull()) {
cerr << "[ERROR] Queue is full" << endl;
return;
}
if (front == -1) {
front = 0;
}
tail = (tail + 1) % N;
arr[tail] = x;
}

T pop() {
// todo: check if empty
T x = arr[front];
if (front == tail) {
clear();
} else {
front = (front + 1) % N;
}
return x;
}

T peek() {
return arr[front];
}
};

#define mapP(a, point) a[point.x][point.z][point.y]
struct Point {
int x, y, z;

void assign(int x, int z, int y) {
this->x = x;
this->y = y;
this->z = z;
}
};

const Point dir[] = {
{ 0, 0, 1 },
{ 0, 0, -1 },
{ 0, 1, 0 },
{ 0, -1, 0 },
{ 1, 0, 0 },
{ -1, 0, 0 }
};
const int nDir = sizeof(dir) / sizeof(*dir);

const int oo = 2 * 999999999;
const int N = 32;
int tnum, ans;
int n;
int a[N][N][N];
int step[N][N][N];
Point start;

void input() {
cin >> n;
f(x, 0, n, 1) {
f(z, 0, n, 1) {
f(y, 0, n, 1) {
cin >> a[x][z][y];
if (a[x][z][y] == 2) {
start.assign(x, z, y);
}
}
}
}

f(x, 0, n, 1) {
f(y, 0, n, 1) {
a[x][n][y] = 7;
}
}
}

bool inBound(Point p) {
// z == n is the wall
return p.x >= 0 && p.x < n && p.y >= 0 && p.y < n && p.z >= 0 && p.z <= n;
}

void bfs() {
static Queue<Point> q;
Point cur, next;
f(x, 0, n, 1) {
f(z, 0, n, 1) {
f(y, 0, n, 1) {
step[x][z][y] = oo;
}
}
}

q.clear();
q.push(start);
mapP(step, start) = 0;
while (!q.isEmpty()) {
cur = q.pop();
f(i, 0, nDir, 1) {
next = cur;
next.x += dir[i].x;
next.z += dir[i].z;
next.y += dir[i].y;

if (!inBound(next)) {
ans = min(ans, mapP(step, cur));
continue;
}

if (mapP(a, next) < 2
&& mapP(step, next) > (mapP(step, cur) + mapP(a, next))
) {
mapP(step, next) = mapP(step, cur) + mapP(a, next);
q.push(next);
}
}
}
}

void solve() {
input();
ans = oo;
bfs();
printf("#%d %d\n", tnum, ans);
}

int main() {

#ifdef DEBUG
fprintf(stderr, "Running on Debug mode\n");
clock_t start = clock();
DEBUG;
#endif

int t;
cin >> t;
for (tnum = 1; tnum <= t; tnum++) {
solve();
}

#ifdef DEBUG
double duration = double(clock() - start) / CLOCKS_PER_SEC;
fprintf(stderr, "Finished in %.6lf seconds\n", duration);
#endif

return 0;
}```