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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.60
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
#1

Надо найти "острова" на квадратной матрице - C++

03.06.2009, 01:26. Просмотров 3323. Ответов 18
Метки нет (Все метки)

Собственно ниже условие и я вроде все понял, но как это сделать...
Буду очень благодарен за Вашу помощь.
Каждый элемент квадратной матрицы размерности NxN равен нулю либо единице. Найдите количество "островов", образованных единицами. Под "островом" понимается группа единиц, со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному "острову", если из одной из них можно перейти к другой, "наступая" на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2009, 01:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Надо найти "острова" на квадратной матрице (C++):

Найти номер последней по порядку строки в матрице, содержащей наибольшее количество букв "ш", "щ" - C++
Нужен код к этому условию, пожалуйста. Дана символьная матрица размера 13х18. Найти номер последней по порядку строки,содержащей...

Вывести на экран фразу "Мне n лет", учитывая что при некоторых значениях n слово "лет" надо заменить на "год" - C++
дано натуральное число n. Вывести на экран фразу "Мне n лет", учитывая что при некоторых значениях n слово "лет" надо заменить на "год" или...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно". Я так...

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс "вентилятор" содержащий в себе классы:...

18
mikutu
27 / 27 / 2
Регистрация: 29.04.2009
Сообщений: 90
03.06.2009, 07:06 #2
самое простое что пришло в голову это решение этой задачи с помощью 2 дополнительных матриц: 1-ая матрица имеет следующие состояние ячейки 0 и 1 просто дублируют значения в исходной матрице, да еще 0 значит не обрабатывать эту ячейку она не является частью острова, 2 - кадидат на матрицу у которого обработаны все соседи, 3 - кадидат на матрицу у которого обработаны не все соседи. 2-ая матрица (строкового типа) содержит для единичных элементов имя родителя (начало острова имеет родителя себя)
пример
1 0 0
1 1 1
0 0 0
2-ая матрица имеет вид
0;0 0 0
0;0 0;0 1;1
0 0 0
ну и переменной для определения состояния программы true - в поисках начала острова false - обработка острова
Обрабатываться должны все элементы исходного массива, началом острова может быть только элемент у которого значения исходной и 1-ой матрицы равны 1, а 2-ой - 0.
1-ая матрица вначале представляет собой копию исходной, а у 2-ой все элементы равны 0;
0
Evg
Эксперт CАвтор FAQ
18032 / 6264 / 427
Регистрация: 30.03.2009
Сообщений: 17,232
Записей в блоге: 28
03.06.2009, 09:56 #3
Возможно, что мой вариант чем-то совпадает с вариантом mikutu, но его объяснения я затруднился понять. Метод мой заключается в следующем. Ищем первую попавшуюся единицу и запускаем процесс, который удалит остров (содержащий данную единицу) с поля. После удаления острова увеличиваем счётчик и ищем слудующую единицу и т.д. Удалять острова можо на оргинальном массиве, а можно и сделать копию

Рекурсивная процедура удаления выглядит примерно так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[10][10]; // <--- наш массив
 
// Удаление острова, содержащего поле x, y
void
delete_island (int x, y)
{
  // Для внутреннего контроля (чтобы убедиться, что мы всё делаем правильно)
  if (a[x][y] != 1)
    abort ();
 
  // Сразу сотрём данную точку, чтобы повторно сюда не зайти и не зациклиться
  a[x][y] = 0;
 
  // Обходим четырёх соседей данной точки, учитывая границы поля
  // Предполагая, что координаты соседа x1, y1, нужно на каждого
  // соседа запутить код
  if (a[x1][y1] == 1)
    delete_island (x1, y1);
}
0
mikutu
27 / 27 / 2
Регистрация: 29.04.2009
Сообщений: 90
03.06.2009, 11:05 #4
кстати в моем прошлом сообщении закраласт небольшая ошибка вместо
2-ая матрица имеет вид
0;0 0 0
0;0 0;0 1;1
0 0 0
нужно
2-ая матрица имеет вид
0;0 0 0
0;0 1;0 1;1
0 0 0
Трой
кстати что значит найти все острова в каком виде это выводить просто количество островов, обозначить их при выводе массива (каждый остров по разному или все одинаково)
C
1
2
3
4
5
6
7
 -
|1|  0   0
         -
|1|  0  |1|
 -   -  
 0  |1   1|
     -   -
(просто что бы пробелы не убирало)
Если я понимаю, то в выше приведенной матрице 2 острова.
Вообще решение Evg вроде более просто, но его нужно реализовать и проверить на трудных примерах например таком
1 1 1 1 1
1 0 1 0 0
1 1 0 0 0
0 0 1 1 0
0 1 1 0 0
всего должно быть 2 острова
0
Evg
Эксперт CАвтор FAQ
18032 / 6264 / 427
Регистрация: 30.03.2009
Сообщений: 17,232
Записей в блоге: 28
03.06.2009, 11:59 #5
> но его нужно реализовать и проверить на трудных примерах например

Да с этим примером в теории проходит.
Главна тонкость в том, что при вычислении соседа надо соблюсти порядок. Т.е. "в цикле { вычислил соседа - проверил }", но не "в цикле { вычислил соседей }, в цикле { проверил соседей }"
0
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
04.06.2009, 14:49  [ТС] #6
Evg и mikutu Спасибо за помощь, но у меня все же не получается написать полный код программы.

кстати что значит найти все острова в каком виде это выводить просто количество островов, обозначить их при выводе массива (каждый остров по разному или все одинаково)
Хороший вопрос. Я тоже вчера о нем подучал и сегодня хотел спросить его у преподавателя, но она сегодня не пришла
0
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
07.06.2009, 05:05  [ТС] #7
up
0
Evg
Эксперт CАвтор FAQ
18032 / 6264 / 427
Регистрация: 30.03.2009
Сообщений: 17,232
Записей в блоге: 28
07.06.2009, 12:00 #8
И в чём проблема?
0
Ultrator
11 / 7 / 1
Регистрация: 28.04.2009
Сообщений: 219
07.06.2009, 15:32 #9
Скорее всего, надо просто количество островов
(т.к. "разбиение" на острова, в некоторых случаях, не будет однозначно... как это ни странно).
Вот, например:
1 1
1 1
Если начать с [0][0] получим 2 острова, если с [1][1] - тоже 2, но уже - других!
0
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
07.06.2009, 15:42 #10
Цитата Сообщение от Ultrator Посмотреть сообщение
Скорее всего, надо просто количество островов
(т.к. "разбиение" на острова, в некоторых случаях, не будет однозначно... как это ни странно).
Вот, например:
1 1
1 1
Если начать с [0][0] получим 2 острова, если с [1][1] - тоже 2, но уже - других!
не понял, почему их будет ДВА?
будет один.
а в качестве координаты острова - брать левый верхний угол, к примеру.
для однозначной идентификации.
0
Ultrator
11 / 7 / 1
Регистрация: 28.04.2009
Сообщений: 219
07.06.2009, 15:44 #11
Ой, точно.
0
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
08.06.2009, 06:07  [ТС] #12
Patch
Да была такая у нас мысль.
Например вводим NxN, как 3x3 и допустим оператор rnd нам выведет такую матрицу:

000
110
110
с координатами:

x1, y1 =1
x2, y1 =1
x3, y1 =0
x1, y2 =1
x2, y2 =1
x3, y2 =0
x1, y3 =0
x2, y3 =0
x3, y3 =0
Наша програма будет проверять все эти координцаты и нужные нам символы откладывать в отдельный массив. Если углубится то сложней конечно будет, но проблема не в этом. Когда я говорил в первом посте, что все понел, то я имел ввиду, что понел поставленную задачу, но я не могу её написать, не могу написать сам код на С++. Скажите сделай сайт я вам замучу афигенский сайт за короткие сроки, но когда дело доходит до С++ я тут дальше cout и cin нешарю.
Так вот помогите пожалуйсто написать полный код. Мне это сдавать через пару дней :'(
0
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
08.06.2009, 07:06 #13
если я сделаю так, как считаю нужным, работать будет очень быстро и точно, но препод может не понять...
я 15 лет системы распознавания образов разрабатываю.
это задание - частный случай, и довольно простой.
лучше так: Трой, пиши как сам понимаешь, и как умеешь, а мы доделаем, если что не работает.
0
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
08.06.2009, 19:04  [ТС] #14
Patch
Ну когда я говорил, что дальше cout и cin не шарю это была правда

Так вот помогите пожалуйсто написать полный код. Мне это сдавать через пару дней :'(
0
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
08.06.2009, 19:54 #15
Цитата Сообщение от Трой Посмотреть сообщение
Ну когда я говорил, что дальше cout и cin не шарю это была правда
блин, ты-же писать умеешь?
по русски?
зайди на ядекс и спроси: "массивы в c c++"
узнаешь, как их делать.
и делай себе наздоровье.
я лет 15 назад Assembler и С изучал, так у меня была ОДНА растрепанная книга.
почти все делал методом научного тыка, потому как интернета тогда на 600км вокруг небыло, и спросить было не у кого.
а у вас вся информация под рукой...
так нет, лень-матушка...
ленишся читать и думать - иди в раздел "Заказ программ". с деньгами.
1
08.06.2009, 19:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2009, 19:54
Привет! Вот еще темы с ответами:

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...

Создать иерархию классов "Фирма", "Бухгалтер", "Сотрудник", "Зарплата" - C++
Само по себе понятие &quot;зарплата&quot; не особенно конкретное: оно включает и почасовую, и ставочную зарплату, и комиссионные, и процент с продаж....

Структура «Преподаватель» с полями "ФИО", "стаж", "категория", "нагрузка" - C++
Функция - расчёт зарплаты по нагрузке и оплате часа для определенной категории. Категория Оплата часа Вторая 150 Первая 200 ...


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

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

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