Вдохновленный
шедевром Казимира Малевича "Черный квадрат", Петр Палевич решил
создать собственную версию картины. Он приготовил полотно в виде прямоугольной
сетки с m × n белыми квадратами – m строк по n ячеек каждая.
Петр
покрасил некоторые клетки в черный цвет так, что черные ячейки сформировали
квадрат размером s × s ячеек. Но на следующий день Петр
разочаровался в своем творении и уничтожил его, разрезав полотно
горизонтальными полосами размера 1 × n,
после чего сжег их в камине.
На
следующее утро Петр передумал и решил восстановить картину. Он попытался найти
ее останки в камине, и, к счастью, одну из полос, а именно k-ую сверху, огонь не тронул.
Теперь
Петр задумался, можно ли восстановить картину на основе этой полосы. Помогите ему
сделать это.
Вход.
Первая строка содержит четыре целых числа: m, n, s и k
(1 ≤ m, n ≤ 5000, 1 ≤ s
≤ min(m, n), 1 ≤ k ≤ m).
Вторая строка содержит n символов и описывает k-ую строку картины, '.' означает белую
клетку, '*' означает черную клетку.
Выход. Если
изображение может быть однозначно восстановлено, то следует вывести
"Unique". Если существует несколько вариантов восстановления картины,
то вывести "Ambiguous". Если ни одной соответствующей картины не
существует, вывести "Impossible".
|
Пример
входа 1 |
Пример
выхода 1 |
|
4 4 1 2 ..*. |
Unique |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
4 4 2 2 ..** |
Ambiguous |
перебор
Вычислим
количество черных клеток в k-ой
строке картины. Все они должны располагаться рядом, их количество должно равняться
s.
Далее переберем
все возможные позиции (i, j) левого верхнего угла квадрата и
посчитаем количество вариантов расположения квадрата. Это число вариантов может
равняться 0 (ответ Impossible), 1 (ответ Unique), или быть больше 1 (ответ
Ambiguous).
k-ую строку картины будем хранить в массиве ss.
#define MAX 5010
char ss[MAX];
Читаем входные данные. Уменьшим значение k на 1 чтобы нумерация строк начиналась с нуля.
scanf("%d %d %d %d\n",&m,&n,&s,&k);
k--;
gets(ss);
Определим положение черных клеток: самая левая клетка будет в
позиции start, самая правая в finish. Вычислим общее количество черных
клеток sum.
sum = 0; start =
finish = -1;
for(i = 0; i < n; i++)
if (ss[i] == '*')
{
sum++;
if (start
== -1) start = i;
finish = i;
}
Рассмотрим случай, когда в k-ой строке имеются черные клетки. Тогда их количество sum должно равняться длине отрезка [start,
finish], а также значению s.
if ((sum > 0) && ((sum !=
finish - start + 1) || (sum != s)))
{
puts("Impossible");
return 0;
}
Переберем все возможные позиции (i, j) левого верхнего
угла квадрата и посчитаем количество вариантов pos расположения квадрата.
pos = 0;
for (i = 0; i < m - s + 1; i++)
for (j = 0; j < n - s + 1; j++)
Если k-ая строка
расположена среди строк [i, i + s
– 1], то она должна содержать черные клетки, причем самая левая позиция start черных клеток должна равняться j.
if ((i <=
k) && (k <= i + s - 1))
{
if (j ==
start) pos++;
}
else
{
Иначе k-ая строка
не должна содержать черные клетки (в этом случае start остается равным -1).
if (start
== -1) pos++;
}
В зависимости от значения pos
выводим ответ.
if (pos == 0)
puts("Impossible");
else if
(pos == 1)
puts("Unique");
else
puts("Ambiguous");