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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Адрес объекта, адрес указателя. Где что находится? http://www.cyberforum.ru/cpp-beginners/thread826862.html
#include <iostream> void Foo(int* val) { std::cout << val << " " << *val << " " << &val << '\n'; } void Bar(int* &val) { std::cout << val << " " << *val << " " << &val << '\n';
C++ Задача на подсчет и вычисление в одномерном массиве с++ Ребята помогите с заданием по с++: "Подсчитать количество простых чисел в одномерном массиве, которые больше своих соседних элементов справа и слева. В этом же массиве найти сумму таких элементов,... http://www.cyberforum.ru/cpp-beginners/thread826859.html
вместо цикла рекурсию сделать C++
#include "stdafx.h" #include <iostream> #include "locale.h" #include "conio.h" #include <vector> #include <string> #include <algorithm> #include <iterator> #include <functional>...
Нужно исправит код C++
Использование функций, получающих и возвращающих более одного значения. Даны вещественные массивы A, B. Для каждого массива определить среднее арифметическое отрицательных элементов, среднее...
C++ Как обращаться к Union http://www.cyberforum.ru/cpp-beginners/thread826823.html
Создал указатель на структуру Person в 19 строчке. Как обратиться к полю Union'a? Некорректное обращение к union в 30, 34, 38, 49, 56, 63. Помогите как правильно, заранее спасибо? #include...
C++ Что передать функции? Как из отдельной функции присвоить значение члену класса определённого обьекта? Например: // file это класс; f - обьекты; fname - переменная которой надо присвоить значение int _tmain(int argc,... подробнее

Показать сообщение отдельно
fjay69
85 / 85 / 1
Регистрация: 26.10.2012
Сообщений: 248
03.04.2013, 16:07
Алгоритм такой. Есть вектор, содержащий ячейки нужной нам комнаты. Есть указатель на элемент вектора, который был проверен (что это значит - читайте дальше). Первый элемент - ячейка, координаты которой мы указали при вводе. Далее проверяем ячейки, окружающие текущую. Если ячейка равна '.' и при этом её нет в векторе, добавляем эту ячейку в вектор. После того, как все 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
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru