1 / 1 / 1
Регистрация: 12.08.2017
Сообщений: 34
|
|
1 | |
Определить на сколько кусков распадётся клетчатый лист при удалаении заданных клеток29.06.2018, 23:05. Показов 17488. Ответов 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 | 2 | |||||
Когда-то давно решал эту задачку где-то здесь https://informatics.msk.ru/mod... pterid=652
1
|
11 / 9 / 11
Регистрация: 14.06.2017
Сообщений: 20
|
|
30.06.2018, 15:12 | 4 |
Согласен. Однако dfs из этого кода несложно получить заменой очереди на стек. В этой задаче это не особо важно, т.к. все сводится к нахождению своеобразных компонент связности
0
|
1 / 1 / 1
Регистрация: 12.08.2017
Сообщений: 34
|
||||||
30.06.2018, 17:29 [ТС] | 6 | |||||
Новичок, я натыкалась на ваш ответ в теме Из листа клетчатой бумаги размером M умножить N клеток удалили некоторые клетки и там вы написали функцию, в которой надо было еще делать проверку на выход за границы массива и на то была ли посещена клетка. Я попробовала дописать, но оно как то не работает, можете указать на ошибки?
0
|
1682 / 1095 / 489
Регистрация: 17.07.2012
Сообщений: 5,360
|
|
30.06.2018, 19:26 | 7 |
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 [ТС] | 8 | |||||
Новичок, то есть функция должна оставаться такой?
0
|
3 / 2 / 1
Регистрация: 29.10.2020
Сообщений: 28
|
||||||
13.07.2021, 23:00 | 9 | |||||
Решение. Дфс в матрице, суть заключается в том, что просто идем в соседние вершины, проверяем и закрашиваем чтобы повторно туда не зайти. Количесво частей на которые распадется лист равно количеству компонент связности, а то есть количеству цветов в графе. Работает за О(n*m).
Код
1 Accepted 0,015 372 Кб 2 Accepted 0,015 372 Кб 3 Accepted 0,015 376 Кб 4 Accepted 0,015 376 Кб 5 Accepted 0,015 832 Кб 6 Accepted 0,03 716 Кб 7 Accepted 0,015 484 Кб 8 Accepted 0,015 588 Кб 9 Accepted 0,015 520 Кб 10 Accepted 0,015 368 Кб 11 Accepted 0,015 372 Кб 12 Accepted 0,015 380 Кб
1
|
3 / 3 / 0
Регистрация: 27.02.2022
Сообщений: 18
|
|||||||||||
02.11.2022, 22:34 | 10 | ||||||||||
Один небольшой вопрос...
зачем? : нельзя ли просто написать изначально
Зачем все эти костыли в коде??? И да, если вы забыли, то итерация в массиве начинается с 0.. Добавлено через 7 минут А нет, это я туплю. Прошу прощения)) Добавлено через 1 минуту Но тот факт, что итерация начинается с 0, все равно остается)
0
|
3697 / 2647 / 761
Регистрация: 29.06.2020
Сообщений: 9,800
|
|
03.11.2022, 00:06 | 11 |
Это наверное рамка ограничитель, не зря же он массивы в статическую память положил, global scope.
От того что нет проверок на вводимые размеры, то это не совсем очевидно.
0
|
03.11.2022, 00:06 | |
03.11.2022, 00:06 | |
Помогаю со студенческими работами здесь
11
Из листа клетчатой бумаги N*N вырезали М клеток, на сколько кусков распадается оставшаяся часть листа? Лена взяла клетчатый лист, нарисовала на нем прямоугольник размера n×3mn Определить сколько клеток по периметру доски Определить, сколько значений f(x) при заданных x расположены выше и ниже указанной прямой Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |