Укладка плитки, Городская олимпиада Опции

[Cheburashka]

Недавно прошёл муниципальный тур олимпиады, там встертилась очень интересная задача)) Вот её условие:

Укладка плитки
Бригаде строителей поручили уложить квадратной плиткой пол на кухне в виде шахматного узора. Но строители работали не очень слаженно, и когда весь пол уже был уложен, оказалось, что в некоторых местах плитки одинакового цвета граничат друг с другом.
По заданному замощению определите, какое минимальное число строителей могло укладывать плитку.
Входные данные
Input.txt содержит восемь строк, состоящих из 8 символов W и B - полученное замощение (W - белый, B - ченрый).
Выходные данные
Output.txt нужно вывести искомое число строителей.

И пример к этой задаче:
WBWBWBBW
BWBBWBWB
WBWWBWBW
WBWWBWWB
BWBBWBWB
WBWBWWBW
BWBWBBWB
WBWBWWBW
Ответ 4 строителя.

Очень хотелось бы услышать методы решения задачи. Лично я делил всё замощение по 4 плитки и просматривал различные плитки... Но подобное решение не прошло.

Сообщение отредактировано: Сергей Меркурьев - 17.11.2010 17:48

[TarasBer]

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

[Cheburashka]

Предполагается, что каждый строитель укладывает непрерывную область?

Условие которое я дал, оно полное. Что же касается непрерывной области я не знаю Сам гадаю, как могу.

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

Не могли бы Вы поподробнее объяснить этот момент?

[TarasBer]

Ну было поле
01010101
10110101
01011010
10100101
01101011
11010100

Перекрасили все чётные клетки на противоположный цвет

стало такое:

00000000
00011111
00001111
00001111
00111110
01111110

Тут 3 области (сам как-нибудь применишь стандартные алгоритмы обхода графа, чтобы понять, что их три).

А вот пример из задания:

10101001
01001010
10110101
10110110
01001010
10101101
01010010
10101101

Перекрашиваем, получаем

11111100
11100000
11100000
00011100
00011111
00000111
00000111
00000111

тут 4 области.

На самом деле про перекраску я для наглядности сказал.
Просто сделай обход исходного графа, в качестве условия связности клеток возьми A[i1,j1] <> A[i2,j2].

[Cheburashka]

TarasBer, спасибо, попробуем разобраться с графами

[Lapp]

Хорошая задачка. Условие только не совсем ясно поставлено.. Про непрерывность (более правильно, наверное - связность) приходится додумывать самому, исходя из примера. Скажем, может быть еще гипотеза, что у каждого рабочего своя не только связная, но и прямоугольная область. Но эта гипотеза отвергается из примера. Могут, наверное, быть и другие гипотезы. Лучше бы они все же сказали это более явно..

Добавлено через 6 мин.
хотя, впрочем, подумавши немного, я готов согласиться, что этого достаточно. Фразу:

Но строители работали не очень слаженно

- можно толковать так, что каждый при укладке обращал внимание только на согласованность с плитками, уложенными им самим (как они их распознают потом - не важно). И тогда все становится на свои места .

Все возражения снимаю. А задача еще поднимается в моих глазах .

[Cheburashka]

TarasBer, я проверил на 5 других тестах задачу, всё работает правильно.
А как можно придти к такому решению?)

[TarasBer]

Ну я в детстве любил составлять кроссворды, и я заметил, что намного проще составлять их из слов, где чередуются гласные и согласные. И тогда получится, что если покрасить клетки кроссворда в зависимости от гласности буквы, то получится шахматная доска.
Потом я стал для интереса смотреть, где происходит разрыв шахматности, получил непрерывную линию, делящую кроссвод на несколько частей. Потому я стал количество таких линий считать одним из критериев качественности кроссворда.

Короче, ну не знаю я, как додуматься. Просто смотришь, что объединяет те плитки, которые проложил один человек, думаешь, прикидываешь, доходишь до ответа.

[Unconnected]

каждый при укладке обращал внимание только на согласованность с плитками, уложенными им самим

Ну тогда например положил первый рабочий 4 плитки и ушел на перекур, подошел второй, который до этого ничего не клал, продолжать эту линию, на что ему ориентироваться и что класть? Они как-то между собой наверное согласовываться должны все же.

Сообщение отредактировано: Unconnected - 18.11.2010 18:34

[Lapp]

Ну тогда например положил первый рабочий 4 плитки и ушел на перекур, подошел второй, который до этого ничего не клал, продолжать эту линию, на что ему ориентироваться и что класть? Они как-то между собой наверное согласовываться должны все же.

Не нужно забывать, что это все же абстракция.
Меня всегда радует, когда автору удается придумать хорошую проекцию "на реальную жизнь". Это на самом деле ОООЧЕНЬ непросто бывает. Но оно того стОит - решать веселее, проще с созданим образов.. Но излишнего углубления в реальность следует избегать. Иначе говоря, тут, например, рабочий - РАБОТАЕТ (а не ест, курит и т.п.) Работа сделана (все ЕГО плитки невозможно продолжить) - уходит.

Это тоже все очень важно. Это помогает потом абстрагироваться в действительно реальной (это тавтология?)) задаче.

[Lapp]

Они как-то между собой наверное согласовываться должны все же.

И еще один момент..
В условии сказано найти МИНИМАЛЬНОЕ возможное количество рабочих. Если, скажем, кто-то сверился с соседом - то его кладку от кладки соседа теперь не отличить. Это значит, что 2 рабочих превратились в 1 - то есть, общее количество рабочих уменьшилось. Поэтому, если они худо-бедно сверяются с соседями, то условие все равно при этом не нарушается.

А если рабочий начинает укладку в области, в которой слева один способ, а справа - другой, то он неизбежно присоединится к одному и законфликтует с другим. И снова условие задачи не нарушено и результат (при верном решении) будет верным.

[how to order prednisone for a do]

Amoxicillin For Amoxil

[where can i buy plaquenil in tuc]

Cialis 5 Mg Original

[buy cialis online with a prescri]

Trazadone Without Rx