Indian National Olympiad in Informatics

Related:

Online Programming Contest, 24-25 December, 2005

IARCS home > OLYMPIAD

Advanced Division

Problem 2: Minimum Turn Route, (K Narayan Kumar, CMI)

The Siruseri amusement park has a new attraction. It consists of a rectangular array of discs. Each disc is divided into four equal sectors and the four sectors are coloured with the colours Red, Blue, Green and Yellow (in some order). The ordering may be different in different discs. Here is a possible arrangment of the discs:

You start at the top left disc. Your task is to walk down to the bottom right disc. In each step, you can rotate the current disc by 90 degrees in the clockwise direction or move to a neighbouring disc. However, you can move to a neighbouring disc only if adjacent sectors of these two discs have the same colour. For example, in the figure above, you can move from the disc at position (1,1) to either of its neighbours. However, from the disc at position (1,2) you can only move to the disc at position (1,1). If you wish to move from (1,2) to (1,3) then you would have to rotate this disc three times so that the colour (red) on the adjacent sectors are the same.

For each rotate move, a penalty point is added to the score. The aim is to reach the bottom right with as few penalty points as possible. For example, in the arrangement described in the above figure, the best possible score is 2, corresponding to the following path: Move from (1,1) to (2,1). Move from (2,1) to (2,2). Rotate. Rotate. Move from (2,2) to (2,3). Move from (2,3) to (1,3). Move from (1,3) to (1,4). Finally, move from (1,4) to (2,4).

Your task is to determine the minimum number of penalty points required to go from the top left disc to the bottom right disc for the given arrangement of discs.

Input format

The first line contains two integers M and N. M is the number of rows and N is the number of columns in the given arrangment. This is followed by M×N lines of input. Lines 2 to N+1, describe the colours on the discs on the first row, Lines N+2 to 2N+1 describe the colours on discs in the second row and so on. Each of these lines contain a permutation of the set {R, G, B, Y} giving the colours in the top, right, bottom and left sectors in that order.

Output format

A single integer on a single line indicating the minimum number of penalty points required to go from the top left disc to the bottom right disc for the given arrangement of discs.

Test Data:

You may assume that in 80% of the input, 1 ≤ M,N ≤ 60. Moreover, 1 ≤ M,N ≤ 1000 in all the inputs.

Example:

Here is the sample input and output corresponding to the example discussed above.

Sample Input

2 4
G Y B R
B G R Y
G Y B R
G R B Y
B Y G R
G B R Y
B R G Y
B R G Y

Sample Output