1

Тема: Задача про лампу.

Маємо електронну схему на прямокутній сітці розміром N*M.
Усього N*M квадратних плиток. Два (з чотирьох) протилежних кута кожної
плитки з'єднані дротом. Джерело живлення під’єднано до лівого верхнього кута сітки, лампа - до
правого нижнього. Для того щоб увімкнути лампу можна повернути будь-яку
плитку на 90 градусів у обох напрямках.
На зображені лампа вимкнута. Якщо повернути будь-яку плитку у другій
cправа колонці, то лампа увімкнеться.
Написати програму, яка знаходить мінімальну кількість плиток, що треба
перевернути для того, щоб увімкнути лампу.
Вхідні дані:
Перший рядок містить два цілих числа N та M - розміри сітки. Далі
слідують N рядків по M символів - \ або /, що характеризують напрямлення
дроту на даній плитці.
Вихідні дані:
Єдиний рядок вихідного файлу має містити відповідь на задачу, або ж
повідомлення "NO SOLUTION", в тому випадку, коли увімкнути лампу
неможливо.
Обмеження:
1 ≤ N, M ≤ 500.

Приклад:
Приклад
Input:
3 5     
\\/\\
\\///
/\\\\
Output:
1

Post's attachments

Снимок.PNG 21.03 kb, 132 downloads since 2015-06-10 

2

Re: Задача про лампу.

Знайдіть у правилах малюнок.