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:-----
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 \times N$ lines of input. Lines $2$ to $N+1$, describe the colours on the discs on the first row, Lines $N+2$ to $2 \cdot N+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:-----
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.

-----Constraints:-----
- In $80 \%$ of the input, $1 \leq M,N \leq 60$.
- In all the inputs $1 \leq M,N \leq 1000$.

-----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-----
2

Difficulty: interview

Starter code:

Solutions:
#for _ in range(int(input()):
#n,m = map(int,input().split())
#x = [int(w) for w in input().split()]
#n = int(input())
#x = [int(input()) for _ in range(n)]
#for i in range(n):
#dt = {} for i in x:dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}

m,n = map(int,input().split())  # top,right,bottom,left
x = []
for i in range(m):
    x.append([])
    for j in range(n):
        clr = [w for w in input().split()]
        x[i].append(clr)

import queue as Q                
dp = [float('inf')]*m
for i in range(m):
    dp[i] = [float('inf')]*n
dp[m-1][n-1] = 0
pq = Q.PriorityQueue()
pq.put([dp[m-1][n-1],m-1,n-1])
visited = set()
xx,yy = [-1,0,1,0],[0,1,0,-1] # top,right,bottom,left
while not pq.empty():
    pop = pq.get()
    cx,cy = pop[1],pop[2]
    if (cx,cy) not in visited:
        visited.add((cx,cy))
        for k in range(4):
            nx,ny = cx+xx[k],cy+yy[k]
            if 0<=nx<m and 0<=ny<n and (nx,ny) not in visited:
                clr = x[cx][cy][k]
                #print("*",nx,ny,"_",k,clr)
                ind = x[nx][ny].index(clr)
                cost = (k-(ind+2)%4)%4
                #print(cost)
                if dp[cx][cy]+cost < dp[nx][ny]:
                    dp[nx][ny] = dp[cx][cy]+cost
                    pq.put([dp[nx][ny],nx,ny])
        #print("#############")
#print(dp)
print(dp[0][0])

from bisect import insort
class disk:
    def __init__(self):
        self.U = ''
        self.D = ''
        self.L = ''
        self.R = ''
        
        
m, n = map(int,input().split())
adj = [[] for _ in range(m*n)]
grid = [[disk() for _ in range(n)] for _ in range(m)]
for i in range(m):
    for j in range(n):
        grid[i][j].U,grid[i][j].R,grid[i][j].D,grid[i][j].L = input().split()
for i in range(m):
	for j in range(n):
		if (j!=0):

			if (grid[i][j].R == grid[i][j-1].R):
			    dist = 2
			if (grid[i][j].U == grid[i][j-1].R): 
			    dist = 3
			if (grid[i][j].L == grid[i][j-1].R): 
			    dist = 0
			if (grid[i][j].D == grid[i][j-1].R): 
			    dist = 1
			adj[i*n + j].append((dist, i*n + j - 1))
		
		if (j!=n-1):

			if (grid[i][j].R == grid[i][j+1].L): 
			    dist = 0
			if (grid[i][j].U == grid[i][j+1].L): 
			    dist = 1
			if (grid[i][j].L == grid[i][j+1].L): 
			    dist = 2
			if (grid[i][j].D == grid[i][j+1].L): 
			    dist = 3
			adj[i*n + j].append((dist, i*n + j + 1))

		
		if (i!=0):

			if (grid[i][j].R == grid[i-1][j].D):
			    dist = 3
			if (grid[i][j].U == grid[i-1][j].D):
			    dist = 0
			if (grid[i][j].L == grid[i-1][j].D):
			    dist = 1
			if (grid[i][j].D == grid[i-1][j].D):
			    dist = 2
			adj[i*n + j].append((dist, i*n + j - n))

		
		if (i!=m-1):

			if (grid[i][j].R == grid[i+1][j].U): 
			    dist = 1
			if (grid[i][j].U == grid[i+1][j].U): 
			    dist = 2
			if (grid[i][j].L == grid[i+1][j].U): 
			    dist = 3
			if (grid[i][j].D == grid[i+1][j].U):
			    dist = 0
			adj[i*n + j].append((dist, i*n + j + n))
q = []
q.append((0,0))
dists = [2147483647 for _ in range(m*n)]
visited = [False for _ in range(m*n)]
dists[0] = 0
while q:
    cur = q[-1]
    q.pop()
    if visited[cur[1]] == False:
        visited[cur[1]] = True
        dists[cur[1]] = -1*cur[0]
    for i in range(len(adj[cur[1]])):
        to = adj[cur[1]][i][1]
        dis = adj[cur[1]][i][0]
        if (not visited[to] and dists[cur[1]] + dis < dists[to]):
            insort(q,(-1*(dists[cur[1]] + dis),to))
print(dists[m*n - 1])