Здравствуйте, _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 square
for(int x=0;x<NX;x++) //in rectangle
if(g.board[y][x]==space) //can move car to here
for(int dir=0;dir<4;dir++)//find car to move - left-up-right-down
{
grid gg=g; //try to move car and change position
char 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 car
break;
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;
}