Задача №1963. Окна
Отличнице Лене классный руководитель поручил на Новый год важное задание — определить, в каких окнах школы следует зажечь свет, чтобы при взгляде с улицы о́кна, в которых включен свет, составляли картинку, похожую на данную. Ленину школу можно приближённо считать таблицей высотой \(H\) и шириной \(W\). Естественно, некоторые окна могут принадлежать одному кабинету: во всех окнах одного кабинета свет может быть либо только включен, либо только выключен. Для каждого окна известен номер кабинета, которому оно принадлежит; известна также желаемая картинка. Помогите Лене так определить, где свет должен быть включен, а где — нет, чтобы количество окон, состояние которых не совпадает с желаемым, было минимальным. Если ответов несколько, требуется минимизировать количество кабинетов, в которых свет включен.
В первой строке входного файла содержатся три натуральных числа \(W\), \(H\) и \(K\) — ширина школы, её высота и количество кабинетов (\(1\le W,H\le10^3\), \(1\le K\le W\cdot H\)). В следующих \(H\) строках содержится по \(W\) натуральных чисел — для каждого окна номер кабинета, которому оно принадлежит. (Каждое из этих чисел не превышает \(K\), каждому кабинету принадлежит хотя бы одно окно.) Далее следуют \(H\) строк по \(W\) символов ‘.’ или ‘#’ для выключенных и включенных окон соответственно — описание желаемой картинки.
Выведите ответ на задачу: в первой строке количество кабинетов, свет в которых нужно включить, а во второй — номера этих кабинетов в возрастающем порядке.
3 3 5 1 2 5 3 5 5 5 5 4 .## #.# ..#
3 2 3 4