슬리퍼

“먼저 일어난 사람이 슬리퍼를 신는다”는 러시아 속담이 있다. 하지만 우리 캠퍼스에서는 그렇게 간단하지 않다. 일찍 오는 것뿐만 아니라 (그렇지 않으면 슬리퍼는 이미 다 나가고 없다) 신발장의 엄격한 규칙도 따라야 한다.

신발장은 n × m 격자 모양이다. 각 칸에는 왼쪽 또는 오른쪽 슬리퍼가 하나씩 들어 있다. 처음에 각 슬리퍼는 왼쪽, 오른쪽, 앞, 뒤 네 방향 중 하나를 향하고 있다. 인접한 슬리퍼 두 개를 (서로 같아도 무방하다) 골라 하나는 시계 방향으로 90도, 다른 하나는 반시계 방향으로 90도 회전시킬 수 있다. 자연스러운 자세의 슬리퍼 한 쌍을 찾으면, 그것을 신고 행복하고 따뜻하게 떠날 수 있다.

슬리퍼 한 쌍이 자연스러운 자세라는 것은 다음과 같다:

• 두 슬리퍼의 칸이 한 변을 공유한다;
• 두 슬리퍼가 같은 방향을 향한다;
• 그 방향을 따라 두 칸을 바라볼 때, 한 칸이 오른쪽에 있고 다른 칸이 왼쪽에 있다. 그리고 오른쪽 칸에는 오른쪽 슬리퍼가, 왼쪽 칸에는 왼쪽 슬리퍼가 있다.

쉽게 말해, 평범한 사람이 이 슬리퍼 한 쌍에 자연스럽게 발을 넣을 수 있다는 뜻이다. 예시는 “힌트” 절을 참고하라.

모두가 이타적이어서 최적으로 행동한다고 가정할 때, 슬리퍼를 신고 떠날 수 있는 사람의 최대 수를 구하라.

입력의 첫 줄에는 격자의 크기 n과 m (1 ≤ n, m ≤ 100)이 주어진다. 다음 n개의 줄에는 각각 m개의 공백으로 구분된 문자열이 주어지며, 해당 칸의 슬리퍼를 나타낸다. 각 슬리퍼는 길이 2의 문자열로 표현된다. 첫 번째 문자는 “L” 또는 “R”이며 각각 왼쪽, 오른쪽 슬리퍼를 뜻한다. 두 번째 문자는 “<”, “>”, “^”, “v” 중 하나이며, 슬리퍼가 처음에 왼쪽, 오른쪽, 앞, 뒤를 향함을 뜻한다.

슬리퍼 한 쌍을 만들 수 있는 최대 개수를 정수 하나로 출력한다.

첫 번째 예시를 보자. 먼저 왼쪽 슬리퍼 두 개를 회전시킨다: 위쪽은 반시계 방향, 아래쪽은 시계 방향. 다음으로 위쪽 슬리퍼 두 개를 회전시킨다: 왼쪽은 반시계 방향, 오른쪽은 시계 방향. 그러면 자연스러운 자세의 슬리퍼 한 쌍이 두 개 생긴다: 위쪽 행에 하나, 아래쪽 행에 하나.

R^ L>    R< L>    Rv Lv
L< R^    L^ R^    L^ R^

이 예시에서 다른 최종 그림에 이르는 또 다른 가능한 행동 순서는 다음과 같다.

R^ L>    R< Lv    R< L>
L< R^    L< R^    L< R>