Решение задачи «Гирлянды», ДонНУ?

Question

[ZiGR]

В данный момент VI региональная олимпиада ДонНУ закончилась. Я, как и обещал, публикую заново этот вопрос.

Среди заданий есть очень интересная задачка, которая называется «Гирлянды», связана с физикой.

Насколько мне известно, даже на открытом чемпионате Харькова по программированию эту задачу никто не решил. Хотелось бы услышать идеи Хабра.



Ограничения

Ограничения по памяти: 64 МБ

Ограничения по времени: 2 c.

Разрешено использовать: Pascal (FreePascal 2.4.2/Delphi Compiler 15.0), C/C++ (MinGW 3.4.2, Microsoft Visual C++ 2008/2010/2012)



Текст задачи

К Новому Году роботы наряжали компьютер светящейся гирляндой из лампочек, закрепленных на квадратной сетке макетной платы. Напряжение подведено к верхнему левому и нижнему правому углу макетной платы. Все лампочки одинаковые и светятся даже при очень слабых токах. В самый разгар подготовки одна из лампочек перегорела. Роботы очень заняты подготовкой, поэтому поручили Вам ответственную задачу — определить, какие лампочки в гирлянде останутся светиться постоянно, пусть и слабо. Напряжение считать постоянным (гирлянду запитали от блока питания компьютера), поэтому эффекты ёмкости и индуктивности учитывать не нужно.



Формат входных данных

В первой строке задано два целых числа: N — число ячеек сетки по вертикали и M — по горизонтали. Далее следует (2N+1) строка. В каждой нечётной строке записано M чисел — значения горизонтальных проводников. В каждой чётной строке записано (M+1) число — значения вертикальных проводников. Число 0 в строке означает, что проводник отсутствует (на рисунке представлено пунктирной линией), число 1 — присутствует проводник с лампочкой, число 2 обозначает перегоревшую лампочку (на рисунке — пунктирная лампочка). Гарантируется, что среди входных данных есть ровно одна двойка.



0 ≤ N ≤ 10, 0 ≤ M ≤ 10.



Формат выходных данных

Вывод должен содержать матрицу (подобную входной матрице), в которой число 0 означает отсутствие проводника с лампочкой, 1 — проводник есть и лампочка горит, 2 — проводник с лампочкой есть, но лампа не горит.





Примеры входных и выходных данных:

Answer 1

[Arktos]

Некорректно обсуждать задачу до окончания олимпиады

Comments

[ZiGR]

И то верно. В 10 по Киеву переношу вопрос в черновики.
После окончания возобновим обсуждение. Хоть 17 числа и будет консультация для участников олимпиады.

Answer 2

[Brand]

*удалено

Comments

[Brand]

Довёл до ума идею. Если перегоревшая лампа была мостом — ничего не будет гореть. Иначе пускаем глубину в две стороны до первых узлов — пройденные лампы не будут гореть.

[FilimoniC]

Тут маловероятна ситуация что лампа является мостом, т.к. это возможно только при матрицах Mx1 и 1xN. Перегоревшая лампочка является отсутствием проводника (скорее всего, это НЕ уточнено в задаче, т.к. бывает и по-другому), но требует указания на тип т.к. у нас негорящие лампочки надо «вернуть» в ответе и она там тоже должна быть, наверное (НЕ УКАЗАНО В УСЛОВИИ, считать ли мертвую лампочку «не горящей»)

[Brand]

Пример лампы-моста:
2 3
1 0 1
1 1 1 1
1 *1* 1
1 1 1 1
1 0 1
Звёздная единица — мост. Если такая лампа перегорает, ток идёт в никуда — ничего не будет светить.

[Brand]

Ну и ещё дополнение к идее. Если лампа — мост, но одна из компонент связности содержит обе точки подачи напряжения, то только другая компонента не будет гореть (ну и пуск глубины к первой компоненте).

Answer 3

[FilimoniC]

Рисунок не соответствует данным вроде бы

Comments

[ZiGR]

Почему не соответствует?
Это рисунок входящих данных. Пунктирная лампочка — это перегоревшая лампа.

[FilimoniC]

Все, понял, я думал что «число ячеек» — это контактные площадки, а не посадочные места лампочек

[FilimoniC]

Думаю, что решить можно любым методом «пускания» волны, если пренебречь законами физики. Препятствия — отсутствующие проводники и перегоревшие лампочки. Простой способ — составить избыточную матрицу из (2N+1) x (2M+1) элементов, каждый из которых может быть лампочкой, проводником или пустышкой и иметь статус «есть\нет ток». Пустить волну из левого верхнего угла. Затем все лампочки, у которых волна обазалась с обеих сторон, считать рабочими.

На основе этого: goo.gl/Aocwi, только значения не надо увеличивать, а только обрабатывать препятствия

[FilimoniC]

T и X -образные ячейки при наличии в них хотя бы одного живого проводника, можно целиком считать токопроводящими.
Салатовые — препятствия, полученные в ходе построения матрицы
Розовые — препятствия, полученные из входных данных

Думаю, на такой матрице проще работать

Answer 4

[FilimoniC]

Кстати, очень странное ограничение в 64 мегабайта. Многовато. за указанные 2с не кажддый жесткий диск успеет прочитать эту программу, не то что исполнить

Comments

[ZiGR]

Такое ограничение стоит почти на всех задачах. 2 секунды даётся именно на исполнение.

Answer 5

[Нуржан Бакибаев]

есть эта задача на каком-нибудь online judge чтобы проверить решение?

Comments

[Arktos]

acm.donnu.edu.ua/OpenContest.aspx?ContestId=17

Answer 6

[ivnik]

Алгоритм Флойда — Уоршелла?