Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Способы задания графа
---> 1 задач <---
Источники --> Личные олимпиады --> Украинские олимпиады
    1999(3 задач)
    2000(5 задач)
    2001(4 задач)
    2002(7 задач)
    2003(3 задач)
    2004(6 задач)
    2005(5 задач)
    2006(6 задач)
    2007(6 задач)
    2008(5 задач)
    2009(6 задач)
    2010(0 задач)
    2011(0 задач)
    2012(0 задач)
    2013(0 задач)
    2016(5 задач)
Страница: 1 Отображать по:
#1355
Векторы
  

На плоскости задано множество точек (x, y), где x, y – целые числа, 1≤x≤M, 1≤y≤N. Из каждой точки выходит ровно один из следующих векторов: (-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1). Каждый вектор соединяет одну целочисленную точку плоскости с другой. Например, если из точке (2, 5) выходит вектор (1, 1), то он соединяет эту точку с (3, 6), но не наоборот.

Последовательность из двух и более точек плоскости a1, a2,…, ak назовем циклом, если каждая точка ai соединена вектором с ai+1 (1≤i≤k-1), и ak соединена вектором с a1. Циклы считаются разными если они отличаются хотя бы одной вершиной.

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

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

Первая строка входного файла содержит два целых числа N (1≤N≤100) и M (1≤M≤100). Каждая из последующих N строк, содержит M пар чисел (т.е. 2≤M чисел). Пара x, которая находится в строке y, задает вектор в точке (x, y).

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

Единственная строка выходного файла должна содержать целое число – количество циклов, образованных векторами.

Примеры
Входные данные
2 4 
-1 1 -1 1 -1 0 0 1
1 0 1 0 0 -1 0 -1
Выходные данные
2
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест