Re: Код авторешалки
От: Pushkin Россия www.linkbit.com
Дата: 24.03.03 08:38
Оценка: 102 (6)
Здравствуйте, _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;
}
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.