|
1 / 1 / 1
Регистрация: 12.08.2017
Сообщений: 34
|
|
Определить на сколько кусков распадётся клетчатый лист при удалаении заданных клеток29.06.2018, 23:05. Показов 18902. Ответов 10
Метки нет (Все метки)
Из прямоугольного листа клетчатой бумаги (N строк, M столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.
В первой строке входного файла INPUT.TXT находятся целые числа N и M, в следующих N строках – по M символов (1 ≤ N, M ≤ 100). Если клетка не была вырезана, этому соответствует знак #, если вырезана – точка. В выходной файл OUTPUT.TXT выведите одно число – ответ на задачу. Input: 4 8 #.##.#.# ......## #.###.## ##.##.## Output: 6
0
|
|
| 29.06.2018, 23:05 | |
|
Ответы с готовыми решениями:
10
Из листа клетчатой бумаги размером М*Н клеток удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа? Создать программу (Подсчитать, на сколько кусков распадется оставшаяся часть листа). Списки, Стеки,Очереди (На сколько кусков распадется оставшаяся часть листа? ) |
|
11 / 9 / 11
Регистрация: 14.06.2017
Сообщений: 20
|
||||||
| 29.06.2018, 23:24 | ||||||
|
Когда-то давно решал эту задачку где-то здесь https://informatics.msk.ru/mod... pterid=652
1
|
||||||
|
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,360
|
||
| 30.06.2018, 14:49 | ||
Хотя задача легко решается как поиском в глубину так и поиском в ширину.
0
|
||
|
11 / 9 / 11
Регистрация: 14.06.2017
Сообщений: 20
|
||
| 30.06.2018, 15:12 | ||
Однако dfs из этого кода несложно получить заменой очереди на стек. В этой задаче это не особо важно, т.к. все сводится к нахождению своеобразных компонент связности
0
|
||
|
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,360
|
|
| 30.06.2018, 16:57 | |
|
0
|
|
|
1 / 1 / 1
Регистрация: 12.08.2017
Сообщений: 34
|
||||||
| 30.06.2018, 17:29 [ТС] | ||||||
|
Новичок, я натыкалась на ваш ответ в теме Из листа клетчатой бумаги размером M умножить N клеток удалили некоторые клетки и там вы написали функцию, в которой надо было еще делать проверку на выход за границы массива и на то была ли посещена клетка. Я попробовала дописать, но оно как то не работает, можете указать на ошибки?
0
|
||||||
|
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,360
|
|
| 30.06.2018, 19:26 | |
|
MHeming123345, тяжело тут указать на ошибки - подход неправильный. Зачем внутри dfs этот цикл? Проверка нужна не для i, j а для i-1, j; i+1, j и.т.д. А в мейне уже запустить dfs для всех клеток(которые не посещались еще и не были удалены) и после каждого вызова dfs увеличивать переменную-результат на 1.
0
|
|
|
1 / 1 / 1
Регистрация: 12.08.2017
Сообщений: 34
|
||||||
| 30.06.2018, 20:10 [ТС] | ||||||
|
Новичок, то есть функция должна оставаться такой?
0
|
||||||
|
3 / 2 / 1
Регистрация: 29.10.2020
Сообщений: 28
|
|||||||||||
| 13.07.2021, 23:00 | |||||||||||
|
Решение. Дфс в матрице, суть заключается в том, что просто идем в соседние вершины, проверяем и закрашиваем чтобы повторно туда не зайти. Количесво частей на которые распадется лист равно количеству компонент связности, а то есть количеству цветов в графе. Работает за О(n*m).
1
|
|||||||||||
|
3 / 3 / 0
Регистрация: 27.02.2022
Сообщений: 18
|
|||||||||||||
| 02.11.2022, 22:34 | |||||||||||||
|
Один небольшой вопрос...
зачем? :
Зачем все эти костыли в коде??? ![]() И да, если вы забыли, то итерация в массиве начинается с 0.. ![]() Добавлено через 7 минут А нет, это я туплю. Прошу прощения)) Добавлено через 1 минуту Но тот факт, что итерация начинается с 0, все равно остается)
0
|
|||||||||||||
|
4086 / 2975 / 813
Регистрация: 29.06.2020
Сообщений: 11,000
|
||
| 03.11.2022, 00:06 | ||
|
От того что нет проверок на вводимые размеры, то это не совсем очевидно.
0
|
||
| 03.11.2022, 00:06 | |
|
Помогаю со студенческими работами здесь
11
На сколько кусков распадется часть листа, если из него вырезать некоторые клетки? Есть алгоритм. Из листа клетчатой бумаги N*N вырезали М клеток, на сколько кусков распадается оставшаяся часть листа? Лена взяла клетчатый лист, нарисовала на нем прямоугольник размера n×3mn
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование
. \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json>
Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом.
# Check if. . .
|
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так:
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347
Основана на STM32F303RBT6.
На борту пять. . .
|
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
|
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу,
и светлой Луне.
В мире
покоя нет
и люди
не могут жить в тишине.
А жить им немного лет.
|
|
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила»
«Время-Деньги»
«Деньги -Пуля»
|
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога
Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога
Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
|