infoarena

[#include <fstream>
#include <queue>
#include <cstring>
#define nmax 105
using namespace std;
ifstream fin("traseu3.in");
ofstream fout("traseu3.out");
 
struct rooms {
    short storey, line, column;
};
 
queue < rooms > tail;
 
int building[nmax][nmax][nmax], n, m;
 
bool was_here[nmax][nmax][nmax], sec_was_here[nmax][nmax][nmax];
 
int d_f[6] = {-1, 0, 0, 0, 0, 1};
int d_l[6] = {0, -1, 0, 0, 1, 0};
int d_c[6] = {0, 0, -1, 1, 0, 0};
 
bool is_ok(int x, int y, int z) {
    if (x < 1 or y < 1 or z < 1 or x > n or y > n or z > n or building[x][y][z] == -1 or was_here[x][y][z] == true)
        return false;
    return true;
}
 
void main_program() {
    while (!tail.empty()) {
        short storey = tail.front().storey;
        short line = tail.front().line;
        short column = tail.front().column;
        tail.pop();
        for (int k = 0; k < 6; ++k)
            if (is_ok(storey + d_f[k], line + d_l[k], column + d_c[k])) {
                building[storey + d_f[k]][line + d_l[k]][column + d_c[k]] = building[storey][line][column] + 1;
                was_here[storey + d_f[k]][line + d_l[k]][column + d_c[k]] = true;
                rooms stuff = {storey + d_f[k], line + d_l[k], column + d_c[k]};
                tail.push(stuff);
            }
    }
}
 
bool is_good(int x, int y, int z) {
    if (x < 1 or y < 1 or z < 1 or x > n or y > n or z > n or was_here[x][y][z] == false or sec_was_here[x][y][z] == true)
        return false;
    return true;
}
 
void second_main_program(int x, int y, int z, int stop_x, int stop_y, int stop_z) {
    while (!tail.empty()) {
        short storey = tail.front().storey;
        short line = tail.front().line;
        short column = tail.front().column;
        tail.pop();
        for (int k = 0; k < 6; ++k)
            if (is_ok(storey + d_f[k], line + d_l[k], column + d_c[k]))
                if (building[storey + d_f[k]][line + d_l[k]][column + d_c[k]] = building[storey][line][column] - 1) {
                    was_here[storey + d_f[k]][line + d_l[k]][column + d_c[k]] = true;
                    rooms stuff = {storey + d_f[k], line + d_l[k], column + d_c[k]};
                    tail.push(stuff);
                }
    }
    rooms stuff = {x, y, z};
    tail.push(stuff);
    fout << x << " " << y << " " << z << "\n";
    sec_was_here[x][y][z] = true;
    while (!tail.empty()) {
        short storey = tail.front().storey;
        short line = tail.front().line;
        short column = tail.front().column;
        tail.pop();
        for (int k = 0; k < 6; ++k)
            if (is_good(storey + d_f[k], line + d_l[k], column + d_c[k]))
                if (building[storey + d_f[k]][line + d_l[k]][column + d_c[k]] == building[storey][line][column] + 1) {
                    sec_was_here[storey + d_f[k]][line + d_l[k]][column + d_c[k]] = true;
                    rooms stuff = {storey + d_f[k], line + d_l[k], column + d_c[k]};
                    tail.push(stuff);
                    fout << storey + d_f[k] << " " << line + d_l[k] << " " << column + d_c[k] << "\n";
                    if (storey + d_f[k] == stop_x and line + d_l[k] == stop_y and column + d_c[k] == stop_z)
                        return;
                    break;
                }
    }
}
 
void read_input() {
    fin >> n >> m;
    int floor_m, line_m, column_m, floor_c, line_c, column_c;
    fin >> floor_m >> line_m >> column_m >> floor_c >> line_c >> column_c;
    rooms stuff = {floor_m, line_m, column_m};
    tail.push(stuff);
    was_here[floor_m][line_m][column_m] = true;
    building[floor_m][line_m][column_m] = 1;
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        building[x][y][z] = -1;
    }
    main_program();
    fout << building[floor_c][line_c][column_c] << "\n";
    stuff = {floor_c, line_c, column_c};
    tail.push(stuff);
    memset(was_here, false, sizeof(was_here));
    was_here[floor_c][line_c][column_c] = true;
    second_main_program(floor_m, line_m, column_m, floor_c, line_c, column_c);
}
 
int main()
{
    read_input();
    return 0;
}]