0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
|
||||||
1 | ||||||
Найти количество островов из единиц12.07.2015, 16:38. Показов 11452. Ответов 15
Метки нет (Все метки)
Здравствуйте, есть задачка.
Задача Острова Каждый элемент квадратной матрицы размеренности N x N равен нулю, либо единице. Найдите количество «островов», образованных единицами. Под «островом» понимается группа единиц (либо одна единица), со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному «острову», если из одной из них можно перейти к другой «наступая» на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали. Уточним, что одна единица тоже считается островом. Также предлагаю считывать матрицу из файла. Входные данные В первой строке файла INPUT.TXT записано натуральное число N не больше 100 - размер квадратной матрицы. В следующих N строках задаются элементы матрицы через пробел. Выходные данные В файл OUTPUT.TXT выведите единственное число - количество островов. Пример INPUT.TX T OUTPUT.TX T 5 1 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 4 Решение задачи Итак, это классическая задача на поиск в глубину графа. Понятно, что надо обходить матрицу и каким-то образом вычислять количество островов. Вариантрешения такой: после того, как мы попадаем на остров, надо это зафиксировать увеличив переменную-результат на единицу. Чтобы второй раз не посчитать один и тот же остров, сразу после посещения необходимо его уничтожить, т.е. присвоить всем клеткам острова значение ноль. Поскольку тест задачи не слишком мал, стоит написать процедуру уничтожения островов, назовем ее"count". Чтобы во время выполнения процедуру не "выскочить" за пределы массива, сделаем его не размером N x N, а размеров N+2 x N+2, это даст нам возможность окружить искомый массив размеромN x N нулями. вот код Кликните здесь для просмотра всего текста
Код данной программы реализован без графов. А мне нужно используя поиск в глубину реализовывать данный алгоритм. Есть идеи?
0
|
12.07.2015, 16:38 | |
Ответы с готовыми решениями:
15
Найти количество «островов» Найти количество островов на море В массиве найти количество "островов" из единиц Найти количество островов в матрице |
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||||||
12.07.2015, 19:14 | 2 | |||||
Сообщение было отмечено xDanceRx как решение
Решение
1
|
838 / 641 / 940
Регистрация: 26.06.2015
Сообщений: 1,409
|
||||||
12.07.2015, 19:45 | 3 | |||||
0
|
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
|
|
12.07.2015, 23:12 [ТС] | 4 |
спасибо за быстрый отклик, решил компильнуть, dev c++ пишет ошибки
строка 23 adj_cell_it = cells.begin (); [Error] 'adj_cell_it' does not name a typeм строка 24 adj_cell_it != cells.end (); [Error] 'adj_cell_it' was not declared in this scope дело в компиляторе? если у вас все работало? подскажите в какой среде вы работаете? Добавлено через 49 минут Геомеханик, спасибо за быстрый отклик, решил компильнуть, dev c++ пишет ошибки строка 23 adj_cell_it = cells.begin (); [Error] 'adj_cell_it' does not name a typeм строка 24 adj_cell_it != cells.end (); [Error] 'adj_cell_it' was not declared in this scope дело в компиляторе? если у вас все работало? подскажите в какой среде вы работаете?
0
|
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|
13.07.2015, 03:56 | 5 |
Да, у вас новый стандарт не поддерживает, auto не воспринимает. Можно просто явно тип указать.
1
|
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
|
|
13.07.2015, 09:57 [ТС] | 6 |
а какой нужно использовать компилятор, что бы поддерживал auto?
0
|
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|
13.07.2015, 10:05 | 7 |
1
|
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
|
|
13.07.2015, 11:50 [ТС] | 8 |
dev с++ должен все поддерживать, а точней его базовый компилятор. Погуглив узнал, что есть не мало вариаций, компилятора. Будь те добры, скажите свою среду и компилятор.
0
|
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|
13.07.2015, 11:53 | 9 |
У меня студия.
1
|
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
|
|
13.07.2015, 12:00 [ТС] | 10 |
понял, скачаю, протестирую, спасибо.
0
|
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
|
|
14.07.2015, 09:14 [ТС] | 12 |
Легче, если знаешь какой тип должен быть, думаю разбираться с кодом лучше тогда, когда он работает. Но если вам не составит труда " поправить тип итератора в программе" будет просто замечательно.
0
|
15.07.2015, 09:49 | 13 |
1
|
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
|
|
15.07.2015, 11:29 [ТС] | 14 |
Мне нужно осуществить реализацию с помощью графа, поэтому вариант выше - не подходит. Спасибо.
0
|
15.07.2015, 11:40 | 15 |
Насколько я понял, нужно именно через поиск в глубину. А в графе этот поиск, в матрице, или где-то ещё - дело десятое. Матрица всегда может рассматриваться как отображение графа. Удаление острова в моём примере делается поиском в глубину
0
|
0 / 0 / 0
Регистрация: 26.04.2014
Сообщений: 39
|
||||||
28.07.2015, 10:55 [ТС] | 16 | |||||
Доброе времени суток! Я новичок в программировании. Мне не понятен вот этот код. Написан он очень уж умно. А мне нужен примитивный, просто код, что бы его можно было легко читать. А этот код даже "загуглив" практически каждую строчку, требует практики, что бы его понять. Может быт, кто- нибудь смог бы его переписать более просто? на базовом уровне?
Задача Острова Каждый элемент квадратной матрицы размеренности N x N равен нулю, либо единице. Найдите количество «островов», образованных единицами. Под «островом» понимается группа единиц (либо одна единица), со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному «острову», если из одной из них можно перейти к другой «наступая» на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали. Уточним, что одна единица тоже считается островом. Также предлагаю считывать матрицу из файла. Входные данные В первой строке файла INPUT.TXT записано натуральное число N не больше 100 - размер квадратной матрицы. В следующих N строках задаются элементы матрицы через пробел. Выходные данные В файл OUTPUT.TXT выведите единственное число - количество островов. Пример INPUT.TXT 4 OUTPUT.TXT 5 1 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1 Решение задачи Итак, это классическая задача на поиск в глубину графа. Понятно, что надо обходить матрицу и каким-то образом вычислять количество островов. Вариант решения такой: после того, как мы попадаем на остров, надо это зафиксировать увеличив переменную-результат на единицу. Чтобы второй раз не посчитать один и тот же остров, сразу после посещения необходимо его уничтожить, т.е. присвоить всем клеткам острова значение ноль. Поскольку тест задачи не слишком мал, стоит написать процедуру уничтожения островов, назовем ее"count". Чтобы во время выполнения процедуру не "выскочить" за пределы массива, сделаем его не размером N x N, а размеров N+2 x N+2, это даст нам возможность окружить искомый массив размеромN x N нулями.
0
|
28.07.2015, 10:55 | |
28.07.2015, 10:55 | |
Помогаю со студенческими работами здесь
16
Определить по карте количество островов Найти количество единиц Подсчитать количество единиц в числе, кроме единиц в младших разрядах Определить количество единиц в цифровой записи числа, кроме единиц в младших разрядах Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |