Здравствуйте, _Dinosaur, Вы писали:
D>задачка
D>Поигрался и подумал, что, наверняка, D>можно придумать алгоритм нахождения D>последовательности перемещений блоков, D>приводящий к решению задачи. D>Есть у кого-нибудь идеи?
Прошу прощения, что поднимаю сильно утонувшую тему...
Но что-то захотелось мне таки сделать то, о чём писал автор топика.
Всё оказалось совсем не сложным. Я даже не стал пытаться ничего оптимизировать. Вот так например моя радость меньше чем за секунду нашла гарантированно кратчайший путь на восьмом уровене
А вот собственно код (его можно откомпилить). Так как это по сути моё первое поюзание STL (стыдно ужасно ) прошу сильно не пинать, но если не лень, указать на очевидные проколы.
// Gridlock.cpp : Defines the entry point for the console application.
//#include"stdafx.h"#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <stack>
//main structure and simple functions /////////////////////////#define NY 6
#define NX 6
#define EXIT_Y 2
#define EXIT_X (NX-1)
#define EXIT_DIR 0 //0 means that exit is in hor direction (1 - ver directio)const char space=' ';
const std::string cars[]= {"-=", "|#"};
struct grid
{
char board[NY][NX];
grid()
{memset(board,0,sizeof(board));}
bool operator<(const grid& g) const
{return memcmp(board,g.board,sizeof(board))<0;}
bool operator==(const grid& g) const
{return memcmp(board,g.board,sizeof(board))==0;}
grid& operator=(const grid& g)
{memcpy(board,g.board,sizeof(board)); return *this;}
};
std::istream& operator>>(std::istream& in,grid& g)
{
for(int y=0;y<NY;y++)
{
char is[80];in.getline(is,80);
memset(g.board[y],' ',NX);
memcpy(g.board[y],is,strlen(is));
}
return in;
}
#define end_of_out grid()
std::ostream& operator<<(std::ostream& out,const grid& g)
{
static std::string os[NY];
if( os[0].length()+NX+3>80 || //not enough space in line
g==end_of_out)
{
for(int y=0;y<NY;y++)
out<<os[y]<<"\n",os[y]="";
out<<"\n\n";
if(g==end_of_out)
return out;
}
for(int y=0;y<NY;y++)
os[y].append(g.board[y],NX), os[y]+=" ";
return out;
}
// main function //////////////////////////////////////////////////////bool find_path(const grid& start,std::stack<grid>& theStack)
{
std::map<grid, grid> theMap;
theMap[start]=start;//fill index with something
std::queue<grid> theQueue;
for(theQueue.push(start);!theQueue.empty();theQueue.pop())
{
grid& g=theQueue.front();
for(int y=0;y<NY;y++) //scan every squarefor(int x=0;x<NX;x++) //in rectangleif(g.board[y][x]==space) //can move car to herefor(int dir=0;dir<4;dir++)//find car to move - left-up-right-down
{
grid gg=g; //try to move car and change positionchar cur=space;
int x1=x,y1=y,x2=x,y2=y,n;
while(1)
{
dir==0? x2--:dir==1? y2--:dir==2? x2++:y2++;
if(x2<0 || y2<0 || x2>=NX || y2>=NY)
break;
if(cur==space)
{
if(gg.board[y2][x2]==space)
continue;
cur=gg.board[y2][x2];
n=cars[dir%2].find(cur);
if(n==-1)
break;
n+=2; //n=2 or n=3 - a length of the car
}
if(gg.board[y2][x2]!=cur || n--==0) //end of carbreak;
gg.board[y1][x1]=cur;
gg.board[y2][x2]=space;
dir==0? x1--:dir==1? y1--:dir==2? x1++:y1++;
}
if(!(gg==g) && theMap.find(gg)==theMap.end()) //new position
{
theMap[gg]=g; //we come to gg from g
theQueue.push(gg); //now where can we go from gg?if(dir%2==EXIT_DIR && y==EXIT_Y && x==EXIT_X) //we find path!
{
while(1)
{
theStack.push(gg);
if(gg==start)
return true;
gg=theMap[gg];
}
}
}
}
}
return false;
}
main()
{
std::cout<<"Enter a grid ("<<NY<<" lines)x("<<NX<<" columns).\n"<<
"Use simbol '-' to construct 2-square-horizontal-cars\n"
"Use simbol '=' to construct 3-square-horizontal-cars\n"
"Use simbol '|' to construct 2-square-vertical-cars\n"
"Use simbol '#' to construct 3-square-vertical-cars\n"
"Empty space means empty space.\n"
"Any other simbols means 'stones'.\n\n";
while(1)
{
grid g;
std::cin>>g;
std::cout<<"\n\n";
std::stack<grid> path;
if(find_path(g,path))
{
for(;!path.empty();path.pop())
std::cout<<path.top();
std::cout<<end_of_out;
}
else
{
std::cout<<"Fails to find path\n\n";
}
std::cout<<"Enter a grid\n\n";
}
return 0;
}
Здравствуйте, _Dinosaur, Вы писали:
D>задачка
D>Поигрался и подумал, что, наверняка, D>можно придумать алгоритм нахождения D>последовательности перемещений блоков, D>приводящий к решению задачи.
D>Есть у кого-нибудь идеи?
Придумать, как кодить позицию покомпактнее и осуществить простой волновой алгоритм.Имхо совсем не трудно, будет вполне быстро работать и главное давать гарантировано кратчайшую перестановку. Сам бы сделал, да мне ещё полимино считать
Здравствуйте, _Dinosaur, Вы писали:
D>Здравствуйте, Pushkin, Вы писали:
P>>Придумать, как кодить позицию покомпактнее и осуществить простой волновой алгоритм.Имхо совсем не трудно, будет вполне быстро работать и главное давать гарантировано кратчайшую перестановку. Сам бы сделал, да мне ещё полимино считать
D>а что из себя представляет волновой алгоритм
Запроси в Гугле "волновой алгоритм". Первые 15-20 ссылок — то что тебе нужно.
Здравствуйте, Pushkin, Вы писали:
P>Придумать, как кодить позицию покомпактнее и осуществить простой волновой алгоритм.Имхо совсем не трудно, будет вполне быстро работать и главное давать гарантировано кратчайшую перестановку. Сам бы сделал, да мне ещё полимино считать
а что из себя представляет волновой алгоритм
Завидую людям, которые могут себе позволить никуда не спешить.
Здравствуйте, Pushkin, Вы писали:
P>Здравствуйте, _Dinosaur, Вы писали:
D>>а что из себя представляет волновой алгоритм
P>Стыдно, да? P>На самом деле шут бы с ним, как он называется, но можно сделать типа заливки области
Здравствуйте, Pushkin, Вы писали:
P>Здравствуйте, _Dinosaur, Вы писали:
D>>Да, кстати, волновой алгоритм не самый D>>эффективный среди алгоритмов заливки
P>Зато волновой
ага
Блин, засел на 33 уровне, никак не могу пройти
Завидую людям, которые могут себе позволить никуда не спешить.
Здравствуйте, Pushkin, Вы писали:
P>Здравствуйте, _Dinosaur, Вы писали:
P> D>>Блин, засел на 33 уровне, никак не могу пройти
P>Вот уж точно маньяк Я поле 5-го заленился. P>Хотя забавная. Дизайн только на любителя.
Здравствуйте, _Dinosaur, Вы писали:
D>Поигрался и подумал, что, наверняка, D>можно придумать алгоритм нахождения D>последовательности перемещений блоков, D>приводящий к решению задачи.
Имхо существенно более трудная и интересная задача
написать ГЕНЕРАТОР таких позиций.
Случайная может а) не сойтись б) сойтись слишком просто
Научная работа: найти позицию, которая сойдётся за максимальное число перемещений.
Имхо сделать можно.
И будет даже лучше, чем машинки.
Н так наглядно, но можно играть в метро.
На тонкой но хорошей фанере рисуется сетка 6х6.
Вырезается из другого куска 36 квадратов чуть меньше, чем клетка, и со скруглёнными углами.
Из третьего куска вырезается ещё 36 квадратов совсем маленьких.
Клеим самые маленькие на клетки доски, а на них побольше. Получили ПОЛЕ.
Выглядит как бумага в клетку, но вместо линий щели.
Всё жёстко, один неразборный кусок дерева, но внутри хитрой формы.
Теперь машинки. Из той же фанеры прямоугольник — это верх, его можно лаком покрыть.
Прямоугольник поменьше это низ — он внутри поля ездит.
Между ними — очень узкий прямоугольний (типа карандаша) — перемычка. Всё склеивается.
В итоге машинки в щели вставляются через края доски, края закрываются заглушками,
и дальше машинки уже могут ходить только вдоль себя. Снял заглушки — сменил позицию.
Здравствуйте, Кодт, Вы писали:
D>>задачка
К>YES! Я ее уделал. Там всего 40 уровней. На 41 мне показали белый квадрат.
Да, довольно просто всё. Некоторые, конечно, заставляли задуматься, но в среднем не больше минуты на уровень получилось... Однако на 40овой я попух Сходу не получилось. Через перерыв попробую снова
А вот и баг, кстати:
В правом нижнем углу фигурки пересекаются
... << RSDN@Home 1.0 beta 6a | Сейчас пятница, 13:03, слушаю 02 — The Four Horsemen >>
Перекуём баги на фичи!
