Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Kasl
1 / 1 / 0
Регистрация: 20.02.2013
Сообщений: 7
#1

Область комнаты (рекурсия) - C++

03.04.2013, 14:33. Просмотров 511. Ответов 2
Метки нет (Все метки)

Здраствуйте. помогите решить задачу
площадь комнаты
Ваша задача написать программу, которая найдет площадь комнаты в данном квадратный лабиринт


Ввод:
Первая строка содержит только одно число N (3 <= N <= 10). Число, которое описывает размер площади лабиринта.
На следующих строках мы вводим сами ('.' - Пустые ячейки, '*' - стены).
И последняя строка содержит два числа - строки и столбца ячейки в помещении те области необходимо найти. Это гарантирует, что данная ячейка пуста, и что лабиринт окружен стенами со всех сторон.
Выход:
Выход только один номер - общее количество пустых ячеек в выбранном помещении

пример
0
Миниатюры
Область комнаты (рекурсия)  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2013, 14:33
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Область комнаты (рекурсия) (C++):

Рекурсия, вычислить площадь комнаты в квадратном лабиринте - C++
Требуется вычислить площадь комнаты в квадратном лабиринте. Формат входных данных В первой строке вводится число N – размер...

Расчет обоев для комнаты - C++
Посмотрите пожалуйста, что с кодом. После того как я ввожу значения, программа не выводит значение. #include &quot;stdafx.h&quot; #include...

Подсчитать количество обоев для оклейки комнаты - C++
Есть комната. Длина 1-й стены 6 метров, длина другой 7.5 метров, высота 3.2 метра. Дверь шириной 0.8 метром, а высотой 2 метра....

Подсчитать количество обоев для оклейки комнаты - C++
Есть комната. Длина 1-й стены 6 метров, длина другой 7.5 метров, высота 3.2 метра. Дверь шириной 0.8 метром, а высотой 2 метра....

Подсчитать количество обоев для оклейки комнаты - C++
необходимо написать программку, которая будет рассчитывать какое количество рулонов потребуется и сколько метров обоев выкинется при...

Определить хватит ли линолеума чтобы застелить пол комнаты - C++
Пользователь купил линолеум, чтобы постелить его в своей комнате. Спросите ширину и длину рулона линолеума, а так же ширину и длину...

2
fjay69
85 / 85 / 1
Регистрация: 26.10.2012
Сообщений: 248
03.04.2013, 16:07 #2
Алгоритм такой. Есть вектор, содержащий ячейки нужной нам комнаты. Есть указатель на элемент вектора, который был проверен (что это значит - читайте дальше). Первый элемент - ячейка, координаты которой мы указали при вводе. Далее проверяем ячейки, окружающие текущую. Если ячейка равна '.' и при этом её нет в векторе, добавляем эту ячейку в вектор. После того, как все 8 клеток проверены, сдвигаем указатель вектора на следующий элемент и проверяем его окружающие ячейки. И так до тех пор, пока указателю будет некуда двигаться. Ответ задачи - количество элементов вектора.
Минус такого решения - многократная проверка уже проверенных ячеек. Так что простор для оптимизации имеется.

Добавлено через 1 час 20 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
 
int main(int nArg, char* pszArgs[])
{
  vector<int> roomCells;
  int mazeSize=atoi(pszArgs[1]);
  char maze[mazeSize][mazeSize];
  for (int x=0;x<mazeSize;x++)
    for (int y=0;y<mazeSize;y++)
      maze[x][y]=pszArgs[2][x+(mazeSize-1-y)*mazeSize];
  int initX=atoi(pszArgs[3])-1;
  int initY=atoi(pszArgs[4])-1;
  //первая ячейка  
  roomCells.push_back(initX);
  roomCells.push_back(initY);
  int i=0;//номер элемента вектора
  bool exists;
  
  while (i<roomCells.size())
  {
    //клетка справа
    if (maze[roomCells[i]+1][roomCells[i+1]]=='.')
    {
      for (int k=0;k<roomCells.size();k+=2)//проверяем есть ли такое координаты в векторе
      {
        if ((roomCells[i]+1==roomCells[k]) && (roomCells[i+1]==roomCells[k+1]))
        {
          exists=true;break;
        }      
      }
      if (!exists)
      {
        roomCells.push_back(roomCells[i]+1);
        roomCells.push_back(roomCells[i+1]);      
      }
      exists=false;
    }
    //клетка слева
    if (maze[roomCells[i]-1][roomCells[i+1]]=='.')
    {
      for (int k=0;k<roomCells.size();k+=2)//проверяем есть ли такое координаты в векторе
      {
        if ((roomCells[i]-1==roomCells[k]) && (roomCells[i+1]==roomCells[k+1]))
        {
          exists=true;break;
        }      
      }
      if (!exists)
      {
        roomCells.push_back(roomCells[i]-1);
        roomCells.push_back(roomCells[i+1]);      
      }
      exists=false;
    }
    //клетка сверху
    if (maze[roomCells[i]][roomCells[i+1]+1]=='.')
    {
      for (int k=0;k<roomCells.size();k+=2)//проверяем есть ли такое координаты в векторе
      {
        if ((roomCells[i]==roomCells[k]) && (roomCells[i+1]+1==roomCells[k+1]))
        {
          exists=true;break;
        }      
      }
      if (!exists)
      {
        roomCells.push_back(roomCells[i]);
        roomCells.push_back(roomCells[i+1]+1);      
      }
      exists=false;
    }
    //клетка снизу
    if (maze[roomCells[i]][roomCells[i+1]-1]=='.')
    {
      for (int k=0;k<roomCells.size();k+=2)//проверяем есть ли такое координаты в векторе
      {
        if ((roomCells[i]==roomCells[k]) && (roomCells[i+1]-1==roomCells[k+1]))
        {
          exists=true;break;
        }      
      }
      if (!exists)
      {
        roomCells.push_back(roomCells[i]);
        roomCells.push_back(roomCells[i+1]-1);      
      }
      exists=false;
    }
  i+=2;
  }
  cout<<"Room square - "<<roomCells.size()/2;
  return 0;
}
Примечание: четные элементы вектора хранят координату x, нечетные - y.
0
salam
170 / 151 / 16
Регистрация: 10.07.2012
Сообщений: 749
03.04.2013, 17:58 #3
вы понимаете, что у вашего решения, грубо говоря, экспоненциальная сложность...?) вообще такие задачи решаются с помощью dfs с линейной сложностью.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.04.2013, 17:58
Привет! Вот еще темы с ответами:

Для прямоугольной комнаты размером W x H метров нужно закупить линолеум. C++ - C++
Для прямоугольной комнаты размером W x H метров нужно закупить линолеум. В магазине линолеум продают рулонами; вам известно количество...

Какое количество ковров необходимо приобрести, чтобы максимально накрыть площадь комнаты - C++
Чебурашка решил купить ковры, чтобы застелить комнату, в которой он жил вместе с Геной. Их прямоугольная комната оказалась размерами а х b,...

Комнаты в игре - PHP
Есть некая игра. В игре есть общая комната (лобби), куда изначально заходят все игроки. Там есть список созданных игровых комнат, к...

Комнаты в помещении) - Дискретная математика
Всем привет) А подскажите-ка пожалуйста, есть ли алгоритм, который позволяет выделить из графа простые циклы? Под простыми я имею в виду...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru