Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [C++]Игра "Лабиринт",


Автор: Igor11 27.11.2012, 21:12
Реализация класса «стек» в задачах поиска выхода из лабиринта.
Описать класс, реализующий стек. Написать программу, использующую этот класс для отыскания прохода по лабиринту. Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат или открытый, или закрытый. Вход в закрытый квадрат запрещен. Если квадрат открыт, то вход в него возможен со стороны, но не с угла. Каждый квадрат определяется его координатами в матрице. После отыскания прохода программа печатает найденный путь в виде координат квадратов.

Автор: bsa 27.11.2012, 21:40

M
bsa		Для домашних заданий, курсовых и т.п. существует \"Центр Помощи\".




Тема перенесена. 

Автор: t_gran 29.11.2012, 18:45
stack.h
Код

#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED

#include <iostream>
#include <stdexcept>

template <class T>
class TStack
{
   private:
      struct TNode
      {
         T data;
         TNode* next;
      }* stack;

   public:
      TStack() : stack(NULL)
      {
         ;
      }

      ~TStack()
      {
         MakeNull();
      }

      TStack& Push(T data)
      {
         TNode* node = new TNode;
         node->data = data;
         node->next = stack;

         stack = node;

         return *this;
      }

      T& Top() throw(std::range_error)
      {
         if (stack == NULL)
         {
            throw std::range_error("stack is empty");
         }
         return stack->data;
      }

      TStack& Pop() throw(std::range_error)
      {
         if (stack == NULL)
         {
            throw std::range_error("stack is empty");
         }

         TNode* node = stack;
         stack = stack->next;

         delete node;

         return *this;
      }

      bool IsEmpty() const
      {
         return (stack == NULL);
      }

      void MakeNull()
      {
         while (!IsEmpty())
         {
            Pop();
         }
      }

      friend std::ostream& operator << (std::ostream& os, const TStack<T>& stack)
      {
         TNode* node = stack.stack;

         while (node != NULL)
         {
            os << node->data << " ";
            node = node->next;
         }

         return os;
      }
};

#endif // STACK_H_INCLUDED

pos.h
Код

#ifndef POS_H_INCLUDED
#define POS_H_INCLUDED

#include <iostream>

struct TPos
{
   int col, row;

   TPos(): col(-1), row(-1)
   {
      ;
   }

   TPos(int theCol, int theRow): col(theCol), row(theRow)
   {
      ;
   }

   void Set(int theCol, int theRow)
   {
      col = theCol;
      row = theRow;
   }

   friend std::ostream& operator << (std::ostream& os, const TPos& pos)
   {
      //os << "[" << pos.col << ", " << pos.row << "]";
      os << "[" << pos.col+1 << "," << pos.row+1 << "]";

      return os;
   }
};

#endif // POS_H_INCLUDED

map.h
Код

#ifndef MAP_H_INCLUDED
#define MAP_H_INCLUDED

#include <vector>
#include <stdexcept>

#include "pos.h"

struct TSector
{
   enum
   {
      TYPE_SPACE = ' ',
      TYPE_WALL  = '#',
      TYPE_START = '1',
      TYPE_FINSH = '2'
   };

   char type;
   bool use;

   TSector(char theType, bool theUse = false) : type(theType), use(theUse)
   {
      ;
   }
};

typedef std::vector<std::vector<TSector>> TMap;

TPos LoadMap(const char* filename, TMap& map) throw(std::runtime_error);
void PrintMap(const TMap& map);

#endif // MAP_H_INCLUDED

map.cpp
Код

#include "map.h"

#include <iostream>
#include <fstream>
#include <string>

//----------------------------------------------//
TPos LoadMap(const char* filename, TMap& map) throw(std::runtime_error)
{
   std::ifstream file(filename);

   if (file.is_open() == false)
   {
      throw std::runtime_error("file not opened");
   }

   TPos start;
   unsigned j = 0;

   std::string line;

   while (getline(file, line))
   {
      std::vector<TSector> ln;

      for (unsigned i = 0; i < line.size(); ++i)
      {
         ln.push_back(TSector(line[i], line[i] == TSector::TYPE_WALL));

         if (line[i] == TSector::TYPE_START)
         {
            start.Set(i, j);
         }
      }
      j++;
      map.push_back(ln);
   }

   if ((start.col == -1) && (start.row == -1))
   {
      throw std::runtime_error("start position not set");
   }

   return start;
}
//----------------------------------------------//
void PrintMap(const TMap& map)
{
   for (auto ln : map)
   {
      for (auto ch : ln)
      {
         std::cout << ch.type;
      }
      std::cout << std::endl;
   }
}
//----------------------------------------------//

main.cpp
Код

#include <iostream>
#include <string>

#include "stack.h"
#include "pos.h"
#include "map.h"

//----------------------------------------------//
bool IsUse(TMap& map, int col, int row)
{
   bool isUse = true;
   try
   {
      isUse = map.at(row).at(col).use;
   }
   catch (...)
   {
      ;
   }

   return isUse;
}
//----------------------------------------------//
bool GetWay(TMap& map, TStack<TPos>& stack);

bool DeepTo(TMap& map, TStack<TPos>& stack, int col, int row)
{
   if (IsUse(map, col, row) == false)
   {
      stack.Push(TPos(col, row));
      if (GetWay(map, stack))
      {
         return true;
      }
   }

   return false;
}
//----------------------------------------------//
bool GetWay(TMap& map, TStack<TPos>& stack)
{
   int col = stack.Top().col;
   int row = stack.Top().row;

   map[row][col].use = true;

   if (map[row][col].type == TSector::TYPE_FINSH)
   {
      return true;
   }

   if (DeepTo(map, stack, col+1, row))
   {
      return true;
   }

   if (DeepTo(map, stack, col, row+1))
   {
      return true;
   }

   if (DeepTo(map, stack, col-1, row))
   {
      return true;
   }

   if (DeepTo(map, stack, col, row-1))
   {
      return true;
   }

   stack.Pop();

   return false;
}
//----------------------------------------------//

int main(int argc, const char* argv[])
{
   if (argc != 2)
   {
      std::cout << "Usage: program <MAP>";
      return 0;
   }

   TPos start;
   TMap map;

   try
   {
      start = LoadMap(argv[1], map);
   }
   catch (std::runtime_error& error)
   {
      std::cerr << "Error: " << error.what() << std::endl;
      return 1;
   }

   PrintMap(map);

   TStack<TPos> way;
   way.Push(start);

   GetWay(map, way);

   if (way.IsEmpty())
   {
      std::cerr << "Error: way not found" << std::endl;
   }
   else
   {
      std::cout << way << std::endl;
   }

   return 0;
}

Makefile
Код

CXX = g++
CXXFLAGS = -O2 -Wall --std=gnu++11
LDFLAGS = -s
OBJS = main.o map.o
TARGET = program

$(TARGET):    $(OBJS)
        $(CXX) $(LDFLAGS) -o $(TARGET) $(OBJS) $(LIBS)

all:    $(TARGET)

clean:
        rm $(OBJS) $(TARGET)

Пример карты 002.map
Код

##########################
1   #    #   #           #
### # ## # # # #### #### #
#   # #  #     #       # #
# ### ###### ###### ## # #
# #        #    ###  # ###
# # ###### # #### ## # # #
# #   #    # #       # # #
# ### # #### # ### ### # #
#     #      #  #    #   2
##########################

где, # - стена, 1/2 - старт/финиш

http://s1.ipicture.ru/

Автор: Igor11 29.11.2012, 21:54
что именно было сделано в части pos.h?

Добавлено через 12 минут и 43 секунды
и у меня ошибка на # include "map.h", как именно мне ее исправить, ведь сам фаил map сохранен там же где и программа main

Автор: t_gran 30.11.2012, 03:07
Цитата

что именно было сделано в части pos.h?

А вы не видите? Или не понимаете?
Цитата

и у меня ошибка на # include "map.h", как именно мне ее исправить, ведь сам файл map сохранен там же где и программа main 

Тут телепатов нет. Что за ошибка? Смею предположить, что вполне возможно ругается на 18-ую строчку:
Код

typedef std::vector<std::vector<TSector>> TMap;

Если так, то у вас просто компилятор не поддерживает C++11 стандарт.

P.S.: Пересобрал под винду и без использования C++11.

Автор: Igor11 30.11.2012, 11:45
к сожалению я не понимаю

Автор: Igor11 30.11.2012, 12:57
в Pos реализуется запоминания координат пути выхода из лабиринта ?

Автор: t_gran 30.11.2012, 18:51
Igor11, это же просто. В стеке вам нужно хранить 2-а значения: номер столбца и номер строки. Что это за абстракция? Правильно, координата или позиция. Вот структура TPos и реализует её. Хотя, по честности, можно было обойтись стандартным stl-овским шаблоном std::pair. Но думал для прозрачности описать свою структуру. Как практика показала - зря.

Автор: Igor11 2.12.2012, 01:12
извини что надоидаю , но Вы могли бы сделать программу одним кодом, от меня требуют именно этого, а сам объединить я не могу, то что возникает проблема с кодом касается введения и считывания карты.  smile 

Автор: t_gran 3.12.2012, 04:02
Код

#include <iostream>
#include <fstream>
#include <string>
#include <stdexcept>
#include <vector>

//----------------------------------------------//
template <class T>
class TStack
{
   private:
      struct TNode
      {
         T data;
         TNode* next;
      }* stack;

   public:
      TStack() : stack(NULL)
      {
         ;
      }

      ~TStack()
      {
         MakeNull();
      }

      TStack& Push(T data)
      {
         TNode* node = new TNode;
         node->data = data;
         node->next = stack;

         stack = node;

         return *this;
      }

      T& Top() throw(std::range_error)
      {
         if (stack == NULL)
         {
            throw std::range_error("stack is empty");
         }
         return stack->data;
      }

      TStack& Pop() throw(std::range_error)
      {
         if (stack == NULL)
         {
            throw std::range_error("stack is empty");
         }

         TNode* node = stack;
         stack = stack->next;

         delete node;

         return *this;
      }

      bool IsEmpty() const
      {
         return (stack == NULL);
      }

      void MakeNull()
      {
         while (!IsEmpty())
         {
            Pop();
         }
      }

      friend std::ostream& operator << (std::ostream& os, const TStack<T>& stack)
      {
         TStack<T>::TNode* node = stack.stack;

         while (node != NULL)
         {
            os << node->data << " ";
            node = node->next;
         }

         return os;
      }
};
//----------------------------------------------//
struct TPos
{
   int col, row;

   TPos(): col(-1), row(-1)
   {
      ;
   }

   TPos(int theCol, int theRow): col(theCol), row(theRow)
   {
      ;
   }

   void Set(int theCol, int theRow)
   {
      col = theCol;
      row = theRow;
   }

   friend std::ostream& operator << (std::ostream& os, const TPos& pos)
   {
      os << "[" << pos.col+1 << "," << pos.row+1 << "]";

      return os;
   }
};
//----------------------------------------------//
struct TSector
{
   enum
   {
      TYPE_SPACE = ' ',
      TYPE_WALL  = '#',
      TYPE_START = '1',
      TYPE_FINSH = '2'
   };

   char type;
   bool use;

   TSector(char theType, bool theUse = false) : type(theType), use(theUse)
   {
      ;
   }
};

typedef std::vector<std::vector<TSector> > TMap;
//----------------------------------------------//
TPos LoadMap(const char* filename, TMap& map) throw(std::runtime_error)
{
   std::ifstream file(filename);

   if (file.is_open() == false)
   {
      throw std::runtime_error("file not opened");
   }

   TPos start;
   unsigned j = 0;

   std::string line;

   while (getline(file, line))
   {
      std::vector<TSector> ln;

      for (unsigned i = 0; i < line.size(); ++i)
      {
         ln.push_back(TSector(line[i], line[i] == TSector::TYPE_WALL));

         if (line[i] == TSector::TYPE_START)
         {
            start.Set(i, j);
         }
      }
      j++;
      map.push_back(ln);
   }

   if ((start.col == -1) && (start.row == -1))
   {
      throw std::runtime_error("start position not set");
   }

   return start;
}
//----------------------------------------------//
void PrintMap(const TMap& map)
{

   for (TMap::const_iterator ln = map.begin(); ln != map.end(); ++ln)
   {
      for (std::vector<TSector>::const_iterator ch = ln->begin(); ch != ln->end(); ++ch)
      {
         std::cout << ch->type;
      }

      std::cout << std::endl;
   }
}
//----------------------------------------------//
bool IsUse(TMap& map, int col, int row)
{
   bool isUse = true;
   try
   {
      isUse = map.at(row).at(col).use;
   }
   catch (...)
   {
      ;
   }

   return isUse;
}
//----------------------------------------------//
bool GetWay(TMap& map, TStack<TPos>& stack);

bool DeepTo(TMap& map, TStack<TPos>& stack, int col, int row)
{
   if (IsUse(map, col, row) == false)
   {
      stack.Push(TPos(col, row));
      if (GetWay(map, stack))
      {
         return true;
      }
   }

   return false;
}
//----------------------------------------------//
bool GetWay(TMap& map, TStack<TPos>& stack)
{
   int col = stack.Top().col;
   int row = stack.Top().row;

   map[row][col].use = true;

   if (map[row][col].type == TSector::TYPE_FINSH)
   {
      return true;
   }

   if (DeepTo(map, stack, col+1, row))
   {
      return true;
   }

   if (DeepTo(map, stack, col, row+1))
   {
      return true;
   }

   if (DeepTo(map, stack, col-1, row))
   {
      return true;
   }

   if (DeepTo(map, stack, col, row-1))
   {
      return true;
   }

   stack.Pop();

   return false;
}
//----------------------------------------------//

int main(int argc, const char* argv[])
{
   if (argc != 2)
   {
      std::cout << "Usage: program <MAP>";
      return 0;
   }

   TPos start;
   TMap map;

   try
   {
      start = LoadMap(argv[1], map);
   }
   catch (std::runtime_error& error)
   {
      std::cerr << "Error: " << error.what() << std::endl;
      return 1;
   }

   PrintMap(map);

   TStack<TPos> way;
   way.Push(start);

   GetWay(map, way);

   if (way.IsEmpty())
   {
      std::cerr << "Error: way not found" << std::endl;
   }
   else
   {
      std::cout << way << std::endl;
   }

   return 0;
}

Автор: Igor11 3.12.2012, 12:14
// TStack<T>::TNode* node = stack.stack;
 у мене тут помилка із  'node' undeclared (firs use this function)

Автор: Igor11 3.12.2012, 12:32
я исправил эту ошибку, но при запуске программы консоль появляется лишь на мгновение, и функция "system (" pause ")" здесь не помогает.

Добавлено через 14 минут и 45 секунд
я исправил, и консоль появляется на больше времени но ответа никакого не дает

Автор: Igor11 3.12.2012, 12:49
user posted image

Добавлено через 1 минуту и 16 секунд
http://ipicture.ru/Gallery/View/18978682.html

Добавлено через 2 минуты и 29 секунд
она не подключает карту и соответственно не считывает ее

Автор: Igor11 3.12.2012, 13:51
що відбувається тут typedef std::vector<std::vector<TSector> > TMap;

Автор: t_gran 3.12.2012, 14:04
Блин, тяжёлый случай. Я ПАС!!! smile 

Автор: Igor11 3.12.2012, 14:04
а возможно использование карты не в виде файла, а сразу вписать в исходный код?

Добавлено @ 14:11
 зачем нам нужны эти исключения?
//----------------------------------------------//
bool IsUse(TMap& map, int col, int row)
{
   bool isUse = true;
   try
   {
      isUse = map.at(row).at(col).use;
   }
   catch (...)
   {
      ;
   }

   return isUse;
}


и зачем нам следующий фрагмент кода?
//----------------------------------------------//
bool GetWay(TMap& map, TStack<TPos>& stack);

bool DeepTo(TMap& map, TStack<TPos>& stack, int col, int row)
{
   if (IsUse(map, col, row) == false)
   {
      stack.Push(TPos(col, row));
      if (GetWay(map, stack))
      {
         return true;
      }
   }

   return false;
}

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)