cho.shDirection Board
Given a toroidal N x M grid of arrows (N,M <= 15), change the fewest arrows so that every cell lies on a cycle of length 1.
Hard8GraphBit manipulationDynamic programmingBrute forceNo attempts yetTime limit2sMemory limit512 MBProblem
A direction board is a matrix filled with arrows. Each arrow takes up one whole cell and points left, right, up, or down.
A cell is written as (row, column), and the top left cell is (0, 0).
The arrow written in cell (r, c) decides which cell you move to next. Left moves to (r, c-1), right moves to (r, c+1), up moves to (r-1, c), and down moves to (r+1, c).
Every row and every column of the board wraps around, so leaving the board on one side brings you back in on the opposite side. For example, on a board of size 5 × 5, moving one cell left from (3, 0) takes you to (3, 4).
You want to rewrite arrows so that, whichever cell you start from, following the arrows always brings you back to that starting cell. For example, in the board drawn below you can change the arrows at (1, 1), (1, 2), (2, 0), and (2, 3) to make every start return to itself. Write a program that finds the minimum number of arrows you have to change.
Input
The first line contains the number of rows N and the number of columns M of the board. (1 ≤ N, M ≤ 15)
Each of the next N lines contains a string of length M describing the board. U is up, D is down, L is left, and R is right.
Output
Print the minimum number of arrows you have to change so that the given board satisfies the condition.