Проход по лабиринту

// lab4 : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stack.h"
#include <windows.h> // для работы с выводом рисунка в консоль
#include "stdlib.h"
 
enum direct
{
    up,
    r,
    down,
    l
};
 
struct Pass
{
    int x;
    int y;
    direct dir;
};
 
const int width = 10; const int height = 10;
 
const char up_arrow = '^';
const char down_arrow = 'V';
const char left_arrow = '<';
const char right_arrow = '>';
 
 
short int labyrint[width][height] = 
    {{0,1,0,1,0,0,1,0,0,1},
     {0,0,0,0,0,1,0,0,0,1},
     {0,0,1,0,0,1,0,1,1,1},
     {0,0,0,0,1,0,0,1,0,0},
     {0,1,0,1,1,0,1,0,1,0},
     {0,1,0,1,0,0,0,0,0,1},
     {0,1,0,1,0,0,0,1,0,1},
     {0,0,0,0,0,0,0,1,0,1},
     {0,1,1,1,1,0,1,0,0,1},
     {0,1,0,0,0,0,1,0,0,1}};
 
stack <Pass, width*height> Passes;
Pass start, finish,finish2;;
 
void show(){
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    COORD position = {0, 0};
    SetConsoleCursorPosition(hConsole, position);
 
    Pass current = ::Passes[(::Passes.GetSize() - 1)];
 
    for (int j = 0; j < height; j++){
        for (int i = 0; i < width; i++){
            if (current.x == i && current.y == j){
                switch (current.dir){
                    case up: cout << up_arrow; break;
                    case down: cout << down_arrow; break;
                    case l: cout << left_arrow; break;
                    case r: cout << right_arrow; break;
                }
            } else {
                    cout << labyrint[j][i];
                }
            }
        cout << '\n';
        }
}
 
bool similar(Pass pass){
    for (int i=0; i<::Passes.GetSize(); i++){
        if (::Passes[i].x == pass.x && ::Passes[i].y == pass.y && ::Passes[i].dir == pass.dir) return true;
    }
    return false;
}
 
int step(Pass pass){
 
    Pass prev_pass;
    int size = ::Passes.GetSize();
 
    if (size > 0){
        prev_pass = ::Passes.pop();
        if (pass.x != prev_pass.x || pass.y != prev_pass.y) { ::Passes.push(prev_pass); }
    }
 
    if (similar(pass)) {
        labyrint[pass.y][pass.x] = 1;
    }
    ::Passes.push(pass);
    prev_pass = pass;
 
    show();
 
    _sleep(100);
 
    if ((pass.x == finish.x && pass.y == finish.y) || (pass.x == finish2.x && pass.y == finish2.y)) return 1;
 
    if (pass.y-1 >= 0 && labyrint[pass.y-1][pass.x] == 0 && pass.dir != down){
        pass.y--;
        pass.dir = up;
        return step(pass);
    }
    else
    if (pass.x+1 < width && labyrint[pass.y][pass.x+1] == 0 && pass.dir != l){
        pass.x++;
        pass.dir = r;
        return step(pass);
    }
    else
    if (pass.x-1 >= 0 && labyrint[pass.y][pass.x-1] == 0 && pass.dir != r){
        pass.x--;
        pass.dir = l;
        return step(pass);
    }
    else
    if (pass.y+1 < height && labyrint[pass.y+1][pass.x] == 0 && pass.dir != up){
        pass.y++;
        pass.dir = down;
        return step(pass);
    }
    else
    {
        labyrint[pass.y][pass.x] = 1;
 
        prev_pass = ::Passes.pop();
        prev_pass = ::Passes.pop();
 
        switch (pass.dir){
            case up: prev_pass.dir = down; break;
            case down: prev_pass.dir = up; break;
            case l: prev_pass.dir = r; break;
            default: prev_pass.dir = l;
        }
 
        return step(prev_pass);
 
    }
 
}
 
int main(void)
{
    start.x = 0;    start.y = 9;    start.dir = up;
    finish.x = 8;   finish.y = 1;   finish.dir = up;
        finish2.x = 4;  finish2.y = 6;  finish2.dir = up;
 
    cout << step(start);
 
    cin >> start.x;
 
    return 0;
}

#pragma once
 
class StackOverflow{};
class StackOutOfRange{};
class EmptyStack{};
 
template <class name, int size>
 
class stack
{
private:
    name stack_array[size];
    int last_element;
 
public:
    stack(void){ last_element = 0; };
    ~stack(void){};
 
    void push(name element)
    {
        if (last_element < size)
        {
            stack_array[last_element] = element;
            last_element++;
        }
        else
        {
            throw StackOverflow();
        }   
    };
 
    name pop()
    {
        if (last_element > 0){
            last_element--;
            return stack_array[last_element];
        }
        else
        {
            throw EmptyStack();
        }
    };
 
    int Capacity()
    {
        return size;
    }
 
    int GetSize()
    {
        return last_element;
    }
 
    name& operator[] (int N)
    {
        if (N < size)
        {
        return stack_array[N];
        }
        else
        {
            throw StackOutOfRange();
        }
    }
};

#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <limits>
 
template <class T>
class Stack {
 public:
  Stack() : head(0), size(0) {}
  Stack(const Stack& other) : head(0), size(0) {
    copyFrom(other);
  }
  virtual ~Stack() {
    clear();
  }
  void copyFrom(const Stack &other) {
    clear();
    Node *otherNode = other.head;
    Node *lastNode = 0;
    while (otherNode != 0) {
      Node *newNode = new Node(otherNode->value, 0);
      if (lastNode == 0)
        head = lastNode;
      else
        lastNode->next = newNode;
      lastNode = newNode;
      otherNode = otherNode->next;
      ++size;
    }
  }
  void push(const T &value) {
    head = new Node(value, head);
    ++size;
  }
  T pop() {
    if (isEmpty()) throw std::underflow_error("stack is empty");
    T result = head->value;
    Node *newHead = head->next;
    delete head;
    head = newHead;
    --size;
    return result;
  }
  const T &top() const {
    if (isEmpty()) throw std::underflow_error("stack is empty");
    return head->value;
  }
  int isEmpty() const { return head == 0; }
  int getSize() const { return size; }
  void clear() {
    while (head != 0) {
      Node *newHead = head->next;
      delete head;
      head = newHead;
    }
    size = 0;
  }
 private:
  Stack &operator=(const Stack&);
  struct Node {
    T value;
    Node *next;
    Node(const T &value, Node *next) : value(value), next(next) {}
  };
  Node *head;
  int size;
};
 
struct Point {
  int x, y;
  Point(int x, int y) : x(x), y(y) {}
  friend Point operator+(const Point &a, const Point &b) {
    return Point(a.x + b.x, a.y + b.y);
  }
};
 
std::ostream &operator<<(std::ostream &stream, const Point &p) {
  return stream << "[" << p.x << ":" << p.y << "]";
}
 
class Maze {
 public:
  Maze(int height, int width) : height(height), width(width),
    maze(createMatrix(height, width, 0)) {}
  virtual ~Maze() {
    deleteMatrix(maze, height);
  }
  void generate() {
    Stack<Point> points;
    points.push(Point(width / 2, height / 2));
    while (!points.isEmpty()) {
      Point thisPoint = points.pop();
      int rnd = rand() % 2;
      int shiftX = rnd ? ((rand() % 2) ? -1 : 1) : 0;
      int shiftY = rnd ? 0 : ((rand() % 2) ? -1 : 1);
      
      if (thisPoint.x + shiftX * 2 > -1 && thisPoint.x + shiftX * 2 < width &&
        thisPoint.y + shiftY * 2 > -1 && thisPoint.y + shiftY * 2 < height &&
        !maze[thisPoint.y + shiftY * 2][thisPoint.x + shiftX * 2]) {
        maze[thisPoint.y + shiftY][thisPoint.x + shiftX] = 1;
 
        thisPoint.x += shiftX * 2;
        thisPoint.y += shiftY * 2;
        for (int i = 0; i < 10; ++i)
          points.push(Point(thisPoint.x, thisPoint.y));
        maze[thisPoint.y][thisPoint.x] = 1;
      }
    }
    maze[0][0] = maze[height - 1][width - 1] = 1;
  }
  
  Stack<Point> getSolution() const {
    static const Point shifts[] = {Point(0, 1), Point(1, 0), Point(0, -1), Point(-1, 0)};
    int **solutionMatrix = createSolutionMatrix();
    Stack<Point> stack;
 
    if (solutionMatrix[height - 1][width - 1] < std::numeric_limits<int>::max()) {
      Point point(width - 1, height - 1);
      stack.push(point);
      do {
        int thisValue = solutionMatrix[point.y][point.x];
        for (const Point *shift = shifts; shift < shifts + 4; ++shift) {
          Point thisPoint = point + *shift;
          if (thisPoint.x > -1 && thisPoint.y > -1 &&
            thisPoint.x < width && thisPoint.y < height && 
            solutionMatrix[thisPoint.y][thisPoint.x] == thisValue - 1) {
            point = thisPoint;
            stack.push(point);
            break;
          }
        }
      } while (point.x != 0 || point.y != 0);
    }
        
    deleteMatrix(solutionMatrix, height);
    return stack;
  }
  int get(int y, int x) const { return maze[y][x]; }
  int getHeight() const { return height; }
  int getWidth() const { return width; }
 private:
  Maze(const Maze&);
  Maze &operator=(const Maze&);
  static int **createMatrix(int height, int width, int defaultValue) {
    int **maze = new int*[height];
    for (int i = 0; i < height; ++i) {
      maze[i] = new int[width];
      for (int j = 0; j < width; ++j) {
        maze[i][j] = defaultValue;
      }
    }
    return maze;
  }
  static void deleteMatrix(int **matrix, int height) {
    for (int i = 0; i < height; ++i)
      delete [] matrix[i];
    delete [] matrix;
  }
  int **createSolutionMatrix() const {
    static const Point shifts[] = {Point(0, 1), Point(1, 0), Point(0, -1), Point(-1, 0)};
    int **matrix = createMatrix(height, width, std::numeric_limits<int>::max());
    Stack<Point> stack;
    matrix[0][0] = 0;
    stack.push(Point(0, 0));
    while (!stack.isEmpty()) {
      Point point = stack.pop();
      int value = matrix[point.y][point.x];
      for (const Point *shift = shifts; shift < shifts + 4; ++shift) {
        Point thisPoint = point + *shift;
        if (thisPoint.x > -1 && thisPoint.x < width &&
          thisPoint.y > -1 && thisPoint.y < height &&
          matrix[thisPoint.y][thisPoint.x] > value + 1 &&
          maze[thisPoint.y][thisPoint.x]) {
          matrix[thisPoint.y][thisPoint.x] = value + 1;
          stack.push(thisPoint);
        }
      }
    }
    return matrix;
  };
  int height;
  int width;
  int **maze;
};
 
std::ostream &operator<<(std::ostream &stream, const Maze &maze) {
  for (int j = 0; j < maze.getWidth() + 2; ++j) stream << '#';
  stream << std::endl;
  for (int i = 0; i < maze.getHeight(); ++i) {
    stream << '#';
    for (int j = 0; j < maze.getWidth(); ++j) {
      stream << ((maze.get(i, j)) ? ' ' : '#');
    }
    stream << '#' << std::endl;
  }
  for (int j = 0; j < maze.getWidth() + 2; ++j) stream << '#';
  stream << std::endl;
  return stream;
}
 
int main(int argc, char **argv) {
  srand(time(0));
 
  // значения лучше подбирать опытным путем
  Maze maze(9, 21);
  maze.generate();
  std::cout << maze << std::endl;
  
  Stack<Point> result = maze.getSolution();
  while (!result.isEmpty()) {
    Point point = result.pop();
    std::cout << point << (result.isEmpty() ? "\n" : "->");
  }
 
  std::cin.get();
  return 0;
}