e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

0-1 BFS

Включить лампу

Степан разрабатывает электронную схему на прямоугольной сетке размером n * m. Всего n * m квадратных плиток. Два (из четырёх) противоположных угла каждой плитки соединены проводом.

Источник питания подсоединен к левому верхнему углу сетки, лампа - к правому нижнему. Для того чтобы включить лампу можно повернуть любую плитку на 90 градусов в обоих направлениях.

На изображении лампа выключена. Если повернуть любую плитку во второй колонке справа, то лампа включится.

prb7403

Напишите программу, которая найдет минимальное количество плиток, которое надо перевернуть для того, чтобы включить лампу.

Входные данные

Первая строка содержит два целых числа n и m (1n, m500) - размеры сетки. Далее следуют n строк по m символов - \ или /, характеризующие направление провода на данной плитке.

Выходные данные

Вывести ответ к задаче, или сообщение "**NO SOLUTION**", если включить лампу невозможно.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3 5
\\/\\
\\///
/\\\\

Çıxış verilənləri #1
1
Mənbə 2015 ACM Ukraine, Первый этап, 25 апреля