Стрелочки
(Время: 1 сек. Память: 16 Мб Сложность: 37%)
На бумаге нарисовали клетчатое поле N×M клеток. В каждой клетке нарисовали стрелочку в одном из четырех направлений «вправо», «вверх», «влево» или «вниз».
Дальше в некоторую клетку этого поля ставят фишку. Затем эту фишку сдвигают в соседнюю клетку в направлении стрелочки, нарисованной в клетке, где стоит фишка. Затем ее снова сдвигают по стрелке, нарисованной в той клетке, где она оказалась. Так продолжается до тех пор, пока фишка не окажется за пределами поля. Однако возможно, что фишка будет бесконечно ходить по полю.
Напишите программу, которая по заданному полю определит количество клеток, начав с которых фишка никогда не покинет пределы поля.
Входные данные
Во входном файле INPUT.TXT заданы сначала размеры поля – число строк N и число столбцов M (1 ≤ N, M ≤ 1000). Далее идет N строк по M чисел в каждой, задающих направления стрелочек в клетках. Число 1 обозначает стрелочку вправо, 2 – вверх, 3 – влево, 4 – вниз. Числа в строке разделяются пробелами.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – количество клеток, начав с которых фишка никогда не покинет пределы поля.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
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 2 1 2 3 4 | 0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|