VPF::Алгоритм змейки для поля - Форум программистов

Vaz007

Дата 6.11.2009, 14:18 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 114
Регистрация: 13.5.2009
Где: Москва

Репутация: нет
Всего: нет

Всем привет!
Нужно придумать алгоритм, которому не важен размер поля.Он должен вывести все возможные прохождения доски змейкой.
Например:
У нас есть:
1 2 3
4 5 6
7 8 9
А должно получиться:
1 2 3
6 5 4
7 8 9
а также
1 2 9
4 3 8
5 6 7
то есть пронумерованы шаги на доске. Таких комбинаций будет несколько. Нужно показать все правильные.
Помогите пожалуйста.

Это сообщение отредактировал(а) Vaz007 - 6.11.2009, 15:02

UniBomb

Дата 6.11.2009, 16:48 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Награды: 1

Профиль
Группа: Завсегдатай
Сообщений: 1754
Регистрация: 24.10.2006
Где: Санкт-Петербург

Репутация: 2
Всего: 97

Цитата(Vaz007 @ 6.11.2009, 15:18

)

Он должен вывести все возможные прохождения доски змейкой

Алгоритм тут только один - перебор всех возможных вариантов, с отбрасыванием заведомо ложных вариантов (это когда есть повторы или змейка заходит в тупик).

Нужно создать цикл, количество итераций которого соответствует количеству перестановок (в данном случае 9! = 362880). В этом цикле составлять цепочки прохождений и смотреть выполняет ли такая цепочка вышеозначенные условия, если выполняет, то сохраняешь её или выводишь на экран. Алгоритм простой, но довольно долгий - время выполнения экспоненциально возрастает в зависимости от размера поля.

зы: дай угадаю - эта тема в разделе С++ потому, что тебе нужен код именно на этом языке? Этой теме самое место в "алгоритмах".

--------------------

Маэстро пошлости и непотребства

17dufa

Дата 6.11.2009, 17:39 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 324
Регистрация: 2.3.2006

Репутация: 3
Всего: 5

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

собстна вот кусок кода:

Код


struct Coord
{
int X;
int Y;
void SetInfo(int x, int y)
{
X = x;
Y = y;
}
};

int main()
{
int N = 10; //размер доски
Find(N);
}

void Find(int size)
{
bool ** visited = CreateMatrix(size,size,false); //инициализация квадратной матрицы со значениями false

std::vector<Coord> stack;
Coord c = {0,0}; //если стартовать из левого верхнего угла, если нужно все старты пересмотреть, то тут цикл будет
stack.push_back(c);
while (stack.size())
{
Coord current = *(stack.begin()+(stack.size()-1)); //знатоки STL подрихтуйте это место
visited[current.X,current.Y] = true;
Coord child;
bool isNewAvailable = AddChilds(current, stack, size);
if (!isNewAvailable)
  if (AllVisited(visited,size)) //проверка, что матрица visited состоит только из элементов равных true
     printPath(stack); // печать текущего пути, так как он представляет собой один из вариантов прохождения
                             // в stack[0] - лежит первый шаг, stack[size*size-1] - последний
visited[current.X,current.Y] = false;
stack.pop_back();
}
FreeMatrix(visited);
}

bool AddChilds(Coord current, std::vector<Coord> & stack, int size)
{
bool res = false;
if (IsValid(current.X-1,current.Y, size)) // проверяет что координаты current.X-1 и current.Y принадлежат диапазону 0..size-1
   if(!enter[current.X-1, current.Y])
   {
       res = true;
       child.SetInfo(current.X-1, current.Y);
       stack.push_back(child);
    }
//аналогичный if для движений вверх, вниз, вправо
return res;

Это сообщение отредактировал(а) 17dufa - 6.11.2009, 18:03

UniBomb

Дата 6.11.2009, 17:46 (ссылка)

(нет голосов)

Загрузка ...

Новичок

17dufa, тот же самый метод перебора smile

--------------------

Маэстро пошлости и непотребства

17dufa

Дата 6.11.2009, 18:05 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 324
Регистрация: 2.3.2006

Репутация: 3
Всего: 5

UniBomb, ясен перец это тож полный перебор. только не надо моск ломать над отсечением невозможных вариантов и генерацией всех перестановок. оно типа само и сгенерит и отсечет smile

Vaz007

Дата 7.11.2009, 14:56 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 114
Регистрация: 13.5.2009
Где: Москва

Репутация: нет
Всего: нет

Спасибо буду пробовать

Добавлено через 14 минут и 51 секунду
17dufa

Можешь пояснить про матрицу :

Код

  
bool ** visited = CreateMatrix(size,size,false); //инициализация квадратной матрицы со значениями false

17dufa

Дата 9.11.2009, 12:00 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 324
Регистрация: 2.3.2006

Репутация: 3
Всего: 5

Vaz007, вообще факир был пьян и фокус не удался.
вот это место

Код


while (stack.size())
{
Coord current = *(stack.begin()+(stack.size()-1)); //знатоки STL подрихтуйте это место
visited[current.X,current.Y] = true;
Coord child;
bool isNewAvailable = AddChilds(current, stack, size);
if (!isNewAvailable)
  if (AllVisited(visited,size)) //проверка, что матрица visited состоит только из элементов равных true
     printPath(stack); // печать текущего пути, так как он представляет собой один из вариантов прохождения
                             // в stack[0] - лежит первый шаг, stack[size*size-1] - последний
visited[current.X,current.Y] = false;
stack.pop_back();
}

неправильно smile

попытался раскрыть рекурсию в цикл и получил фигню. там вроде как нужно 2 стека, ну или все-таки рекурсию сделать.
вот с этим

Код


bool ** visited = CreateMatrix(size,size,false); //инициализация квадратной матрицы со значениями false

это нечто такое должно получится

Код


bool ** CreateMatrix(int rowCount, int columnCount, bool initialValue)
{
bool ** res = new bool*[rowCount];
for (int i = 0; i < rowCount; ++i)
{
    res[i] = new bool[columnCount];
    for (int j = 0; j < columnCount; ++j)
    {
          res[i][j] = initialValue;
    }
}
return res;
}

хотя слышал что такое создание динамического двойного массива не есть гуд, но что есть гуд не понял. и еще: этот метод вполне можно сделать шаблонным. что-то вроде template <T> T** CreateMatrix(int,int,T);

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »