Авторизация

Логин: Пароль:
Регистрация Забыли свой пароль?

Как найти площадь и периметр

Страницы: 1
Как найти площадь и периметр
#1
06.11.2010 11:55:54
На бумагу начертили замкнутою ломаную без самопересечений, идущую по сторонам клеток. В результате получили некоторую фигуру, стороны которой являются сторонами клеток.
Ваша задача найти периметр и площадь данной фигуры, а также кол-во незакрашеных сторон клеток, лежащих внутри данной фигуры.


По какому алгоритму действовать? через координаты всех точек? Идеи??
Рисунок
Изменено: mihail filatov - 07.11.2010 21:30:33
 
 
#2
06.11.2010 15:14:00
Ну периметр в данном случае - это просто число команд.
 
 
#3
06.11.2010 16:53:59
Используй обход вширь. Переместиться в соседнюю клетку можно, если смежная сторона не закрашена. Число клеток, до которых смогли добраться - площадь.
 
 
#4
07.11.2010 01:31:54
Ну периметр я сам нашел, а вот площадь... Фигура разная может быть. И про клетку подробней
 
 
#5
07.11.2010 17:48:36
Тебе надо почитать про алгоритмы на графах. Здесь применяется алгоритм обхода вширину.
Начинаем из любой клетки внутри фигуры. На каждом шаге помечаем все соседние клетки, до которых можно добраться за один ход. На следующем шаге делаем тоже самое для всех клеток, до которых мы добрались на предыдущем шаге. В конце концов мы доберёмся до всех клеток внутри фигуры. Число помеченных клеток и будет площадь.
 
 
#6
07.11.2010 21:31:43
Дай пример кода, по координатом все делать? С примером понятней.
 
 
 
Страницы: 1
Читают тему (гостей: 1, пользователей: 0, из них скрытых: 0)