Informatica Online Judge

  2마리 생쥐 [1106 / 0452]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 9   Total Tried : 15


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[Codeforces]

Background

이번에 sutekine선생님이 쥐가 다닐 수 있는 미로를 개발했다.

미로는 쥐의 집과 쥐가 이동할 수 있는 칸으로 구성된다.

집은 "#"로 표시되며, 쥐가 집에 위치한 순간부터는 움직이지 않는다.

이동할 수 있는 칸은 다음 4가지로 구성된다.

- "^" : 이 칸에 위치한 쥐는 윗 칸으로만 이동한다.
- "v" : 이 칸에 위치한 쥐는 아래칸으로만 이동한다.
- "<" : 이 칸에 위치한 쥐는 왼쪽 칸으로만 이동한다.
- ">" : 이 칸에 위치한 쥐는 오른쪽 칸으로만 이동한다.


지학이와 한필이는 두 마리의 생쥐를 새로 개발한 미로에 풀어 놓았다.

목적은 2마리의 쥐가 이동한 거리의 합을 최대화 하는 것이다. 쥐는 어느 위치에 놓아도 상관없으며, 모든 쥐는 동시에 움직이며, 1초에 1칸 씩 이동한다.

이동 중 두 쥐가 교차할 수는 있으나 결과적으로 같은 칸에 위치할 수는 없다.

단, "#"으로 표시된 집에는 2마리가 동시에 들어갈 수 있다.

미로가 주어질 때, 2마리의 쥐를 임의의 위치에 놓았을 때, 두 마리의 이동거리의 최댓값을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 n과 m이 공백으로 구분되어 입력된다. (n은 행의 크기, m은 열의 크기)
두 번째 줄부터 n줄에 걸쳐서 각 줄에 길이가 m인 문자열이 주어진다.
문자열의 각 문자는 "#", "<", ">", "^", "v" 중 하나이다.

[Sub-task Info]
- 66.7%의 데이터는 n, m이 100 이하의 값이다.
- 16.6%의 데이터는 n, m이 1,000 이하의 값이다.
- 16.7%의 데이터는 n, m이 2,000 이하의 값이다.

Output

두 마리의 쥐의 이동거리 합의 최댓값을 출력한다. 단, 무한이 이동할 수 있다면 "-1"을 출력한다.

IO Example

입력 1
3 4
####
#>v#
####

출력 1
3

입력2
4 3
###
#v#
#^#
###

출력2
-1

입력3
7 5
#####
##^##
##^##
#####
##^##
##^##
#####

출력3
4

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]