Недавно прошёл муниципальный тур олимпиады, там встертилась очень интересная задача)) Вот её условие:
Укладка плитки
Бригаде строителей поручили уложить квадратной плиткой пол на кухне в виде шахматного узора. Но строители работали не очень слаженно, и когда весь пол уже был уложен, оказалось, что в некоторых местах плитки одинакового цвета граничат друг с другом.
По заданному замощению определите, какое минимальное число строителей могло укладывать плитку.
Входные данные
Input.txt содержит восемь строк, состоящих из 8 символов W и B - полученное замощение (W - белый, B - ченрый).
Выходные данные
Output.txt нужно вывести искомое число строителей.
И пример к этой задаче:
WBWBWBBW
BWBBWBWB
WBWWBWBW
WBWWBWWB
BWBBWBWB
WBWBWWBW
BWBWBBWB
WBWBWWBW
Ответ 4 строителя.
Очень хотелось бы услышать методы решения задачи. Лично я делил всё замощение по 4 плитки и просматривал различные плитки... Но подобное решение не прошло.
Предполагается, что каждый строитель укладывает непрерывную область?
Ну тогда просто перекрась все чётные (у которых сумма координат чётная) клетки и посмотри число связных областей.
Ну было поле
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].
TarasBer, спасибо, попробуем разобраться с графами
Хорошая задачка. Условие только не совсем ясно поставлено.. Про непрерывность (более правильно, наверное - связность) приходится додумывать самому, исходя из примера. Скажем, может быть еще гипотеза, что у каждого рабочего своя не только связная, но и прямоугольная область. Но эта гипотеза отвергается из примера. Могут, наверное, быть и другие гипотезы. Лучше бы они все же сказали это более явно..
Добавлено через 6 мин.
хотя, впрочем, подумавши немного, я готов согласиться, что этого достаточно. Фразу:
TarasBer, я проверил на 5 других тестах задачу, всё работает правильно.
А как можно придти к такому решению?)
Ну я в детстве любил составлять кроссворды, и я заметил, что намного проще составлять их из слов, где чередуются гласные и согласные. И тогда получится, что если покрасить клетки кроссворда в зависимости от гласности буквы, то получится шахматная доска.
Потом я стал для интереса смотреть, где происходит разрыв шахматности, получил непрерывную линию, делящую кроссвод на несколько частей. Потому я стал количество таких линий считать одним из критериев качественности кроссворда.
Короче, ну не знаю я, как додуматься. Просто смотришь, что объединяет те плитки, которые проложил один человек, думаешь, прикидываешь, доходишь до ответа.
Amoxicillin For Amoxil
Cialis 5 Mg Original
Trazadone Without Rx