如何将整数数组分区为“区域”？ [英] How do I partition an integer array into "districts"?

问题描述

我有一个10x10整数数组（称之为table），我有一个迭代任务，我需要在C ++中使用该数组。基本上，我需要做出所有可能的选择，将表格切成表格中的地区，其中地区是指满足表格条目的集合



1）每个区域包括10个表格条目



2）区域中的每个条目与区域中的至少一个其他条目相邻。也就是说，对于区中的每个条目a_ij，a_ij的上方，下方，右侧或左侧区域必须有另一个条目（对角线移动不算作邻接区域）。



我需要的是通过这张桌子的所有可能的划分进入地区。所以一个可能的划分是每一行是一个区，另一个可能的划分是每个列是一个区等。对于每个可能的划分我有一个计算我需要做但我知道如何做这个计算，我只是不知道如何实现将桌子划分为区域的所有可能选择的进行。算法库中有算法可以帮助我吗？或者直接从头开始编码？我很抱歉，如果这是一个微不足道的问题，我不太了解C ++，但我需要为一个单独的项目做这个。



我试过的：



我试过通过算法思考并尝试在C ++算法库中找到类似的东西。

I have a 10x10 integer array (call it "table"), and I have an iterative task I need to do in C++ with the array. Essentially, I need to make all possible choices of chopping the table into "districts" within the table, where by "district" I mean a collection of table entries that satisfies

1) each district consists of 10 entries of the table

2) each entry in a district is adjacent to at least one other entry in the district. That is, for each entry a_ij in the district there must be another entry in the district above, below, to the right of, or to the left of a_ij (diagonal movement doesn't count as adjacent).

What I need is to go through all possible divisions of this table into districts. So one possible division is each row is a district, another possible division is each column is a district, etc. For each possible division I have a computation I need to do but I know how to do this computation, I just don't know how to implement the marching through of all possible choices of dividing the table into districts. Is there an algorithm in the algorithm library that could help me? Or this straightforward to code from scratch? I apologize if this is a trivial question, I don't know much C++ but I need to do this for a separate project.

What I have tried:

I have tried thinking through the algorithm and trying to find something similar in the C++ algorithm library.

推荐答案

这是我的解决方案：

Here's my solution:

// 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;
}

这篇关于如何将整数数组分区为“区域”？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！