Задача №1101. Стрелочки
На бумаге нарисовали клетчатое поле NxM клеток. В каждой клетке нарисовали стрелочку в одном из четырех направлений «вправо», «вверх», «влево» или «вниз».
| ← | → | → | ↓ | ↑ |
| → | ↑ | ↓ | ← | → |
| ↓ | ↑ | → | → | ↓ |
| → | ↑ | ← | ← | ← |
| ← | → | ↓ | ↓ | ↓ |
| ↑ | ↑ | ← | ↓ | ↑ |
Дальше в некоторую клетку этого поля ставят фишку. Затем эту фишку сдвигают в соседнюю клетку в направлении стрелочки, нарисованной в клетке, где стоит фишка. Затем ее снова сдвигают по стрелке, нарисованной в той клетке, где она оказалась. Так продолжается до тех пор, пока фишка не окажется за пределами поля. Однако возможно, что фишка будет бесконечно ходить по полю и никогда не выйдет за его пределы.
Напишите программу, которая по заданному полю определит количество клеток, начав с которых фишка никогда не покинет пределы поля.
Во входном файле заданы сначала размеры поля – число строк N и число столбцов M (1≤N≤1000, 1≤M≤1000). Далее идет N строк по M чисел в каждой, задающих направления стрелочек в клетках. Число 1 обозначает стрелочку вправо, 2 – вверх, 3 – влево, 4 – вниз. Числа в строке разделяются пробелами.
В выходной файл выведите одно число – количество клеток, начав с которых фишка никогда не покинет пределы поля.
Комментарии к примерам тестов.
Пример №1.Соответствует приведенному рисунку. Клетки, начавс которых, фишка никогда не покинет пределов поля на рисунке выделены серым цветом.
6 5 3 1 1 4 2 1 2 4 3 1 4 2 1 1 4 1 2 3 3 3 3 1 4 4 4 2 2 3 4 2
23
2 2 1 2 3 4
0