task.md

Задача 10. Лабиринт с конкретным входом-выходом

Имя входного файла: in.txt
Имя выходного файла: out.txt
Ограничение по времени: 1 с
Ограничение по памяти: нет

Таблица размера n × m определяет некоторый лабиринт (нумерация строк и столбцов начинается с 1). B таблице элемент 1 обозначает стену, а элемент 0 — свободное место. В первой строке расположены входы x_i, а в последней — выходы y_i, i = 1, …, k, которые должны быть нулевыми элементами (все элементы первой и последней строк, отличные от входов и выходов, равны 1). Необходимо определить, можно ли провести k человек от входов x₁, x₂, …, x_k до выходов y₁, y₂, …, y_k соответственно таким образом, чтобы каждое свободное место посещалось не более одного раза.

Замечания

i-й человек начинает движение от входа xi и заканчивает движение на выходе y_i, i = 1, …, k. Движение в лабиринте осуществляется только по вертикали или горизонтали.

Формат входных данных

В первой строке задаются размеры n и m лабиринта. Следующие n строк содержат схему лабиринта (числа в строках не разделены пробелами; входы и выходы задаются нулями в первой и последней строках).

Формат выходных данных

Выведите сообщение Possible, если можно пройти, и Impossible, если нельзя.

Пример

in.txt	out.txt
7 6 110011 000000 000100 000000 110110 000000 111010	Possible

Решение