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

[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

[Unconnected]

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

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

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

[Lapp]

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

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

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