Написать функцию, которая найдёт возможный вариант размещения жителей племени - C (СИ)

Формулировка задачи:

Есть такая интересная задачка, давалась в одном из вузов на экзамене в первом семестре.

int housing (int a[N][N], int k, int m, int h[]) {
   ...
   ...
}

Решение задачи: «Написать функцию, которая найдёт возможный вариант размещения жителей племени»

Листинг программы

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <memory.h>
 
#define N 50
 
const int m = 5;  // number of persons in a single house
const int s = 12; // number of houses
 
int g_house = 1, d = 0;
 
void init_tree(int** tree)
{
    for (int i = 0; i < N; i++)
    {
        int j = 0; tree[i] = new int[N];
        while (j < N) tree[i][j++] = (j > i) ? 1 : 0;
    }
}
 
void gen_entities(int* ent)
{
    for (int i = 0; i < N; i++)
        ent[i] = rand() % 2;
}
 
void invert_entities(int* ent, int* r_ent, int count)
{
    for (int i = 0; i < count; i++)
        r_ent[i] = ent[i] == 0 ? 1 : 0;
}
 
int find_root(int* ent)
{
    int i = 0; while (ent[i] == 0) i++;
    return i;
}
 
bool is_visited(int* p, int top, int count)
{
    for (int i = 0; i < count; i++)
         if (p[i] == top) return true;
    return false;
}
 
void housing(int** tree, int* entities, int* houses, int* visited, int r)
{
    int w = 0, count = w;
    int nh = count = houses[r] = 
        (houses[r] == 0) ? g_house : houses[r]; 
    
    if (is_visited(visited, r, d)) return;
 
    int matched[N] = { 0 }; visited[d++] = r;
    for (int index = 0; index < N; index++)
        if (entities[r] == entities[index] && tree[r][index])
        {
            matched[w++] = index;
 
            if (count >= m) { count = 0; nh++; }
            houses[index] = (houses[index] == 0) ? nh : houses[index];
 
            tree[r][index] = 0; count++; 
        }
 
    for (int nindex = 0; matched[nindex] > 0; nindex++)
        housing(tree, entities, houses, visited, matched[nindex]);
 
    g_house = nh;
}
 
int main()
{ 
    g_house = 1;
 
    int*  p = new int[N];  gen_entities(p);
    int** a = new int*[N]; init_tree(a);
 
    int *h = new int[N], *v = new int[N];
    memset((void*)h, 0x00, sizeof(int) * N);
    memset((void*)v, 0x00, sizeof(int) * N);
 
    housing(a,p,h,v,0);
 
    int* inv_p = new int[N]; invert_entities(p, inv_p, N);
    int r = find_root(inv_p);
 
    memset((void*)v, 0x00, sizeof(int) * N);
 
    housing(a,inv_p,h,v,r);
    
    for (int m = 0; m < N; m++)
        printf("%d ",h[m]);
    printf("\n");
 
    _getch();
 
    return 0;
}

Объяснение кода листинга программы

В этом коде решается задача поиска оптимального размещения жителей племени в домах. Код использует следующие переменные:

N - общее количество жителей племени (50 человек).
m - количество жителей в одном доме (5 человек).
s - количество домов (12 штук).
g_house - номер первого дома для размещения жителей (1).
d - счетчик количества размещенных жителей.
entities - массив, в котором для каждого жителя племени указывается, является ли он владельцем какого-либо дома (0 или 1).
tree - матрица, представляющая собой дерево возможных вариантов размещения жителей в домах.
houses - массив, в котором для каждого дома указывается, сколько жителей в нем проживает.
visited - массив, в котором для каждого дома указывается, был ли он уже проверен на возможность размещения жителей.
r - номер текущего проверяемого дома. Вначале кода создаются и инициализируются все необходимые переменные и массивы. Затем происходит генерация случайных значений для каждого жителя племени и заполнение матрицы tree значениями, соответствующими возможному размещению жителей в домах. Далее вызывается функция housing, которая рекурсивно ищет оптимальное размещение жителей в домах. Она принимает на вход матрицу tree, массив entities, массив houses и массив visited. В этой функции происходит обход всех возможных вариантов размещения жителей в домах и поиск оптимального. В конце кода выводится на экран номер дома, в котором разместилось больше всего жителей.