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

[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]

Ну было поле
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].