Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Kasl
1 / 1 / 0
Регистрация: 20.02.2013
Сообщений: 7
03.04.2013, 14:33     Область комнаты (рекурсия) #1
Здраствуйте. помогите решить задачу
площадь комнаты
Ваша задача написать программу, которая найдет площадь комнаты в данном квадратный лабиринт


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

пример
Миниатюры
Область комнаты (рекурсия)  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2013, 14:33     Область комнаты (рекурсия)
Посмотрите здесь:

Рекурсия C++
Рекурсия C++
Рекурсия C++
Расчет обоев для комнаты C++
C++ Рекурсия
Рекурсия C++
C++ Рекурсия, вычислить площадь комнаты в квадратном лабиринте
рекурсия C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fjay69
 Аватар для 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.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
03.04.2013, 17:58     Область комнаты (рекурсия) #3
вы понимаете, что у вашего решения, грубо говоря, экспоненциальная сложность...?) вообще такие задачи решаются с помощью dfs с линейной сложностью.
Yandex
Объявления
03.04.2013, 17:58     Область комнаты (рекурсия)
Ответ Создать тему
Опции темы

Текущее время: 16:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru