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

Написать рекурсивную функцию, которая находит размер самой большой фигуры - C++

Восстановить пароль Регистрация
 
poroh
0 / 0 / 0
Регистрация: 03.12.2012
Сообщений: 10
27.03.2013, 16:18     Написать рекурсивную функцию, которая находит размер самой большой фигуры #1
В прямоугольной таблице N рядов и M колонок. Каждая клетка или пустая, или закрашенная. Каждая закрашенная клетка принадлежит одной из фигур. Если у двух закрашенных клеток есть общая сторона, они принадлежат одной фигуре. Пустые клетки фигурам не принадлежат. Площадь фигуры равна количеству принадлежащих ей клеток. В примере даны три фигуры, площади которых 3, 19 и 2.
[404]
Написать рекурсивную функцию, которая находит размер самой большой фигуры.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.03.2013, 16:18     Написать рекурсивную функцию, которая находит размер самой большой фигуры
Посмотрите здесь:

Написать рекурсивную функцию, которая находит минимальный элемент в матрице (двумерном массиве). C++
Составить рекурсивную функцию, которая находит цифровой корень целого числа C++
C++ Описать рекурсивную функцию, которая методом деления отрезка пополам находит корень уравнения
Составить рекурсивную функцию, которая находит произведение n парных положительных чисел C++
Написать функцию, которая находит площадь любой фигуры C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SummerRain
 Аватар для SummerRain
325 / 324 / 17
Регистрация: 16.12.2012
Сообщений: 544
27.03.2013, 16:39     Написать рекурсивную функцию, которая находит размер самой большой фигуры #2
Подобная задача была Задача на "закрашивание" некоторых элементов матрицы
А эта ещё легче. Просто здесь нужно узнать максимальный размер cur.size(), пройдя все "фигуры".
Смотреть 9 пост. Этот вектор объявлен в 156 строчке кода.

Добавлено через 6 минут
Ах да, у меня ещё там проверка на расположение точки на границе матрицы (функция bool isborder(const point& p)).
Его тоже можете убрать.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
27.03.2013, 17:04     Написать рекурсивную функцию, которая находит размер самой большой фигуры #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Ну или можно по-короче.
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
98
#include <iostream>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <algorithm>
 
struct Point {
  int x, y;
  Point() : x(0), y(0) {}
  Point(int x, int y) : x(x), y(y) {}
};
 
std::ostream &operator<<(std::ostream &stream, const Point &point) {
  return stream << "[" << point.x << "," << point.y << "]";
}
 
class Figure {
 public:
  Figure() : points() {}
  void addPoint(const Point &point) {
    points.push_back(point);
  }
  const std::vector<Point> &getPoints() const { return points; }
  size_t getSize() const { return points.size(); }
 private:
  std::vector<Point> points;
};
 
std::ostream &operator<<(std::ostream &stream, const Figure &figure) {
  stream << "Figure{" <<
    "size=" << figure.getSize() << ",points=";
  for (size_t i = 0; i < figure.getPoints().size(); ++i) {
    stream << figure.getPoints()[i];
  }
  return stream << "}";
}
 
bool operator<(const Figure &a, const Figure &b) {
  return a.getSize() < b.getSize();
}
 
Figure &fillFigure(Figure &figure, size_t i, size_t j, char **map,
  size_t height, size_t width) {
  if (i < height && j < width && i >= 0 && j >= 0 && map[i][j] == 1) {
    figure.addPoint(Point(j, i));
    map[i][j] = -1;
    fillFigure(figure, i + 1, j, map, height, width);
    fillFigure(figure, i, j + 1, map, height, width);
    fillFigure(figure, i - 1, j, map, height, width);
    fillFigure(figure, i, j - 1, map, height, width);
  }
  return figure;
}
 
std::vector<Figure> findAreas(char **map, size_t height,
  size_t width) {
  std::vector<Figure> figures;
  for (size_t i = 0; i < height; ++i) {
    for (size_t j = 0; j < width; ++j) {
      if (map[i][j] == 1) {
        Figure figure;
        figures.push_back(fillFigure(figure, i, j, map, height, width));
      }
    }
  }
  return figures;
};
 
int main(int argc, char *argv[]) {
  srand(time(0));
 
  int height = 6;
  int width = 9;
  char **map = new char*[height];
  for (int i = 0; i < height; ++i) map[i] = new char[width];
 
  for (int i = 0; i != height; ++i) {
    for (int j = 0; j != width; ++j) {
      std::cout << char('0' + (map[i][j] = rand() % 2));
    }
    std::cout << std::endl;
  }
 
  std::vector<Figure> figures = findAreas(map, height, width);
  
  for (size_t i = 0; i < figures.size(); ++i) {
    std::cout << figures[i] << std::endl;
  }
 
  std::cout << "Figure with maximum area is: " <<
    *std::max_element(figures.begin(), figures.end()) << std::endl;
  
  for (int i = 0; i < height; ++i) delete [] map[i];
  delete [] map;
  std::cin.get();
  return 0;
}
poroh
0 / 0 / 0
Регистрация: 03.12.2012
Сообщений: 10
29.03.2013, 16:13  [ТС]     Написать рекурсивную функцию, которая находит размер самой большой фигуры #4
Огромное спасибо!
Yandex
Объявления
29.03.2013, 16:13     Написать рекурсивную функцию, которая находит размер самой большой фигуры
Ответ Создать тему
Опции темы

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