12959번 - 방향판

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

모든 칸은 (행, 열)로 나타낼 수 있으며, 가장 왼쪽 윗 칸은 (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은 오른쪽을 나타낸다.

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

예제 3