시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB34211970.370%

문제

방향판은 화살표로 채워져 있는 행렬이다. 각각의 화살표는 한 칸을 모두 차지하며, 왼쪽, 오른쪽, 위, 아래 중 한 방향을 가르키고 있다.

모든 칸은 (행, 열)로 나타낼 수 있으며, 가장 왼쪽 윗 칸은 (0, 0)이다.

각각의 칸 (r, c)에서 이동할 수 있는 칸은 (r, c)에 적혀있는 화살표에 따라 결정된다. 왼쪽인 경우에는 (r, c-1), 오른쪽인 경우에는 (r, c+1), 위쪽인 경우에는 (r-1, c), 아래쪽인 경우에는 (r+1, c)로 이동한다.

방향판의 모든 행과 열은 사이클 성질을 가지기 때문에, 방향판의 바깥으로 나가게 되면, 반대쪽으로 다시 들어오게 된다. 예를 들어, 게임판의 크기가 5 × 5인 경우에, (3, 0)에서 왼쪽으로 한 칸 이동하면 (3, 4)로 돌아오게 된다.

각각의 칸을 시작점이라고 했을 때, 항상 시작점으로 돌아올 수 있게 방향판의 화살표를 바꾸려고 한다. 예를 들어, 아래 그림과 같은 경우에 (1, 1), (1, 2), (2, 0), (2, 3)에 적힌 화살표를 바꿔서 항상 시작점으로 돌아오게 방향판을 바꿀 수 있다. 바꿔야 하는 화살표 개수의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 방향판의 행의 개수 N과 열의 개수 M이 주어진다. (1 ≤ N, M ≤ 15)

둘째 줄부터 N개의 줄에는 방향판의 정보가 주어진다. U는 위, D는 아래, L은 왼쪽, R은 오른쪽을 나타낸다.

출력

입력으로 주어진 방향판을 문제의 조건을 만족하게 바꾸기 위해서 바꿔야하는 화살표 개수의 최소 개수를 출력한다.

예제 입력 1

4 4
RRRD
URDD
UULD
ULLL

예제 출력 1

0

예제 입력 2

3 4
RRRD
URLL
LRRR

예제 출력 2

2

예제 입력 3

3 3
RRD
URD
ULL

예제 출력 3

2

예제 입력 4

2 6
ULRLRD
UDDLRR

예제 출력 4

4

힌트

예제 3

출처