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

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

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

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

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

Собственно ниже условие и я вроде все понял, но как это сделать...
Буду очень благодарен за Вашу помощь.
Каждый элемент квадратной матрицы размерности NxN равен нулю либо единице. Найдите количество "островов", образованных единицами. Под "островом" понимается группа единиц, со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному "острову", если из одной из них можно перейти к другой, "наступая" на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2009, 01:26     Надо найти "острова" на квадратной матрице
Посмотрите здесь:
C++ Найти угол одной точки "A" в соотношении к точке "B" в градусах
Нужно найти слова которые встречаются в буквы "a" "z" C++
C++ Найти и заменить в строке все символы "а" на "b"
C++ Надо написать программу (игру) "Кости". Где ошибка?
Программа,где надо убрать эти "::" знаки C++
Надо ли книгу выбрасывать "в топку" (печь топить) C++
Метод "игрок берет все карты" не срабатывает как надо C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mikutu
26 / 26 / 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;
Evg
Эксперт CАвтор FAQ
17537 / 5775 / 370
Регистрация: 30.03.2009
Сообщений: 15,904
Записей в блоге: 26
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);
}
mikutu
26 / 26 / 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 острова
Evg
Эксперт CАвтор FAQ
17537 / 5775 / 370
Регистрация: 30.03.2009
Сообщений: 15,904
Записей в блоге: 26
03.06.2009, 11:59     Надо найти "острова" на квадратной матрице #5
> но его нужно реализовать и проверить на трудных примерах например

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

кстати что значит найти все острова в каком виде это выводить просто количество островов, обозначить их при выводе массива (каждый остров по разному или все одинаково)
Хороший вопрос. Я тоже вчера о нем подучал и сегодня хотел спросить его у преподавателя, но она сегодня не пришла
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
07.06.2009, 05:05  [ТС]     Надо найти "острова" на квадратной матрице #7
up
Evg
Эксперт CАвтор FAQ
17537 / 5775 / 370
Регистрация: 30.03.2009
Сообщений: 15,904
Записей в блоге: 26
07.06.2009, 12:00     Надо найти "острова" на квадратной матрице #8
И в чём проблема?
Ultrator
11 / 7 / 1
Регистрация: 28.04.2009
Сообщений: 219
07.06.2009, 15:32     Надо найти "острова" на квадратной матрице #9
Скорее всего, надо просто количество островов
(т.к. "разбиение" на острова, в некоторых случаях, не будет однозначно... как это ни странно).
Вот, например:
1 1
1 1
Если начать с [0][0] получим 2 острова, если с [1][1] - тоже 2, но уже - других!
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, но уже - других!
не понял, почему их будет ДВА?
будет один.
а в качестве координаты острова - брать левый верхний угол, к примеру.
для однозначной идентификации.
Ultrator
11 / 7 / 1
Регистрация: 28.04.2009
Сообщений: 219
07.06.2009, 15:44     Надо найти "острова" на квадратной матрице #11
Ой, точно.
Трой
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 нешарю.
Так вот помогите пожалуйсто написать полный код. Мне это сдавать через пару дней :'(
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
08.06.2009, 07:06     Надо найти "острова" на квадратной матрице #13
если я сделаю так, как считаю нужным, работать будет очень быстро и точно, но препод может не понять...
я 15 лет системы распознавания образов разрабатываю.
это задание - частный случай, и довольно простой.
лучше так: Трой, пиши как сам понимаешь, и как умеешь, а мы доделаем, если что не работает.
Трой
0 / 0 / 0
Регистрация: 03.06.2009
Сообщений: 7
08.06.2009, 19:04  [ТС]     Надо найти "острова" на квадратной матрице #14
Patch
Ну когда я говорил, что дальше cout и cin не шарю это была правда

Так вот помогите пожалуйсто написать полный код. Мне это сдавать через пару дней :'(
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2009, 19:54     Надо найти "острова" на квадратной матрице
Еще ссылки по теме:
Надо решить "Дано трехзначное число. Определить входит ли в него цифра 4." C++
C++ В чём ошибка? Надо чтобы подсчитывалось сколько раз нажата цифра "1"
Мне надо удалить все пустые "висюльки" у гирлянды (работа со списком) C++
произведение средних арифм. значений "диагоналей " в матрице C++
Заменить в матрице каждую "1" на сумму соседних в соответствующей строке элементов C++

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

Или воспользуйтесь поиском по форуму:
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
08.06.2009, 19:54     Надо найти "острова" на квадратной матрице #15
Цитата Сообщение от Трой Посмотреть сообщение
Ну когда я говорил, что дальше cout и cin не шарю это была правда
блин, ты-же писать умеешь?
по русски?
зайди на ядекс и спроси: "массивы в c c++"
узнаешь, как их делать.
и делай себе наздоровье.
я лет 15 назад Assembler и С изучал, так у меня была ОДНА растрепанная книга.
почти все делал методом научного тыка, потому как интернета тогда на 600км вокруг небыло, и спросить было не у кого.
а у вас вся информация под рукой...
так нет, лень-матушка...
ленишся читать и думать - иди в раздел "Заказ программ". с деньгами.
Yandex
Объявления
08.06.2009, 19:54     Надо найти "острова" на квадратной матрице
Ответ Создать тему
Опции темы

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