Олимпиады по программированию

olympiads.ru

II Всероссийская заочная олимпиада школьников по информатике, 2007/08 учебный год

Задача E. Стрелочки

На бумаге нарисовали клетчатое поле NxM клеток. В каждой клетке нарисовали стрелочку в одном из четырех направлений "вправо", "вверх", "влево" или "вниз".

Дальше в некоторую клетку этого поля ставят фишку. Затем эту фишку сдвигают в соседнюю клетку в направлении стрелочки, нарисованной в клетке, где стоит фишка. Затем ее снова сдвигают по стрелке, нарисованной в той клетке, где она оказалась. Так продолжается до тех пор, пока фишка не окажется за пределами поля. Однако возможно, что фишка будет бесконечно ходить по полю и никогда не выйдет за его пределы.

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

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

Во входном файле заданы сначала размеры поля - число строк N и число столбцов M (1≤N≤1000, 1≤M≤1000). Далее идет N строк по M чисел в каждой, задающих направления стрелочек в клетках. Число 1 обозначает стрелочку вправо, 2 - вверх, 3 - влево, 4 - вниз. Числа в строке разделяются пробелами.

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

В выходной файл выведите одно число - количество клеток, начав с которых фишка никогда не покинет пределы поля.

Примеры

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