Задача №114783. Дружелюбные ладьи
Ладья — шахматная фигура, которая может двигаться на любое число клеток по горизонтали или по вертикали при условии, что на её пути нет фигур. Ладья бьет шахматную фигуру, если фигура находится с ладьей на одной вертикали или горизонтали. В одной клетке шахматного поля может находится не более одной ладьи.
Вам даны \(k\) ладей и шахматная доска с размером \(n \times m\). Требуется расставить данные ладьи на этой доске так, чтобы они не били друг друга.
В единственной строке даны три натуральных числа \(n\), \(m\) и \(k\) — размеры поля и число ладей, соответственно (\(1 \le n, m, k \le 100\)).
Если расставить \(k\) ладей на поле \(n \times m\) невозможно, выведите строку Impossible .
Если хотя бы одна искомая расстановка существует, выведите Possible . А затем выведите \(n\) строк по \(m\) символов в каждой — описание итоговой расстановки ладей на поле. В \(i\)-й строке \(j\)-м символом выведите « * », если клетка \((i, j)\) содержит ладью, и « . », если соответствующая клетка вашей расстановки пуста.
Если подходящих расстановок несколько, можно вывести любую из них.
1 2 1
Possible *.
3 3 100
Impossible
3 5 2
Possible ..*.. ..... *....