вот реализация поиска пути в глубину от H.Вирта. можно посмотреть в консольном режиме.
cуть происходящего):
есть лабиринт, в котором "1" обозначает проход, а "0" - стену.
1110110001111
1011101111101
1000101010101
1000111010111
1111100001000
0000100000000
0000111111111
Для того, чтобы найти путь из точки А (0,0) в точку Б (6, 12), пользуясь данным методом поиска, мы должны выбрать некую следующую позицию. В нашем варианте мы будем выбирать любую соседнюю ячейку (исключая ячейки по диагонали) в порядке по часовой стрелке: 1 - строкой выше, 2 - колонкой правее, 3 - строкой ниже, 4 - колонкой левее. Если новая позиция находится на пути к конечной точке - переходим на нее, если нет - выбираем другую позицию. При этом путь ведущий к цели будет помечаться "9", а путь ведущий в тупик - "2".
Вот как будет выглядеть поиск пути в глубину из точки А в точку Б:
9990220002222
1099902222202
1000902020202
1000922020222
1111900001000
0000900000000
0000999999999
Оказавшись в тупике, мы возвращаемся до тех пор, пока не оказываемся в позиции, из которой возможно сделать другой ход и вновь пытаемся достичь конечную точку.
//Position.h
//объявление класса Position
#ifndef POSITION
#define POSITION
class Position
{
private:
int row;
int column;
public:
Position();
Position(int row, int column);
void setPosition(int row, int column);
int getRow();
int getColumn();
};
#endif
//Position.cpp
//методы класса Position
#include "Position.h"
Position::Position()
{
row=0;
column=0;
}
Position::Position(int row, int column)
{
this->row=row;
this->column=column;
}
void Position::setPosition(int row, int column)
{
this->row=row;
this->column=column;
}
int Position::getRow()
{
return this->row;
}
int Position::getColumn()
{
return this->column;
}
//Application.h
//
#ifndef APPLICATION
#define APPLICATION
#include <iostream>
#include "Position.h"
using namespace std;
class Application
{
friend ostream& operator << (ostream& stream,
Application& app);
public:
Position generateInitialState();//генерирует начальное состояние - ввод начальных и конечных точек
bool valid (Position& pos);//проверка корректности ввода
void record (Position& pos);//отмечает пройденный путь как "9"
bool done (Position& pos);//проверка текущей и конечной точек на совпадение
void undo (Position& pos););//отмечает пройденный путь как "2"
class Iterator
{
public:
Iterator();
Iterator (Position& pos);
Position operator++ (int);
bool atEnd();
protected:
void* fieldPtr;
};
};
#endif
//BackTrack.h
//
#ifndef BACKTRACK
#define BACKTRACK
#include "Application.h";
#include "Position.h"
class BackTrack
{
public:
BackTrack (const Application& app);
bool tryToSolve (Position pos);//рекурсивная функция - попытка найти путь через выбранную позицию
protected:
Application app;
};
#endif
//BackTrack.cpp
//
#include "BackTrack.h"
using namespace std;
BackTrack::BackTrack (const Application& app)
{
this->app=app;
}
bool BackTrack::tryToSolve (Position pos)
{
bool success = false;
Application::Iterator itr(pos);
while(!success && !itr.atEnd())
{
pos=itr++;
if(!app.valid(pos))
{
app.record(pos);
if(app.done(pos))
success=true;
else
{
success = this->tryToSolve(pos);
if(!success)
app.undo(pos);
}
}
}
return success;
}
//Maze.cpp
//реализация методов класса Аpplication и установка значений лабиринта
#include <iostream>
#include <string>
#include "Application.h"
const short WALL=0;
const short CORRIDOR=1;
const short PATCH=9;
const short TRIED=2;
const short ROWS=7;
const short COLUMNS=13;
short grid [ROWS][COLUMNS] =
{
{1,1,1,0,1,1,0,0,0,1,1,1,1},
{1,0,1,1,1,0,1,1,1,1,1,0,1},
{1,0,0,0,1,0,1,0,1,0,1,0,1},
{1,0,0,0,1,1,1,0,1,0,1,1,1},
{1,1,1,1,1,0,0,0,0,1,0,0,0},
{0,0,0,0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,1,1,1,1,1,1,1,1,1},
};
Position start, finish;
using namespace std;
Position Application::generateInitialState()
{
const string START_PROMT = "Введите начальные строку и колонку:";
const string FINISH_PROMT = "Введите конечные строку и колонку:";
int row, column;
cout << START_PROMT;
cin>>row>>column;
start.setPosition(row,column);
cout << FINISH_PROMT;
cin>>row>>column;
cin.get();
finish.setPosition(row,column);
return start;
}
bool Application::valid(Position& pos)
{
if(pos.getRow()>=0 && pos.getRow()<ROWS &&
pos.getColumn()>=0 && pos.getColumn() < COLUMNS &&
grid [pos.getRow()][pos.getColumn()] == CORRIDOR)
return false;
else
return true;
}
void Application::record(Position& pos)
{
grid[pos.getRow()][pos.getColumn()]=PATCH;
}
bool Application::done(Position& pos)
{
if(pos.getRow()==finish.getRow()&&
pos.getColumn()==finish.getColumn())
return true;
else
return false;
}
void Application::undo(Position& pos)
{
grid [pos.getRow()][pos.getColumn()]=TRIED;
}
ostream& operator<< (ostream& stream, Application& app)
{
cout<<endl;//
for(int row=0; row<ROWS; row++)//
{
for(int column=0; column<COLUMNS; column++)//
cout<<grid[row][column]<<' ';//
cout<<endl;//
}
return stream;
}
struct itrFields
{
int row,
column,
direction;
};
Application::Iterator::Iterator(Position& pos)
{
itrFields* itrPtr = new itrFields;//
itrPtr->row=pos.getRow();//
itrPtr->column=pos.getColumn();//
itrPtr->direction=0;//
fieldPtr=itrPtr;
}
Position Application::Iterator::operator ++ (int)
{
itrFields* itrPtr = (itrFields*) fieldPtr;
int nextRow=itrPtr->row,//
nextColumn=itrPtr->column;
switch(itrPtr->direction++)//
{
case 0: nextRow=itrPtr->row-1;//
break;
case 1: nextColumn=itrPtr->column+1;//
break;
case 2: nextRow=itrPtr->row+1;//
break;
case 3: nextColumn=itrPtr->column-1;//
break;
}
Position next(nextRow, nextColumn);
return next;
}
bool Application::Iterator::atEnd()
{
return ((itrFields*)fieldPtr)->direction>=4;//
}
//BackTrackMain.cpp
//функция main
#include <iostream>
#include <string>
#include "BackTrack.h"
#include "Application.h"
#include "Position.h"
using namespace std;
int main()
{
const string INITIAL_STATE = "Начальное состояние: \n";
const string SUCCESS = "\n\n Решение найдено:";
const string FAILURE = "\n\n Решения нет";
const string CLOSE_WINDOW_PROMT = "Нажмите Enter, чтобы закрыть окно";
Application app;
BackTrack b(app);
cout<<INITIAL_STATE;//
Position start = app.generateInitialState();
cout<<app;//ввод начальных значений//
if(app.valid(start))//проверка на корректность ввода
cout<<FAILURE<<endl;//
else
{
app.record(start);//помечаем пройденные ячейки как "9"
if(app.done(start) || b.tryToSolve(start))
cout<<SUCCESS<<endl<<app;//
else
{
app.undo(start);
cout<<FAILURE<<endl;//
}
}
cout<<endl<<endl<<CLOSE_WINDOW_PROMT;//
cin.get();
return 0;
}