Я пишу программу, которая должна
сортировать количество квадратных плиток (из которых
каждая сторона окрашена в один из пяти цветов - красный, оранжевый,
синий, зеленый и желтый), которые лежат рядом
(например, 8 строк и 12 столбцов) таким образом, чтобы как можно больше сторон
того же цвета подключите, насколько это возможно.
Так, например, плитка с правой стороны окрашена
красный должен иметь плитку справа, которая имеет красную левую сторону.)
Результат оценивается путем подсчета количества несовпадающих пар
сторон существуют на доске. Я почти закончил с настоящей программой;
У меня просто проблемы с алгоритмом сортировки. Щас пользуюсь
Алгоритм на основе пузырьковой сортировки, который сравнивает каждую фигуру на доске
с каждой другой частью, и если переключение этих двух уменьшает количество
несовпадающие пары сторон на доске, он их переключает. Здесь
Абстрактная версия функции сортировки, как сейчас:
for(int i = 0 ; i < DimensionOfBoard.cx * DimensionOfBoard.cy ; i++)
for(int j = 0 ; j < DimensionOfBoard.cx * DiemsionOfBoard.cy ; j++)
{
// Comparing a piece with itself is useless
if(i == j)
continue;
// v1 is the amount of the nonmatching sides of both pieces
// (max is 8, since we have 2 pieces with 4 sides each (duh))
int v1 = Board[i].GetNonmatchingSides() + Board[j].GetNonmatchingSides();
// Switching the pieces, if this decreases the value of the board
// (increases the amount of nonmatching sides) we'll switch back)
SwitchPieces(Board[i], Board[j]);
// If switching worsened the situation ...
if(v1 < Board[i].GetNonmathcingSides() + Board[j].GetNonmatchingSides())
// ... we switch back to the initial state
SwitchPieces(Board[i], Board[j]);
}
В качестве объяснения: Board - это указатель на массив Piece Object. Каждая часть имеет
четыре Piece-указатели, которые указывают на четыре смежные части (или NULL, если Piece
боковой / угловой кусок.) И переключение на самом деле не переключает сами части, но
скорее меняет цвета. (Вместо того, чтобы обменивать куски, он соскребает цвет
и того и другого.)
Этот алгоритм работает не так уж плохо, он значительно улучшает значение
доска, но она не оптимизирует ее как следует. Я предполагаю, что это потому, что сторона и угол
фигуры не могут двигаться, чем три / две неправильных смежных фигуры, так как одна / две стороны
пусты Я попытался это компенсировать (умножив Board [i] .GetMatchingPieces ()
с Board [i] .GetHowManyNonemptySides () перед сравнением), но это не помогло.
И здесь мне нужна помощь. Я не знаю очень много алгоритмов сортировки, не говоря уже о
те, которые работают с двумерными массивами. Так может кто-нибудь из вас знает о
алгоритмическая концепция, которая может помочь мне улучшить мою работу? Или кто-нибудь может увидеть
проблема, которую я еще не нашел? Любая помощь приветствуется. Спасибо.