3923. Minimum Generations to Target Point

You are given a 2D integer array points where points[i] = [x_i, y_i, z_i] represents a point in 3D space, and an integer array target representing a target point.

Define generation 0 as the initial list of points. For each integer k >= 1, form generation k as follows:

• Consider every pair of two distinct points a = [x_1, y_1, z_1] and b = [x_2, y_2, z_2] taken from all points produced in generations 0 through k - 1.
• For each such pair, compute c = [floor((x_1 + x_2) / 2), floor((y_1 + y_2) / 2), floor((z_1 + z_2) / 2)] and collect every such c into a generation k.
• All points in the generation k are produced simultaneously from points in generations 0 through​​​​​​​ k - 1.
• After generation k is formed, the points in the generation k are considered available for forming later generations.

Return the smallest integer k such that the target appears in one of the generations 0 through k. If the target is already in the initial points, return 0. If it is impossible to obtain the target, return -1.

Notes:

• floor denotes rounding down to the nearest integer.
• “Two distinct points” means the two chosen points must have different (x, y, z) coordinates. A point cannot be paired with itself, and pairing two points with identical coordinates is not possible.

int vis[11][11][11];
class Solution {
public:
    int minGenerations(vector<vector<int>>& points, vector<int>& target) {
        vector<vector<int>> p;
        deque<vector<int>> q(begin(points), end(points));
        memset(vis,-1,sizeof vis);
        for(auto& p : points) vis[p[0]][p[1]][p[2]] = 0;
        auto merge = [&](vector<int>& A, vector<int>& B) {
            vector<int> res;
            for(int i = 0; i < 3; i++) res.push_back((A[i] + B[i]) / 2);
            return res;
        };
        while(q.size() and vis[target[0]][target[1]][target[2]] == -1) {
            auto now = q.front(); q.pop_front();
            for(auto& ps : p) {
                auto nxt = merge(now,ps);
                if(vis[nxt[0]][nxt[1]][nxt[2]] == -1) {
                    vis[nxt[0]][nxt[1]][nxt[2]] = vis[now[0]][now[1]][now[2]] + 1;
                    q.push_back(nxt);
                }
            }
            p.push_back(now);
        }
        return vis[target[0]][target[1]][target[2]];
    }
};