Заполнение матрицы определенным шаблоном
Итак, у меня есть матрица с одинаковыми размерами, которая определяется следующим образом:
public void InitPositionsGrid()
{
int munberOfRows = 6;
for(int i = 0; i < munberOfRows; i++)
{
if ( i % 2 == 0)
{
GridPositions[i] = new int[15];
}
else
{
GridPositions[i] = new int[14];
}
}
}
Теперь мне нужен метод (рекурсивный или итеративный - что угодно), который будет заполнять эту матрицу, но с определенным шаблоном, чтобы она была равномерной во всех направлениях. Предполагается, что метод принимает 3 параметра, X и Y, которые определяют начальную позицию, и еще один, количество мест, которые необходимо заполнить. Должно выглядеть примерно так:
public void FillGridMatrix(int startingRow, int startingColumn, int numberOfPlacesToFill)
{
//Fill the matrix with the following algorithm but don't go out of bounds
}
Вот картинка, показывающая пример алгоритма:
Идея такова: начните с текущего начального места, отметьте два пробела «выше» (должны быть x-1, y-1 и x-1, y), проверьте два смежных пробела (x, y-1 и x, y + 1) и, наконец, отметьте два пробела «снизу» (x + 1, y-1 и x + 1, y). Координаты могут быть не совсем такими, но это общая идея. Обратите внимание: когда больше нет места «вверху» или «внизу», места для заполнения должны быть одинаково слева и справа. Начальный ряд никогда не может быть ни первым, ни последним. Если место, которое в настоящее время проверяется, уже отмечено, пропустите это место. Максимальное количество мест для заполнения может быть 87, как и максимальное количество элементов в самой матрице. После первого раунда, если необходимо заполнить более 7 мест, алгоритм начинается с верхнего левого угла и заканчивается нижним правым «соседним» элементом из начальной позиции (2 и 7 в этом примере).
Есть идеи, какое лучшее решение для этого? C# предпочтительнее.
Обновлено: вот решение, которое наиболее близко похоже на то, что я пытаюсь достичь, единственная проблема заключается в том, что это не подходит для рекурсии и требует слишком много условий для итеративного решения.
public int PopulateMatrixAroundCertainPosition(int[][] matrix, int row, int column, int availableNumbers)
{
if (availableNumbers <= 0)
{
return 0;
}
matrix[row][column] = 1;
availableNumbers = PopulateSingleMatrixPosition(matrix, row - 1, column - 1, availableNumbers - 1);
availableNumbers = PopulateSingleMatrixPosition(matrix, row - 1, column, availableNumbers - 1);
availableNumbers = PopulateSingleMatrixPosition(matrix, row, column - 1, availableNumbers - 1);
availableNumbers = PopulateSingleMatrixPosition(matrix, row, column + 1, availableNumbers - 1);
availableNumbers = PopulateSingleMatrixPosition(matrix, row + 1, column - 1, availableNumbers - 1);
availableNumbers = PopulateSingleMatrixPosition(matrix, row + 1, column, availableNumbers - 1);
return availableNumbers - 1;
}
public int PopulateSingleMatrixPosition(int[][] matrix, int row, int column, int availableNumbers)
{
if (availableNumbers <= 0)
{
return 0;
}
if (matrix[row][column] == 1)
{
return availableNumbers + 1;
}
matrix[row][column] = 1;
return availableNumbers;
}
Ответы 1
Никакой рекурсии не требуется. Просто продолжайте строить внутреннюю структуру. Я создал небольшой конечный автомат для решения головоломки:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
const int TOTAL_BUTTONS = 61;
const int BUTTON_SIZE = 40;
const int SPACE = 10;
public Form1()
{
InitializeComponent();
BuildMatrix();
}
public enum LOCATION
{
TOP_ROW,
LEFT_BUTTON,
RIGHT_BUTTON,
BOTTOM_ROW
}
List<List<Button>> matrix = new List<List<Button>>();
int numberButtons = 0;
public void BuildMatrix()
{
int centerX = 0;
int centerY = 0;
int loopCounter = 1; //count of number of loops around matrix
int numberRows = 0;
int rowCount = 0;
int columnCount = 0;
centerX = this.Width / 2;
centerY = this.Height / 2;
LOCATION location = LOCATION.TOP_ROW;
List<Button> newRow = new List<Button>();
Button newButton = null;
Button buttonLeft = null;
for (int buttonCount = 0; buttonCount < TOTAL_BUTTONS; buttonCount++)
{
switch (location)
{
case LOCATION.TOP_ROW :
if (columnCount == 0)
{
newRow = new List<Button>();
if (numberRows++ == 0)
{
matrix.Add(newRow);
newButton = AddButton(centerY - (BUTTON_SIZE / 2), centerX - (BUTTON_SIZE / 2));
//add first button
newRow.Add(newButton);
loopCounter++;
continue;
}
else
{
matrix.Insert(0, newRow);
Button buttonDownRight = matrix[1][columnCount];
newButton = AddButton(buttonDownRight.Top - SPACE - BUTTON_SIZE, buttonDownRight.Left - ((SPACE + BUTTON_SIZE) / 2));
}
}
else
{
buttonLeft = matrix[rowCount][columnCount - 1];
newButton = AddButton(buttonLeft.Top, buttonLeft.Left + SPACE + BUTTON_SIZE);
}
//put new button above button below, move up one row, move left half column
newRow.Add(newButton);
if (++columnCount == loopCounter)
{
location = LOCATION.LEFT_BUTTON;
rowCount++;
}
break;
case LOCATION.LEFT_BUTTON :
Button buttonRight = matrix[rowCount][0];
newButton = AddButton(buttonRight.Top, buttonRight.Left - SPACE - BUTTON_SIZE);
matrix[rowCount].Insert(0, newButton);
location = LOCATION.RIGHT_BUTTON;
break;
case LOCATION.RIGHT_BUTTON :
buttonLeft = matrix[rowCount][matrix[rowCount].Count - 1];
newButton = AddButton(buttonLeft.Top, buttonLeft.Left + SPACE + BUTTON_SIZE);
matrix[rowCount].Add(newButton);
rowCount++;
if (rowCount >= numberRows)
{
location = LOCATION.BOTTOM_ROW;
}
else
{
location = LOCATION.LEFT_BUTTON;
}
columnCount = 0;
break;
case LOCATION.BOTTOM_ROW :
if (columnCount == 0)
{
newRow = new List<Button>();
matrix.Add(newRow);
numberRows++;
}
Button buttonTopLeft = matrix[rowCount - 1][columnCount];
newButton = AddButton(buttonTopLeft.Top + SPACE + BUTTON_SIZE, buttonTopLeft.Left + ((SPACE + BUTTON_SIZE) / 2));
matrix[rowCount].Add(newButton);
if (++columnCount == loopCounter)
{
location = LOCATION.TOP_ROW;
columnCount = 0;
rowCount = 0;
loopCounter++;
}
break;
}
}
}
public Button AddButton(int top, int left)
{
Button newButton = new Button();
newButton.Width = BUTTON_SIZE;
newButton.Height = BUTTON_SIZE;
newButton.Top = top ;
newButton.Left = left;
numberButtons++;
newButton.Text = numberButtons.ToString();
this.Controls.Add(newButton);
return newButton;
}
}
}
Попытайтесь решить эту проблему и задайте конкретный вопрос. Кажется, вы понимаете логику в том виде, в котором вы ее написали, поэтому попробуйте преобразовать ее в код. В противном случае кажется, что вы просите сообщество написать за вас ваш код, а SO не в этом.