Member 13848263 Ответов: 1

Как разбить целочисленный массив на "районы"?

У меня есть целочисленный массив 10x10 (назовем его "таблицей"), и у меня есть итеративная задача, которую мне нужно выполнить в C++ с этим массивом. По сути, мне нужно сделать все возможные варианты разделения таблицы на "районы" внутри таблицы, где под "районом" я подразумеваю набор записей таблицы, удовлетворяющих требованиям

1) каждый район состоит из 10 записей таблицы

2) каждая запись в округе примыкает по крайней мере к одной другой записи в округе. То есть для каждой записи a_ij в округе должна быть другая запись в округе выше, ниже, справа или слева от a_ij (диагональное движение не считается смежным).

Что мне нужно, так это пройти через все возможные деления этой таблицы на районы. Таким образом, одно возможное деление-каждая строка-это район, другое возможное деление-каждый столбец-это район и т. д. Для каждого возможного деления у меня есть вычисление, которое мне нужно сделать, но я знаю, как это сделать, я просто не знаю, как реализовать марширование всех возможных вариантов разделения таблицы на районы. Есть ли в библиотеке алгоритмов алгоритм, который мог бы мне помочь? Или это просто кодировать с нуля? Я прошу прощения, если это тривиальный вопрос, я не очень хорошо знаю C++, но мне нужно сделать это для отдельного проекта.

Что я уже пробовал:

Я попытался продумать алгоритм и попытаться найти что-то похожее в библиотеке алгоритмов C++.

John R. Shaw

Похоже, пришло время достать бумагу и карандаш. Нарисуйте 2-мерный массив [сетка 10x10] с соответствующими значениями, чтобы вы могли визуализировать проблему.

Daniel Pfeffer

Посмотрите на статьи о полимино.

Это звучит как проблема плитки (покройте область плитками разных форм/размеров). Метод грубой силы должен начинаться с написания алгоритма для создания всех возможных 10-плиток, а затем писать алгоритм, который пытается упаковать 10 из них в определенной области, но, вероятно, есть лучшие методы для этого.

Предположим, что у вас есть любое количество плиток каждой формы. Не забывайте о поворотах и зеркалах плиточных форм!

1 Ответов

Рейтинг:
0

Arthur V. Ratz

Вот мое решение:

// ConsoleApplication3.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
#include <time.h>

#define N 10
#define DIST_N 10

typedef struct tagDists
{
	int** dist;
	int size_x;
	int size_y;
	bool is_d;
} DISTS, *LP_DISTS;

int main()
{
	int** matrix = (int**)malloc(sizeof(int*) * N);
	memset((void*)matrix, 0x00, sizeof(int*) * N);

	srand((unsigned)time(nullptr));

	for (int i = 0; i < N; i++)
	{
		matrix[i] = (int*)malloc(sizeof(int) * N);
		memset((void*)matrix[i], 0x00, sizeof(int) * N);
		for (int j = 0; j < N; j++)
		{
			matrix[i][j] = rand() % 9 + 1;
			printf("%d ", matrix[i][j]);
		}

		printf("\n");
	}

	printf("\n");

	int dist_size = (int)pow((double)N, 2) / DIST_N;
	
	int dist_size_x = int(sqrt((double)dist_size));
	int dist_size_y = dist_size / dist_size_x;

	int n_chunks_row = int(ceil(N / (double)dist_size_x));
	int n_chunks_col = int(ceil(N / (double)dist_size_y));

	int n_dists = n_chunks_row * n_chunks_col;

	LP_DISTS dists = (LP_DISTS)malloc(sizeof(DISTS) * n_dists);
	memset((void*)dists, 0x00, sizeof(DISTS) * n_dists);

	int n = 0;
	for (int t1 = 0; t1 < n_chunks_row; t1++)
	{
		int start_x = t1 * dist_size_x;
		int end_x = (t1 + 1) * dist_size_x;

		start_x = (start_x > N) ? N : start_x;
		end_x = (end_x > N) ? N : end_x;

		for (int t2 = 0; t2 < n_chunks_col; t2++)
		{
			int start_y = t2 * dist_size_y;
			int end_y = (t2 + 1) * dist_size_y;

			start_y = (start_y > N) ? N : start_y;
			end_y = (end_y > N) ? N : end_y;

			dists[n].dist = (int**)malloc(sizeof(int*) * abs(start_x - end_x));

			int n_i = 0;
			for (int i = start_x; i < end_x; i++, n_i++)
			{
				dists[n].dist[n_i] = (int*)malloc(sizeof(int) * abs(start_y - end_y));
				
				int n_j = 0;
				for (int j = start_y; j < end_y; j++, n_j++)
					dists[n].dist[n_i][n_j] = matrix[i][j];
			}

			dists[n].is_d = false;
			dists[n].size_x = abs(start_x - end_x);
			dists[n].size_y = abs(start_y - end_y);

			n++;
		}
	}

	for (int t = 0; t < n_dists; t++)
	{
		if ((dists[t].size_x < dist_size_x) ||
			(dists[t].size_y < dist_size_y))
		{
			int n_items = dists[t].size_x * dists[t].size_y;
			int items_per_dist = int(ceil(n_items / ((double)dist_size_x * dist_size_y)));

			int* v = (int*)malloc(sizeof(int) * dists[t].size_x * dists[t].size_y);
			memset((void*)v, 0x00, sizeof(int) * dists[t].size_x * dists[t].size_y);

			int n = 0;
			for (int s1 = 0; s1 < dists[t].size_x; s1++)
				for (int s2 = 0; s2 < dists[t].size_y; s2++)
					v[n++] = dists[t].dist[s1][s2];

			for (int i = 0, n = 0; i < n_dists && n_items > 0; i++)
			{
				if ((dists[i].size_x >= dist_size_x) &&
					(dists[i].size_y >= dist_size_y) && i != t)
				{
					if (dists[i].size_x * dists[i].size_y < dist_size)
					{
						dists[t].is_d = true;

						int rows = int(ceil(items_per_dist / (double)N));
						dists[i].dist = (int**)realloc(dists[i].dist, sizeof(int) * rows * dists[i].size_y);

						dists[i].size_x += rows;

						int i2 = dists[t].size_x;
						for (int i1 = dists[i].size_x - rows; i1 < dists[i].size_x && --i2 >= 0; i1++)
						{
							int j2 = dists[t].size_y;
							dists[i].dist[i1] = (int*)malloc(sizeof(int) * dists[i].size_y);
							memset((void*)dists[i].dist[i1], 0x00, sizeof(int) * dists[i].size_y);
							for (int j1 = 0; j1 < dists[i].size_y && --j2 >= 0; j1++)
							{
								dists[i].dist[i1][j1] = v[n++]; n_items--;
							}
						}
					}
				}
			}
		}
	}

	int* v = (int*)malloc(sizeof(int) * dist_size);
	memset((void*)v, 0x00, sizeof(int) * dist_size);

	int r = 0;
	for (int t = 0; t < n_dists; t++)
	{
		if ((dists[t].size_x < dist_size_x) ||
			(dists[t].size_y < dist_size_y))
		{
			if (dists[t].is_d == false)
			{
				for (int i = 0; i < dists[t].size_x && i < N; i++)
					for (int j = 0; j < dists[t].size_y && j < N; j++)
						v[r++] = dists[t].dist[i][j];
			}
		}
	}

	int** dist = (int**)malloc(sizeof(int*) * dist_size_x + 1);
	memset((void*)dist, 0x00, sizeof(int*) * dist_size_x + 1);

	for (int i = 0, r = 0; i < dist_size_x; i++)
	{
		dist[i] = (int*)malloc(sizeof(int) * dist_size_y);
		memset((void*)dist[i], 0x00, sizeof(int) * dist_size_y);
		for (int j = 0; j < dist_size_y; j++) 
			dist[i][j] = v[r++];
	}

	dist[dist_size_x] = (int*)malloc(sizeof(int) * dist_size_y);
	memset((void*)dist[dist_size_x], 0x00, sizeof(int) * dist_size_y);

	dist[dist_size_x][0] = v[r - 1];

	int x = 0;
	for (int t = 0; t < n_dists; t++)
	{
		if ((dists[t].size_x >= dist_size_x) &&
			(dists[t].size_y >= dist_size_y))
		{
			if (dists[t].is_d == false)
			{
				printf("District: %d\n", x + 1);

				for (int i = 0; i < dists[t].size_x && i < N; i++)
				{
					for (int j = 0; j < dists[t].size_y && j < N; j++)
						printf("%d ", dists[t].dist[i][j]);

					printf("\n");
				}

				printf("\n");

				x++;
			}
		}
	}

	printf("District: %d\n", x + 1);

	for (int i = 0; i < dist_size_x + 1; i++)
	{
		for (int j = 0; j < dist_size_y; j++)
			printf("%d ", dist[i][j]);

		printf("\n");
	}

	printf("\n");


    return 0;
}

0x01AA

Жаль, что вы не добавили комментарии к коду. В любом случае, большое желание помочь!

Arthur V. Ratz

Я просто немного занят прямо сейчас, вот почему я не написал и не добавил комментарии к своему коду. Извините, я собираюсь добавить некоторые комментарии позже. В любом случае, спасибо за ваш комментарий. :)