Spaceships
Национална Олимпиада по Информатика 2016, Контролна 1
Time Limit: 3s, Memory Limit: 64MiB
Ели играе на нова игра! На правоъгълна дъска с N реда и M колони са разположени няколко междузвездни кораба. Всеки от корабите може да се движи в една единствена (предопределена) посока със скорост една клетка в секунда. Движещ се кораб не спира докато или излезе от дъската (в който случай играта приключва), или се блъсне в друг кораб. При сблъсък с друг кораб, досега движилият се изчезва, а блъснатият започва да се движи (в неговата си посока).

В началото никой от корабите не се движи. Единственото нещо, което играчът прави по време на играта, е да избере един от тях, при което той почва да се движи и играта протича по гореописания начин. В зависимост от това кой кораб избере Елеонора, играта може да продължи различен брой секунди. Сега момичето се чуди колко би продължила най-дългата възможна игра.
Вход
На първия ред на стандартния вход ще бъдат зададени две цели числа N и M – съответно броят редове и колони на дъската. Всеки от следващите N реда ще съдържа низ от M символа от азбуката {'<', '^', '>', 'v', '.'}. Стрелките обозначават кораб и неговата посока на движение (съответно наляво, нагоре, надясно и надолу), а точката обозначава празна клетка, през която корабите просто преминават.
Изход
На единствен ред на стандартния изход изведете едно единствено цяло число – броят секунди, който продължава най-дългата възможна игра на зададената дъска.
Ограничения
  • 1 ≤ N, M ≤ 100
  • Гарантирано е, че дъската ще съдържа поне един кораб.
Примерен Вход Примерен Изход
5 6 vv.^>> .^.<>. >>.^>v .^v>.. ^^...< 21
Избирането на кораба в горната лява клетка би довело до игра с продължителност 16 секунди:
  1. Първият кораб би летял надолу две секунди, докато се блъсне в (2, 0);
  2. Вторият кораб би летял надясно една секунда, докато се блъсне в (2, 1);
  3. Третият кораб би летял надясно две секунди, докато се блъсне в (2, 3);
  4. Четвъртият кораб би летял нагоре една секунда, докато се блъсне в (1, 3);
  5. Петият кораб би летял наляво две секунди, докато се блъсне в (1, 1);
  6. Шестият кораб би летял нагоре една секунда, докато се блъсне в (0, 1);
  7. Седмият кораб би летял надолу три секунди, докато се блъсне в (3, 1). Забележете, че корабите в (1, 1) и (2, 1) вече са се блъснали и сега техните полета са празни;
  8. Осмият кораб би летял нагоре четири секунди, докато излезе от дъската, в който момент играта свършва.
По-оптимално за Ели би било да избере кораба в (2, 3), което би довело до игра с продължителност 21 секунди.
Мрън!