Модераторы: Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [C++]Игра "Лабиринт",  
:(
    Опции темы
Igor11
  Дата 27.11.2012, 21:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 27.11.2012

Репутация: нет
Всего: нет
Реализация класса «стек» в задачах поиска выхода из лабиринта.
Описать класс, реализующий стек. Написать программу, использующую этот класс для отыскания прохода по лабиринту. Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат или открытый, или закрытый. Вход в закрытый квадрат запрещен. Если квадрат открыт, то вход в него возможен со стороны, но не с угла. Каждый квадрат определяется его координатами в матрице. После отыскания прохода программа печатает найденный путь в виде координат квадратов.
PM MAIL   Вверх
bsa
Дата 27.11.2012, 21:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 1
Всего: 196

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




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


--------------------
Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.
PM   Вверх
t_gran
Дата 29.11.2012, 18:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37
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 - старт/финиш

user posted image


Присоединённый файл ( Кол-во скачиваний: 70 )
Присоединённый файл  program.zip 3,71 Kb


--------------------
Я знаю, что ничего не знаю© Сократ
user posted image
PM MAIL WWW   Вверх
Igor11
Дата 29.11.2012, 21:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 27.11.2012

Репутация: нет
Всего: нет
что именно было сделано в части pos.h?

Добавлено через 12 минут и 43 секунды
и у меня ошибка на # include "map.h", как именно мне ее исправить, ведь сам фаил map сохранен там же где и программа main
PM MAIL   Вверх
t_gran
Дата 30.11.2012, 03:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37
Цитата

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

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

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

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

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

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

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


Это сообщение отредактировал(а) t_gran - 30.11.2012, 09:07

Присоединённый файл ( Кол-во скачиваний: 33 )
Присоединённый файл  program.zip 170,22 Kb


--------------------
Я знаю, что ничего не знаю© Сократ
user posted image
PM MAIL WWW   Вверх
Igor11
  Дата 30.11.2012, 11:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 27.11.2012

Репутация: нет
Всего: нет
к сожалению я не понимаю
PM MAIL   Вверх
Igor11
  Дата 30.11.2012, 12:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 27.11.2012

Репутация: нет
Всего: нет
в Pos реализуется запоминания координат пути выхода из лабиринта ?
PM MAIL   Вверх
t_gran
Дата 30.11.2012, 18:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

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


--------------------
Я знаю, что ничего не знаю© Сократ
user posted image
PM MAIL WWW   Вверх
Igor11
  Дата 2.12.2012, 01:12 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 27.11.2012

Репутация: нет
Всего: нет
извини что надоидаю , но Вы могли бы сделать программу одним кодом, от меня требуют именно этого, а сам объединить я не могу, то что возникает проблема с кодом касается введения и считывания карты.  smile 
PM MAIL   Вверх
t_gran
Дата 3.12.2012, 04:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37
Код

#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;
}


Присоединённый файл ( Кол-во скачиваний: 55 )
Присоединённый файл  program.zip 168,76 Kb


--------------------
Я знаю, что ничего не знаю© Сократ
user posted image
PM MAIL WWW   Вверх
Igor11
Дата 3.12.2012, 12:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 27.11.2012

Репутация: нет
Всего: нет
// TStack<T>::TNode* node = stack.stack;
 у мене тут помилка із  'node' undeclared (firs use this function)
PM MAIL   Вверх
Igor11
Дата 3.12.2012, 12:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 27.11.2012

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

Добавлено через 14 минут и 45 секунд
я исправил, и консоль появляется на больше времени но ответа никакого не дает
PM MAIL   Вверх
Igor11
Дата 3.12.2012, 12:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 27.11.2012

Репутация: нет
Всего: нет
user posted image

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

Добавлено через 2 минуты и 29 секунд
она не подключает карту и соответственно не считывает ее
PM MAIL   Вверх
Igor11
Дата 3.12.2012, 13:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 27.11.2012

Репутация: нет
Всего: нет
що відбувається тут typedef std::vector<std::vector<TSector> > TMap;
PM MAIL   Вверх
t_gran
Дата 3.12.2012, 14:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37
Блин, тяжёлый случай. Я ПАС!!! smile 


--------------------
Я знаю, что ничего не знаю© Сократ
user posted image
PM MAIL WWW   Вверх
Igor11
  Дата 3.12.2012, 14:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 27.11.2012

Репутация: нет
Всего: нет
а возможно использование карты не в виде файла, а сразу вписать в исходный код?

Добавлено @ 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;
}


Это сообщение отредактировал(а) Igor11 - 3.12.2012, 15:15
PM MAIL   Вверх
Страницы: (2) [Все] 1 2 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0691 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.