You have a rectangular board consisting of $n$ rows, numbered from $1$ to $n$, and $m$ columns, numbered from $1$ to $m$. The top left is $(1,1)$ and the bottom right is $(n,m)$. Initially - at time $0$ - there is a coin on the top-left cell of your board. Each cell of your board contains one of these letters:  

*: Exactly one of your cells has letter '*'.

U: If at time $\boldsymbol{\boldsymbol{t}}$ the coin is on cell $(i,j)$ and cell $(i,j)$ has letter 'U', the coin will be on cell $(i-1,j)$ at time $t+1$, if $i>1$. Otherwise, there is no coin on your board at time $t+1$.

L: If at time $\boldsymbol{\boldsymbol{t}}$ the coin is on cell $(i,j)$ and cell $(i,j)$ has letter 'L', the coin will be on cell $(i,j-1)$ at time $t+1$, if $j>1$. Otherwise, there is no coin on your board at time $t+1$.

D: If at time $\boldsymbol{\boldsymbol{t}}$ the coin is on cell $(i,j)$ and cell $(i,j)$ has letter 'D', the coin will be on cell $(i+1,j)$ at time $t+1$, if $i<N$. Otherwise, there is no coin on your board at time $t+1$.

R: If at time $\boldsymbol{\boldsymbol{t}}$ the coin is on cell $(i,j)$ and cell $(i,j)$ has letter 'R', the coin will be on cell $(i,j+1)$ at time $t+1$, if $j<M$. Otherwise, there is no coin on your board at time $t+1$.

When the coin reaches a cell that has letter '*', it will stay there permanently. When you punch on your board, your timer starts and the coin moves between cells. Before starting the game, you can make operations to change the board, such that you are sure that at or before time $\boldsymbol{\mbox{k}}$ the coin will reach the cell having letter '*'. In each operation you can select a cell with some letter other than '*' and change the letter to 'U', 'L', 'R' or 'D'. You need to carry out as few operations as possible in order to achieve your goal. Your task is to find the minimum number of operations. 

For example, given a grid of $n=2$ rows and $m=3$ columns:

UDL
RR*

the goal is to get from $(1,1)$ to $(2,3)$ in as few steps as possible.  As the grid stands, it cannot be done because of the U in the cell at $(1,1)$.  If $(1,1)$ is changed to D, the path $(1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(2,3)$ is available.  It could also be changed to R which would make the path $(1,1)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(2,3)$ available.  Either choice takes $1$ change operation, which is the value sought if $k\geq3$.  A lower value of $\boldsymbol{\mbox{k}}$ would result in a return value of $-1$ because the shortest path is $3$ steps, starting from $(1,1)$.  

Function Description  

Complete the coinOnTheTable function in the editor below.  It should return an integer that represents the minimum operations to achieve the goal, or $-1$ if it is not possible.  

coinOnTheTable has the following parameters:  

m: an integer, the number of columns on the board  
k: an integer, the maximum time to reach the goal  
board: an array of strings where each string represents a row of the board  

Input Format

The first line of input contains three integers, $n$, $m$, and $\boldsymbol{\mbox{k}}$, the number of rows, the number of columns and the maximum time respectively.  

The next $n$ lines contain $m$ letters each, describing your board.   

Constraints

$n,m\leq51$ 

$k\leq1000$  

Output Format

Print an integer which represents the minimum number of operations required to achieve your goal.
If you cannot achieve your goal, print $-1$.

Sample Input
2 2 3  
RD  
*L

Sample output :

0

Sample input :

2 2 1  
RD  
*L

Sample output :

1

Explanation :

In the first example, a valid path exists without making any changes.  In the second example, the letter of cell (1,1) must be changed to 'D' to make a valid path.  In each example, a path length $\leq k$ is available.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
class Element:

	def __init__(self, data, next):
		self.data = data
		self.next = next

class Queue:

	def __init__(self):
		self.head = None

	def __str__(self):
		ptr = self.head
		if self.head == None:
			string = 'Front < > Back'
		else:
			string = 'Front < '
			while ptr:
				string += '%s ' % str(ptr.data)
				ptr = ptr.next
			string += '> Back'
		return string

	def enQueue(self, data):
		ptr = self.head
		if ptr == None:
			self.head = Element(data, self.head)
		else:
			while ptr.next:
				ptr = ptr.next
			ptr.next = Element(data, None)

	def deQueue(self):
		if self.head == None:
			return None
		ptr = self.head
		self.head = self.head.next
		ptr.next = None
		return ptr.data

def findEnd(table):
	for (ri, row) in enumerate(table):
		for (ci, column) in enumerate(row):
			if column[0] == '*':
				return (ri, ci)
	return None

def traverseTable(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	queue = Queue()
	followUp = Queue()
	queue.enQueue((x, y))
	first = queue.deQueue()
	while first:
		followUp.enQueue(first)
		x = first[0]
		y = first[1]
		if x - 1 >= 0 and table[y][x - 1][1] == None:
			(table[y][x - 1][1], table[y][x - 1][2]) = computeCount(table, x - 1, y, K, N, M)
			queue.enQueue((x - 1, y))
		if y - 1 >= 0 and table[y - 1][x][1] == None:
			(table[y - 1][x][1], table[y - 1][x][2]) = computeCount(table, x, y - 1, K, N, M)
			queue.enQueue((x, y - 1))
		if x + 1 < M and table[y][x + 1][1] == None:
			(table[y][x + 1][1], table[y][x + 1][2]) = computeCount(table, x + 1, y, K, N, M)
			queue.enQueue((x + 1, y))
		if y + 1 < N and table[y + 1][x][1] == None:
			(table[y + 1][x][1], table[y + 1][x][2]) = computeCount(table, x, y + 1, K, N, M)
			queue.enQueue((x, y + 1))
		first = queue.deQueue()
	second = followUp.deQueue()
	while second:
		x = second[0]
		y = second[1]
		(table[y][x][1], table[y][x][2], changed) = searchNearby(table, x, y, table[y][x][1], table[y][x][2], K, N, M, followUp)
		if changed:
			if x - 1 >= 0:
				if checkNearby(table, x, y, x - 1, y, K):
					followUp.enQueue((x - 1, y))
			if y - 1 >= 0:
				if checkNearby(table, x, y, x, y - 1, K):
					followUp.enQueue((x, y - 1))
			if x + 1 < M:
				if checkNearby(table, x, y, x + 1, y, K):
					followUp.enQueue((x + 1, y))
			if y + 1 < N:
				if checkNearby(table, x, y, x, y + 1, K):
					followUp.enQueue((x, y + 1))
		second = followUp.deQueue()
	if table[0][0][1] == float('inf'):
		return -1
	else:
		return table[0][0][2]

def computeCount(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	ptr = table[y][x]
	if ptr[0] == 'U':
		y -= 1
	elif ptr[0] == 'D':
		y += 1
	elif ptr[0] == 'L':
		x -= 1
	elif ptr[0] == 'R':
		x += 1
	if x < 0 or x >= M or y < 0 or (y >= N):
		return (float('inf'), 0)
	else:
		if table[y][x][1] == None:
			dist = float('inf')
		else:
			dist = table[y][x][1] + 1
		count = table[y][x][2]
		if dist > K:
			(dist, count, changed) = searchNearby(table, startX, startY, dist, count, K, N, M)
		return (dist, count)

def searchNearby(table, x, y, dist, count, K, N, M, queue=None):
	ptr = table[y][x]
	best = count
	prevCount = count
	prevDist = dist
	prevDir = table[y][x][0]
	if y + 1 < N:
		if table[y + 1][x][1] != None and table[y + 1][x][1] + 1 <= K and (table[y + 1][x][2] < best or dist == float('inf')):
			dist = table[y + 1][x][1] + 1
			if table[y][x][3] == 'D':
				best = table[y + 1][x][2]
			else:
				best = table[y + 1][x][2] + 1
			if table[y][x][0] != 'D':
				table[y][x][0] = 'D'
	if x + 1 < M:
		if table[y][x + 1][1] != None and table[y][x + 1][1] + 1 <= K and (table[y][x + 1][2] < best or dist == float('inf')):
			dist = table[y][x + 1][1] + 1
			if table[y][x][3] == 'R':
				best = table[y][x + 1][2]
			else:
				best = table[y][x + 1][2] + 1
			if table[y][x][0] != 'R':
				table[y][x][0] = 'R'
	if y - 1 >= 0:
		if table[y - 1][x][1] != None and table[y - 1][x][1] + 1 <= K and (table[y - 1][x][2] < best or dist == float('inf')):
			dist = table[y - 1][x][1] + 1
			if table[y][x][3] == 'U':
				best = table[y - 1][x][2]
			else:
				best = table[y - 1][x][2] + 1
			if table[y][x][0] != 'U':
				table[y][x][0] = 'U'
	if x - 1 >= 0:
		if table[y][x - 1][1] != None and table[y][x - 1][1] + 1 <= K and (table[y][x - 1][2] < best or dist == float('inf')):
			dist = table[y][x - 1][1] + 1
			if table[y][x][3] == 'L':
				best = table[y][x - 1][2]
			else:
				best = table[y][x - 1][2] + 1
			if table[y][x][0] != 'L':
				table[y][x][0] = 'L'
	if prevCount == best and prevDist == dist and (prevDir == table[y][x][0]):
		changed = False
	else:
		changed = True
	if dist > K:
		return (float('inf'), 0, changed)
	else:
		return (dist, best, changed)

def checkNearby(table, x1, y1, x2, y2, K):
	if table[y1][x1][1] == K:
		return False
	if table[y1][x1][2] < table[y2][x2][2] or table[y2][x2][1] == float('inf'):
		return True
	else:
		return False
NMK = input().strip()
N = int(NMK.split(' ')[0])
M = int(NMK.split(' ')[1])
K = int(NMK.split(' ')[2])
table = []
for row in range(N):
	table.append([])
	for char in input().strip():
		table[row].append([char, None, 0, char])
endpt = findEnd(table)
table[endpt[0]][endpt[1]][1] = 0
print(traverseTable(table, endpt[1], endpt[0], K, N, M))


class Element:

	def __init__(self, data, next):
		self.data = data
		self.next = next

class Queue:

	def __init__(self):
		self.head = None

	def __str__(self):
		ptr = self.head
		if self.head == None:
			string = 'Front < > Back'
		else:
			string = 'Front < '
			while ptr:
				string += '%s ' % str(ptr.data)
				ptr = ptr.next
			string += '> Back'
		return string

	def enQueue(self, data):
		ptr = self.head
		if ptr == None:
			self.head = Element(data, self.head)
		else:
			while ptr.next:
				ptr = ptr.next
			ptr.next = Element(data, None)

	def deQueue(self):
		if self.head == None:
			return None
		ptr = self.head
		self.head = self.head.next
		ptr.next = None
		return ptr.data

def findEnd(table):
	for (ri, row) in enumerate(table):
		for (ci, column) in enumerate(row):
			if column[0] == '*':
				return (ri, ci)
	return None

def traverseTable(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	queue = Queue()
	followUp = Queue()
	queue.enQueue((x, y))
	first = queue.deQueue()
	while first:
		followUp.enQueue(first)
		x = first[0]
		y = first[1]
		if x - 1 >= 0 and table[y][x - 1][1] == None:
			(table[y][x - 1][1], table[y][x - 1][2]) = computeCount(table, x - 1, y, K, N, M)
			queue.enQueue((x - 1, y))
		if y - 1 >= 0 and table[y - 1][x][1] == None:
			(table[y - 1][x][1], table[y - 1][x][2]) = computeCount(table, x, y - 1, K, N, M)
			queue.enQueue((x, y - 1))
		if x + 1 < M and table[y][x + 1][1] == None:
			(table[y][x + 1][1], table[y][x + 1][2]) = computeCount(table, x + 1, y, K, N, M)
			queue.enQueue((x + 1, y))
		if y + 1 < N and table[y + 1][x][1] == None:
			(table[y + 1][x][1], table[y + 1][x][2]) = computeCount(table, x, y + 1, K, N, M)
			queue.enQueue((x, y + 1))
		first = queue.deQueue()
	second = followUp.deQueue()
	while second:
		x = second[0]
		y = second[1]
		(table[y][x][1], table[y][x][2], changed) = searchNearby(table, x, y, table[y][x][1], table[y][x][2], K, N, M, followUp)
		if changed:
			if x - 1 >= 0:
				if checkNearby(table, x, y, x - 1, y, K):
					followUp.enQueue((x - 1, y))
			if y - 1 >= 0:
				if checkNearby(table, x, y, x, y - 1, K):
					followUp.enQueue((x, y - 1))
			if x + 1 < M:
				if checkNearby(table, x, y, x + 1, y, K):
					followUp.enQueue((x + 1, y))
			if y + 1 < N:
				if checkNearby(table, x, y, x, y + 1, K):
					followUp.enQueue((x, y + 1))
		second = followUp.deQueue()
	if table[0][0][1] == float('inf'):
		return -1
	else:
		return table[0][0][2]

def computeCount(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	ptr = table[y][x]
	if ptr[0] == 'U':
		y -= 1
	elif ptr[0] == 'D':
		y += 1
	elif ptr[0] == 'L':
		x -= 1
	elif ptr[0] == 'R':
		x += 1
	if x < 0 or x >= M or y < 0 or (y >= N):
		return (float('inf'), 0)
	else:
		if table[y][x][1] == None:
			dist = float('inf')
		else:
			dist = table[y][x][1] + 1
		count = table[y][x][2]
		if dist > K:
			(dist, count, changed) = searchNearby(table, startX, startY, dist, count, K, N, M)
		return (dist, count)

def searchNearby(table, x, y, dist, count, K, N, M, queue=None):
	ptr = table[y][x]
	best = count
	prevCount = count
	prevDist = dist
	prevDir = table[y][x][0]
	if y + 1 < N:
		if table[y + 1][x][1] != None and table[y + 1][x][1] + 1 <= K and (table[y + 1][x][2] < best or dist == float('inf')):
			dist = table[y + 1][x][1] + 1
			if table[y][x][3] == 'D':
				best = table[y + 1][x][2]
			else:
				best = table[y + 1][x][2] + 1
			if table[y][x][0] != 'D':
				table[y][x][0] = 'D'
	if x + 1 < M:
		if table[y][x + 1][1] != None and table[y][x + 1][1] + 1 <= K and (table[y][x + 1][2] < best or dist == float('inf')):
			dist = table[y][x + 1][1] + 1
			if table[y][x][3] == 'R':
				best = table[y][x + 1][2]
			else:
				best = table[y][x + 1][2] + 1
			if table[y][x][0] != 'R':
				table[y][x][0] = 'R'
	if y - 1 >= 0:
		if table[y - 1][x][1] != None and table[y - 1][x][1] + 1 <= K and (table[y - 1][x][2] < best or dist == float('inf')):
			dist = table[y - 1][x][1] + 1
			if table[y][x][3] == 'U':
				best = table[y - 1][x][2]
			else:
				best = table[y - 1][x][2] + 1
			if table[y][x][0] != 'U':
				table[y][x][0] = 'U'
	if x - 1 >= 0:
		if table[y][x - 1][1] != None and table[y][x - 1][1] + 1 <= K and (table[y][x - 1][2] < best or dist == float('inf')):
			dist = table[y][x - 1][1] + 1
			if table[y][x][3] == 'L':
				best = table[y][x - 1][2]
			else:
				best = table[y][x - 1][2] + 1
			if table[y][x][0] != 'L':
				table[y][x][0] = 'L'
	if prevCount == best and prevDist == dist and (prevDir == table[y][x][0]):
		changed = False
	else:
		changed = True
	if dist > K:
		return (float('inf'), 0, changed)
	else:
		return (dist, best, changed)

def checkNearby(table, x1, y1, x2, y2, K):
	if table[y1][x1][1] == K:
		return False
	if table[y1][x1][2] < table[y2][x2][2] or table[y2][x2][1] == float('inf'):
		return True
	else:
		return False
NMK = input().strip()
N = int(NMK.split(' ')[0])
M = int(NMK.split(' ')[1])
K = int(NMK.split(' ')[2])
table = []
for row in range(N):
	table.append([])
	for char in input().strip():
		table[row].append([char, None, 0, char])
endpt = findEnd(table)
table[endpt[0]][endpt[1]][1] = 0
print(traverseTable(table, endpt[1], endpt[0], K, N, M))


class Element:

	def __init__(self, data, next):
		self.data = data
		self.next = next

class Queue:

	def __init__(self):
		self.head = None

	def __str__(self):
		ptr = self.head
		if self.head == None:
			string = 'Front < > Back'
		else:
			string = 'Front < '
			while ptr:
				string += '%s ' % str(ptr.data)
				ptr = ptr.next
			string += '> Back'
		return string

	def enQueue(self, data):
		ptr = self.head
		if ptr == None:
			self.head = Element(data, self.head)
		else:
			while ptr.next:
				ptr = ptr.next
			ptr.next = Element(data, None)

	def deQueue(self):
		if self.head == None:
			return None
		ptr = self.head
		self.head = self.head.next
		ptr.next = None
		return ptr.data

def findEnd(table):
	for (ri, row) in enumerate(table):
		for (ci, column) in enumerate(row):
			if column[0] == '*':
				return (ri, ci)
	return None

def traverseTable(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	queue = Queue()
	followUp = Queue()
	queue.enQueue((x, y))
	first = queue.deQueue()
	while first:
		followUp.enQueue(first)
		x = first[0]
		y = first[1]
		if x - 1 >= 0 and table[y][x - 1][1] == None:
			(table[y][x - 1][1], table[y][x - 1][2]) = computeCount(table, x - 1, y, K, N, M)
			queue.enQueue((x - 1, y))
		if y - 1 >= 0 and table[y - 1][x][1] == None:
			(table[y - 1][x][1], table[y - 1][x][2]) = computeCount(table, x, y - 1, K, N, M)
			queue.enQueue((x, y - 1))
		if x + 1 < M and table[y][x + 1][1] == None:
			(table[y][x + 1][1], table[y][x + 1][2]) = computeCount(table, x + 1, y, K, N, M)
			queue.enQueue((x + 1, y))
		if y + 1 < N and table[y + 1][x][1] == None:
			(table[y + 1][x][1], table[y + 1][x][2]) = computeCount(table, x, y + 1, K, N, M)
			queue.enQueue((x, y + 1))
		first = queue.deQueue()
	second = followUp.deQueue()
	while second:
		x = second[0]
		y = second[1]
		(table[y][x][1], table[y][x][2], changed) = searchNearby(table, x, y, table[y][x][1], table[y][x][2], K, N, M, followUp)
		if changed:
			if x - 1 >= 0:
				if checkNearby(table, x, y, x - 1, y, K):
					followUp.enQueue((x - 1, y))
			if y - 1 >= 0:
				if checkNearby(table, x, y, x, y - 1, K):
					followUp.enQueue((x, y - 1))
			if x + 1 < M:
				if checkNearby(table, x, y, x + 1, y, K):
					followUp.enQueue((x + 1, y))
			if y + 1 < N:
				if checkNearby(table, x, y, x, y + 1, K):
					followUp.enQueue((x, y + 1))
		second = followUp.deQueue()
	if table[0][0][1] == float('inf'):
		return -1
	else:
		return table[0][0][2]

def computeCount(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	ptr = table[y][x]
	if ptr[0] == 'U':
		y -= 1
	elif ptr[0] == 'D':
		y += 1
	elif ptr[0] == 'L':
		x -= 1
	elif ptr[0] == 'R':
		x += 1
	if x < 0 or x >= M or y < 0 or (y >= N):
		return (float('inf'), 0)
	else:
		if table[y][x][1] == None:
			dist = float('inf')
		else:
			dist = table[y][x][1] + 1
		count = table[y][x][2]
		if dist > K:
			(dist, count, changed) = searchNearby(table, startX, startY, dist, count, K, N, M)
		return (dist, count)

def searchNearby(table, x, y, dist, count, K, N, M, queue=None):
	ptr = table[y][x]
	best = count
	prevCount = count
	prevDist = dist
	prevDir = table[y][x][0]
	if y + 1 < N:
		if table[y + 1][x][1] != None and table[y + 1][x][1] + 1 <= K and (table[y + 1][x][2] < best or dist == float('inf')):
			dist = table[y + 1][x][1] + 1
			if table[y][x][3] == 'D':
				best = table[y + 1][x][2]
			else:
				best = table[y + 1][x][2] + 1
			if table[y][x][0] != 'D':
				table[y][x][0] = 'D'
	if x + 1 < M:
		if table[y][x + 1][1] != None and table[y][x + 1][1] + 1 <= K and (table[y][x + 1][2] < best or dist == float('inf')):
			dist = table[y][x + 1][1] + 1
			if table[y][x][3] == 'R':
				best = table[y][x + 1][2]
			else:
				best = table[y][x + 1][2] + 1
			if table[y][x][0] != 'R':
				table[y][x][0] = 'R'
	if y - 1 >= 0:
		if table[y - 1][x][1] != None and table[y - 1][x][1] + 1 <= K and (table[y - 1][x][2] < best or dist == float('inf')):
			dist = table[y - 1][x][1] + 1
			if table[y][x][3] == 'U':
				best = table[y - 1][x][2]
			else:
				best = table[y - 1][x][2] + 1
			if table[y][x][0] != 'U':
				table[y][x][0] = 'U'
	if x - 1 >= 0:
		if table[y][x - 1][1] != None and table[y][x - 1][1] + 1 <= K and (table[y][x - 1][2] < best or dist == float('inf')):
			dist = table[y][x - 1][1] + 1
			if table[y][x][3] == 'L':
				best = table[y][x - 1][2]
			else:
				best = table[y][x - 1][2] + 1
			if table[y][x][0] != 'L':
				table[y][x][0] = 'L'
	if prevCount == best and prevDist == dist and (prevDir == table[y][x][0]):
		changed = False
	else:
		changed = True
	if dist > K:
		return (float('inf'), 0, changed)
	else:
		return (dist, best, changed)

def checkNearby(table, x1, y1, x2, y2, K):
	if table[y1][x1][1] == K:
		return False
	if table[y1][x1][2] < table[y2][x2][2] or table[y2][x2][1] == float('inf'):
		return True
	else:
		return False
NMK = input().strip()
N = int(NMK.split(' ')[0])
M = int(NMK.split(' ')[1])
K = int(NMK.split(' ')[2])
table = []
for row in range(N):
	table.append([])
	for char in input().strip():
		table[row].append([char, None, 0, char])
endpt = findEnd(table)
table[endpt[0]][endpt[1]][1] = 0
print(traverseTable(table, endpt[1], endpt[0], K, N, M))


class Element:

	def __init__(self, data, next):
		self.data = data
		self.next = next

class Queue:

	def __init__(self):
		self.head = None

	def __str__(self):
		ptr = self.head
		if self.head == None:
			string = 'Front < > Back'
		else:
			string = 'Front < '
			while ptr:
				string += '%s ' % str(ptr.data)
				ptr = ptr.next
			string += '> Back'
		return string

	def enQueue(self, data):
		ptr = self.head
		if ptr == None:
			self.head = Element(data, self.head)
		else:
			while ptr.next:
				ptr = ptr.next
			ptr.next = Element(data, None)

	def deQueue(self):
		if self.head == None:
			return None
		ptr = self.head
		self.head = self.head.next
		ptr.next = None
		return ptr.data

def findEnd(table):
	for (ri, row) in enumerate(table):
		for (ci, column) in enumerate(row):
			if column[0] == '*':
				return (ri, ci)
	return None

def traverseTable(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	queue = Queue()
	followUp = Queue()
	queue.enQueue((x, y))
	first = queue.deQueue()
	while first:
		followUp.enQueue(first)
		x = first[0]
		y = first[1]
		if x - 1 >= 0 and table[y][x - 1][1] == None:
			(table[y][x - 1][1], table[y][x - 1][2]) = computeCount(table, x - 1, y, K, N, M)
			queue.enQueue((x - 1, y))
		if y - 1 >= 0 and table[y - 1][x][1] == None:
			(table[y - 1][x][1], table[y - 1][x][2]) = computeCount(table, x, y - 1, K, N, M)
			queue.enQueue((x, y - 1))
		if x + 1 < M and table[y][x + 1][1] == None:
			(table[y][x + 1][1], table[y][x + 1][2]) = computeCount(table, x + 1, y, K, N, M)
			queue.enQueue((x + 1, y))
		if y + 1 < N and table[y + 1][x][1] == None:
			(table[y + 1][x][1], table[y + 1][x][2]) = computeCount(table, x, y + 1, K, N, M)
			queue.enQueue((x, y + 1))
		first = queue.deQueue()
	second = followUp.deQueue()
	while second:
		x = second[0]
		y = second[1]
		(table[y][x][1], table[y][x][2], changed) = searchNearby(table, x, y, table[y][x][1], table[y][x][2], K, N, M, followUp)
		if changed:
			if x - 1 >= 0:
				if checkNearby(table, x, y, x - 1, y, K):
					followUp.enQueue((x - 1, y))
			if y - 1 >= 0:
				if checkNearby(table, x, y, x, y - 1, K):
					followUp.enQueue((x, y - 1))
			if x + 1 < M:
				if checkNearby(table, x, y, x + 1, y, K):
					followUp.enQueue((x + 1, y))
			if y + 1 < N:
				if checkNearby(table, x, y, x, y + 1, K):
					followUp.enQueue((x, y + 1))
		second = followUp.deQueue()
	if table[0][0][1] == float('inf'):
		return -1
	else:
		return table[0][0][2]

def computeCount(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	ptr = table[y][x]
	if ptr[0] == 'U':
		y -= 1
	elif ptr[0] == 'D':
		y += 1
	elif ptr[0] == 'L':
		x -= 1
	elif ptr[0] == 'R':
		x += 1
	if x < 0 or x >= M or y < 0 or (y >= N):
		return (float('inf'), 0)
	else:
		if table[y][x][1] == None:
			dist = float('inf')
		else:
			dist = table[y][x][1] + 1
		count = table[y][x][2]
		if dist > K:
			(dist, count, changed) = searchNearby(table, startX, startY, dist, count, K, N, M)
		return (dist, count)

def searchNearby(table, x, y, dist, count, K, N, M, queue=None):
	ptr = table[y][x]
	best = count
	prevCount = count
	prevDist = dist
	prevDir = table[y][x][0]
	if y + 1 < N:
		if table[y + 1][x][1] != None and table[y + 1][x][1] + 1 <= K and (table[y + 1][x][2] < best or dist == float('inf')):
			dist = table[y + 1][x][1] + 1
			if table[y][x][3] == 'D':
				best = table[y + 1][x][2]
			else:
				best = table[y + 1][x][2] + 1
			if table[y][x][0] != 'D':
				table[y][x][0] = 'D'
	if x + 1 < M:
		if table[y][x + 1][1] != None and table[y][x + 1][1] + 1 <= K and (table[y][x + 1][2] < best or dist == float('inf')):
			dist = table[y][x + 1][1] + 1
			if table[y][x][3] == 'R':
				best = table[y][x + 1][2]
			else:
				best = table[y][x + 1][2] + 1
			if table[y][x][0] != 'R':
				table[y][x][0] = 'R'
	if y - 1 >= 0:
		if table[y - 1][x][1] != None and table[y - 1][x][1] + 1 <= K and (table[y - 1][x][2] < best or dist == float('inf')):
			dist = table[y - 1][x][1] + 1
			if table[y][x][3] == 'U':
				best = table[y - 1][x][2]
			else:
				best = table[y - 1][x][2] + 1
			if table[y][x][0] != 'U':
				table[y][x][0] = 'U'
	if x - 1 >= 0:
		if table[y][x - 1][1] != None and table[y][x - 1][1] + 1 <= K and (table[y][x - 1][2] < best or dist == float('inf')):
			dist = table[y][x - 1][1] + 1
			if table[y][x][3] == 'L':
				best = table[y][x - 1][2]
			else:
				best = table[y][x - 1][2] + 1
			if table[y][x][0] != 'L':
				table[y][x][0] = 'L'
	if prevCount == best and prevDist == dist and (prevDir == table[y][x][0]):
		changed = False
	else:
		changed = True
	if dist > K:
		return (float('inf'), 0, changed)
	else:
		return (dist, best, changed)

def checkNearby(table, x1, y1, x2, y2, K):
	if table[y1][x1][1] == K:
		return False
	if table[y1][x1][2] < table[y2][x2][2] or table[y2][x2][1] == float('inf'):
		return True
	else:
		return False
NMK = input().strip()
N = int(NMK.split(' ')[0])
M = int(NMK.split(' ')[1])
K = int(NMK.split(' ')[2])
table = []
for row in range(N):
	table.append([])
	for char in input().strip():
		table[row].append([char, None, 0, char])
endpt = findEnd(table)
table[endpt[0]][endpt[1]][1] = 0
print(traverseTable(table, endpt[1], endpt[0], K, N, M))


from collections import defaultdict
(height, width, k) = (int(i) for i in input().split())
board = [input() for i in range(height)]

class Point:

	def __init__(self, row, col, letter):
		self.reachable = set()
		self.row = row
		self.col = col
		self.letter = letter
		self.distances = {}

	def __repr__(self):
		return self.letter + str(self.distances)
points = []
for row in range(height):
	rowlist = []
	points.append(rowlist)
	for col in range(width):
		point = Point(row, col, board[row][col])
		rowlist.append(point)
		if board[row][col] == '*':
			dest = point

def adj_set(point):
	adj = set()
	if point.row > 0:
		adj.add(points[point.row - 1][point.col])
	if point.row < height - 1:
		adj.add(points[point.row + 1][point.col])
	if point.col > 0:
		adj.add(points[point.row][point.col - 1])
	if point.col < width - 1:
		adj.add(points[point.row][point.col + 1])
	return adj

def set_reachable(point):
	adj = adj_set(point)
	for a in adj:
		if a.row > point.row and a.letter == 'U' or (a.row < point.row and a.letter == 'D') or (a.col > point.col and a.letter == 'L') or (a.col < point.col and a.letter == 'R'):
			point.reachable.add(a)
for row in points:
	for point in row:
		set_reachable(point)

def walk_paths(point=dest, movessofar=0, changessofar=0):
	if movessofar > k:
		return
	if changessofar > dest.row + dest.col:
		return
	keystodelete = set()
	for (changes, distance) in point.distances.items():
		if changes <= changessofar and distance <= movessofar:
			return
		if changes > changessofar and distance >= movessofar:
			keystodelete.add(changes)
	point.distances[changessofar] = movessofar
	for key in keystodelete:
		del point.distances[key]
	for a in adj_set(point):
		if a in point.reachable:
			walk_paths(a, movessofar + 1, changessofar)
		else:
			walk_paths(a, movessofar + 1, changessofar + 1)
walk_paths(dest)
starting = points[0][0]
if not starting.distances:
	print(-1)
else:
	print(min(starting.distances.keys()))


def find_path(i, j, plen, cost):
	if i >= N or j >= M or i < 0 or (j < 0) or (plen > K) or (cost >= cost_mat[i][j]):
		return
	cost_mat[i][j] = cost
	find_path(i - 1, j, plen + 1, cost + 1 - int(board[i][j] == 'U'))
	find_path(i + 1, j, plen + 1, cost + 1 - int(board[i][j] == 'D'))
	find_path(i, j - 1, plen + 1, cost + 1 - int(board[i][j] == 'L'))
	find_path(i, j + 1, plen + 1, cost + 1 - int(board[i][j] == 'R'))

def find_exit(board):
	for i in range(N):
		if '*' in board[i]:
			return (i, board[i].index('*'))
(N, M, K) = map(int, input().split())
board = []
cost_mat = []
for i in range(N):
	board.append([k for k in input()])
	cost_mat.append([N * M] * M)
find_path(0, 0, 0, 0)
(i, j) = find_exit(board)
print(cost_mat[i][j] if cost_mat[i][j] != N * M else -1)


(n, m, k) = map(int, input().split())
board = []
star = None
for r in range(n):
	board.append(input())
	if '*' in board[-1]:
		star = (r + 1, board[-1].index('*') + 1)

def addState(state, pos, val):
	m = val
	if pos in state:
		m = state[pos]
	state[pos] = min(m, val)
coin = [{(1, 1): 0}]
for step in range(1, k + 1):
	(current, state) = (coin[-1], {})
	for pos in current:
		if pos == star:
			addState(state, star, current[pos])
		for (dx, dy, f) in [(1, 0, 'D'), (0, 1, 'R'), (-1, 0, 'U'), (0, -1, 'L')]:
			newPos = (pos[0] + dx, pos[1] + dy)
			if newPos[0] < 1 or newPos[0] > n or newPos[1] < 1 or (newPos[1] > m):
				continue
			addState(state, newPos, current[pos] + (0 if board[pos[0] - 1][pos[1] - 1] == f else 1))
	coin.append(state)
print(coin[-1][star] if star in coin[-1] else -1)


import sys
import collections

def dist(p1, p2):
	return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
[n, m, k] = [int(X) for X in sys.stdin.readline().split()]
table = dict()
for i in range(1, n + 1):
	for (j, letter) in enumerate(sys.stdin.readline().strip()):
		if letter == '*':
			goal = (i, j + 1)
		table[i, j + 1] = letter
cache = collections.defaultdict(lambda : 105)

def dist(p):
	return abs(p[0] - goal[0]) + abs(p[1] - goal[1])

def solve(position, t, num_changes):
	cache[position] = num_changes
	letter = table[position]
	if position == goal:
		return num_changes
	else:
		i = position[0]
		j = position[1]
		solutions = list()
		if i > 1 and cache[i - 1, j] > num_changes + (letter != 'U') and (dist((i - 1, j)) < k - t):
			solutions.append(solve((i - 1, j), t + 1, num_changes + (letter != 'U')))
		if j < m and cache[i, j + 1] > num_changes + (letter != 'R') and (dist((i, j + 1)) < k - t):
			solutions.append(solve((i, j + 1), t + 1, num_changes + (letter != 'R')))
		if i < n and cache[i + 1, j] > num_changes + (letter != 'D') and (dist((i + 1, j)) < k - t):
			solutions.append(solve((i + 1, j), t + 1, num_changes + (letter != 'D')))
		if j > 1 and cache[i, j - 1] > num_changes + (letter != 'L') and (dist((i, j - 1)) < k - t):
			solutions.append(solve((i, j - 1), t + 1, num_changes + (letter != 'L')))
		try:
			return min([solution for solution in solutions if solution is not None])
		except ValueError:
			return None
solution = solve((1, 1), 0, 0)
print(solution if solution is not None else -1)


import sys, math, copy
data = sys.stdin.readlines()
(N, M, K) = [int(n) for n in data[0].split()]
iStar = [i for (i, line) in enumerate(data[1:]) if line.find('*') >= 0][0]
jStar = data[iStar + 1].find('*')
cell = [[l for l in line.strip()] for line in data[1:]]
al = [l for line in data[1:] for l in line.strip()]
imax = N - 1
jmax = M - 1
runsInf = imax + jmax
nCells = N * M

def run(K):
	i = 0
	j = 0
	ok = False
	for t in range(K + 1):
		letter = cell[i][j]
		if letter == '*':
			ok = True
			break
		if letter == 'U':
			if i == 0:
				break
			i -= 1
		elif letter == 'L':
			if j == 0:
				break
			j -= 1
		elif letter == 'D':
			if i == imax:
				break
			i += 1
		elif letter == 'R':
			if j == jmax:
				break
			j += 1
	return (ok, t)
for minPathLen in range(runsInf):
	distInf = N * M + N + M
	dist = [distInf] * nCells
	dist2 = [-1] * nCells
	dist3 = [0] * nCells
	prev = [-1] * nCells
	vTarget = iStar * M + jStar
	dist[0] = 0
	dist2[0] = 0
	Q = [True] * nCells
	while any(Q):
		u = None
		mindist = distInf + 1
		for (i, q) in enumerate(Q):
			if q and mindist > dist[i]:
				mindist = dist[i]
				u = i
		if u is None:
			break
		if u == vTarget:
			break
		if dist[u] == distInf:
			break
		alt2 = dist2[u] + 1
		Q[u] = False
		if alt2 > K:
			continue
		letter = al[u]
		i = u // M
		j = u % M
		for (x, y, d, l) in ((i, j + 1, 1, 'R'), (i - 1, j, -M, 'U'), (i, j - 1, -1, 'L'), (i + 1, j, M, 'D')):
			v = u + d
			if x >= 0 and x < N and (y >= 0) and (y < M) and Q[v]:
				distuv = 0 if letter == l else 1
				alt3 = dist[u] + distuv
				alt = alt3
				if minPathLen and alt < minPathLen:
					alt = minPathLen
				closer = alt < dist[v]
				if closer:
					dist[v] = alt
					prev[v] = u
					dist2[v] = alt2
					dist3[v] = alt3
	if u == vTarget and dist2[u] <= K and (dist[u] != distInf):
		break
if u != vTarget:
	ops = -1
else:
	ops = dist3[u]
(ok, runs) = run(K)
ok = True
print(ops if ok else -1)


class Element:

	def __init__(self, data, next):
		self.data = data
		self.next = next

class Queue:

	def __init__(self):
		self.head = None

	def __str__(self):
		ptr = self.head
		if self.head == None:
			string = 'Front < > Back'
		else:
			string = 'Front < '
			while ptr:
				string += '%s ' % str(ptr.data)
				ptr = ptr.next
			string += '> Back'
		return string

	def enQueue(self, data):
		ptr = self.head
		if ptr == None:
			self.head = Element(data, self.head)
		else:
			while ptr.next:
				ptr = ptr.next
			ptr.next = Element(data, None)

	def deQueue(self):
		if self.head == None:
			return None
		ptr = self.head
		self.head = self.head.next
		ptr.next = None
		return ptr.data

def findEnd(table):
	for (ri, row) in enumerate(table):
		for (ci, column) in enumerate(row):
			if column[0] == '*':
				return (ri, ci)
	return None

def traverseTable(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	queue = Queue()
	followUp = Queue()
	queue.enQueue((x, y))
	first = queue.deQueue()
	while first:
		followUp.enQueue(first)
		x = first[0]
		y = first[1]
		if x - 1 >= 0 and table[y][x - 1][1] == None:
			(table[y][x - 1][1], table[y][x - 1][2]) = computeCount(table, x - 1, y, K, N, M)
			queue.enQueue((x - 1, y))
		if y - 1 >= 0 and table[y - 1][x][1] == None:
			(table[y - 1][x][1], table[y - 1][x][2]) = computeCount(table, x, y - 1, K, N, M)
			queue.enQueue((x, y - 1))
		if x + 1 < M and table[y][x + 1][1] == None:
			(table[y][x + 1][1], table[y][x + 1][2]) = computeCount(table, x + 1, y, K, N, M)
			queue.enQueue((x + 1, y))
		if y + 1 < N and table[y + 1][x][1] == None:
			(table[y + 1][x][1], table[y + 1][x][2]) = computeCount(table, x, y + 1, K, N, M)
			queue.enQueue((x, y + 1))
		first = queue.deQueue()
	second = followUp.deQueue()
	while second:
		x = second[0]
		y = second[1]
		(table[y][x][1], table[y][x][2], changed) = searchNearby(table, x, y, table[y][x][1], table[y][x][2], K, N, M, followUp)
		if changed:
			if x - 1 >= 0:
				if checkNearby(table, x, y, x - 1, y, K):
					followUp.enQueue((x - 1, y))
			if y - 1 >= 0:
				if checkNearby(table, x, y, x, y - 1, K):
					followUp.enQueue((x, y - 1))
			if x + 1 < M:
				if checkNearby(table, x, y, x + 1, y, K):
					followUp.enQueue((x + 1, y))
			if y + 1 < N:
				if checkNearby(table, x, y, x, y + 1, K):
					followUp.enQueue((x, y + 1))
		second = followUp.deQueue()
	if table[0][0][1] == float('inf'):
		return -1
	else:
		return table[0][0][2]

def computeCount(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	ptr = table[y][x]
	if ptr[0] == 'U':
		y -= 1
	elif ptr[0] == 'D':
		y += 1
	elif ptr[0] == 'L':
		x -= 1
	elif ptr[0] == 'R':
		x += 1
	if x < 0 or x >= M or y < 0 or (y >= N):
		return (float('inf'), 0)
	else:
		if table[y][x][1] == None:
			dist = float('inf')
		else:
			dist = table[y][x][1] + 1
		count = table[y][x][2]
		if dist > K:
			(dist, count, changed) = searchNearby(table, startX, startY, dist, count, K, N, M)
		return (dist, count)

def searchNearby(table, x, y, dist, count, K, N, M, queue=None):
	ptr = table[y][x]
	best = count
	prevCount = count
	prevDist = dist
	prevDir = table[y][x][0]
	if y + 1 < N:
		if table[y + 1][x][1] != None and table[y + 1][x][1] + 1 <= K and (table[y + 1][x][2] < best or dist == float('inf')):
			dist = table[y + 1][x][1] + 1
			if table[y][x][3] == 'D':
				best = table[y + 1][x][2]
			else:
				best = table[y + 1][x][2] + 1
			if table[y][x][0] != 'D':
				table[y][x][0] = 'D'
	if x + 1 < M:
		if table[y][x + 1][1] != None and table[y][x + 1][1] + 1 <= K and (table[y][x + 1][2] < best or dist == float('inf')):
			dist = table[y][x + 1][1] + 1
			if table[y][x][3] == 'R':
				best = table[y][x + 1][2]
			else:
				best = table[y][x + 1][2] + 1
			if table[y][x][0] != 'R':
				table[y][x][0] = 'R'
	if y - 1 >= 0:
		if table[y - 1][x][1] != None and table[y - 1][x][1] + 1 <= K and (table[y - 1][x][2] < best or dist == float('inf')):
			dist = table[y - 1][x][1] + 1
			if table[y][x][3] == 'U':
				best = table[y - 1][x][2]
			else:
				best = table[y - 1][x][2] + 1
			if table[y][x][0] != 'U':
				table[y][x][0] = 'U'
	if x - 1 >= 0:
		if table[y][x - 1][1] != None and table[y][x - 1][1] + 1 <= K and (table[y][x - 1][2] < best or dist == float('inf')):
			dist = table[y][x - 1][1] + 1
			if table[y][x][3] == 'L':
				best = table[y][x - 1][2]
			else:
				best = table[y][x - 1][2] + 1
			if table[y][x][0] != 'L':
				table[y][x][0] = 'L'
	if prevCount == best and prevDist == dist and (prevDir == table[y][x][0]):
		changed = False
	else:
		changed = True
	if dist > K:
		return (float('inf'), 0, changed)
	else:
		return (dist, best, changed)

def checkNearby(table, x1, y1, x2, y2, K):
	if table[y1][x1][1] == K:
		return False
	if table[y1][x1][2] < table[y2][x2][2] or table[y2][x2][1] == float('inf'):
		return True
	else:
		return False
NMK = input().strip()
N = int(NMK.split(' ')[0])
M = int(NMK.split(' ')[1])
K = int(NMK.split(' ')[2])
table = []
for row in range(N):
	table.append([])
	for char in input().strip():
		table[row].append([char, None, 0, char])
endpt = findEnd(table)
table[endpt[0]][endpt[1]][1] = 0
print(traverseTable(table, endpt[1], endpt[0], K, N, M))


def fork0(i, j):
	if i == need_x and j == need_y:
		return 0
	return -1

def get_distance(i, j):
	d = abs(need_x - i) + abs(need_y - i)
	return d

def getnewp(i, j, let):
	new_i = i
	new_j = j
	if let == 'D':
		new_i += 1
	if let == 'U':
		new_i -= 1
	if let == 'R':
		new_j += 1
	if let == 'L':
		new_j -= 1
	return (new_i, new_j)

def my_func(k):
	queue = []
	queue.append((k, 0, 0, 0))
	while len(queue) > 0:
		(k, i, j, cur) = queue.pop(0)
		if i < 0 or i >= n or j < 0 or (j >= m):
			continue
		if k == 0:
			res = fork0(i, j)
			if res != -1:
				return cur
			continue
		cur_letter = desk[i][j]
		if cur_letter == '*':
			return cur
		d = get_distance(i, j)
		if d > k:
			continue
		if count_desk[i][j] > 0:
			continue
		else:
			count_desk[i][j] = k
		(new_i, new_j) = getnewp(i, j, cur_letter)
		queue.insert(0, (k - 1, new_i, new_j, cur))
		for let in all_letter:
			if let != cur_letter:
				(new_i, new_j) = getnewp(i, j, let)
				queue.append((k - 1, new_i, new_j, cur + 1))
	return -1
all_letter = ['D', 'U', 'R', 'L']
(n, m, k) = [int(i) for i in input().strip().split()]
desk = []
count_desk = []
for i in range(n):
	count_desk.append([0] * m)
need_x = 0
need_y = 0
for i in range(n):
	row = [c for c in input().strip()]
	desk.append(row)
	if '*' in row:
		need_x = i
		need_y = row.index('*')
print(my_func(k))


from itertools import product
(n, m, k) = map(int, input().split())
dataz = []
star = None
for i in range(n):
	s = input()
	st = s.find('*')
	if st >= 0:
		star = (i, st)
	dataz.append(s)
costs = {'U': (0, 1, 1, 1), 'D': (1, 0, 1, 1), 'L': (1, 1, 0, 1), 'R': (1, 1, 1, 0)}
plist = list(product(range(n), range(m)))
dists = {t: k + 1 for t in plist}
dists[0, 0] = 0
for t in range(k):
	nd = {t: k + 1 for t in plist}
	nd[star] = dists[star]
	for p in plist:
		if p == star:
			continue
		(x, y) = p
		(u, d, l, r) = costs[dataz[x][y]]
		if x > 0:
			nd[x - 1, y] = min(nd[x - 1, y], dists[x, y] + u)
		if x < n - 1:
			nd[x + 1, y] = min(nd[x + 1, y], dists[x, y] + d)
		if y > 0:
			nd[x, y - 1] = min(nd[x, y - 1], dists[x, y] + l)
		if y < m - 1:
			nd[x, y + 1] = min(nd[x, y + 1], dists[x, y] + r)
	dists = nd
if dists[star] == k + 1:
	print('-1')
else:
	print(dists[star])


class Element:

	def __init__(self, data, next):
		self.data = data
		self.next = next

class Queue:

	def __init__(self):
		self.head = None

	def __str__(self):
		ptr = self.head
		if self.head == None:
			string = 'Front < > Back'
		else:
			string = 'Front < '
			while ptr:
				string += '%s ' % str(ptr.data)
				ptr = ptr.next
			string += '> Back'
		return string

	def enQueue(self, data):
		ptr = self.head
		if ptr == None:
			self.head = Element(data, self.head)
		else:
			while ptr.next:
				ptr = ptr.next
			ptr.next = Element(data, None)

	def deQueue(self):
		if self.head == None:
			return None
		ptr = self.head
		self.head = self.head.next
		ptr.next = None
		return ptr.data

def findEnd(table):
	for (ri, row) in enumerate(table):
		for (ci, column) in enumerate(row):
			if column[0] == '*':
				return (ri, ci)
	return None

def traverseTable(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	queue = Queue()
	followUp = Queue()
	queue.enQueue((x, y))
	first = queue.deQueue()
	while first:
		followUp.enQueue(first)
		x = first[0]
		y = first[1]
		if x - 1 >= 0 and table[y][x - 1][1] == None:
			(table[y][x - 1][1], table[y][x - 1][2]) = computeCount(table, x - 1, y, K, N, M)
			queue.enQueue((x - 1, y))
		if y - 1 >= 0 and table[y - 1][x][1] == None:
			(table[y - 1][x][1], table[y - 1][x][2]) = computeCount(table, x, y - 1, K, N, M)
			queue.enQueue((x, y - 1))
		if x + 1 < M and table[y][x + 1][1] == None:
			(table[y][x + 1][1], table[y][x + 1][2]) = computeCount(table, x + 1, y, K, N, M)
			queue.enQueue((x + 1, y))
		if y + 1 < N and table[y + 1][x][1] == None:
			(table[y + 1][x][1], table[y + 1][x][2]) = computeCount(table, x, y + 1, K, N, M)
			queue.enQueue((x, y + 1))
		first = queue.deQueue()
	second = followUp.deQueue()
	while second:
		x = second[0]
		y = second[1]
		(table[y][x][1], table[y][x][2], changed) = searchNearby(table, x, y, table[y][x][1], table[y][x][2], K, N, M, followUp)
		if changed:
			if x - 1 >= 0:
				if checkNearby(table, x, y, x - 1, y, K):
					followUp.enQueue((x - 1, y))
			if y - 1 >= 0:
				if checkNearby(table, x, y, x, y - 1, K):
					followUp.enQueue((x, y - 1))
			if x + 1 < M:
				if checkNearby(table, x, y, x + 1, y, K):
					followUp.enQueue((x + 1, y))
			if y + 1 < N:
				if checkNearby(table, x, y, x, y + 1, K):
					followUp.enQueue((x, y + 1))
		second = followUp.deQueue()
	if table[0][0][1] == float('inf'):
		return -1
	else:
		return table[0][0][2]

def computeCount(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	ptr = table[y][x]
	if ptr[0] == 'U':
		y -= 1
	elif ptr[0] == 'D':
		y += 1
	elif ptr[0] == 'L':
		x -= 1
	elif ptr[0] == 'R':
		x += 1
	if x < 0 or x >= M or y < 0 or (y >= N):
		return (float('inf'), 0)
	else:
		if table[y][x][1] == None:
			dist = float('inf')
		else:
			dist = table[y][x][1] + 1
		count = table[y][x][2]
		if dist > K:
			(dist, count, changed) = searchNearby(table, startX, startY, dist, count, K, N, M)
		return (dist, count)

def searchNearby(table, x, y, dist, count, K, N, M, queue=None):
	ptr = table[y][x]
	best = count
	prevCount = count
	prevDist = dist
	prevDir = table[y][x][0]
	if y + 1 < N:
		if table[y + 1][x][1] != None and table[y + 1][x][1] + 1 <= K and (table[y + 1][x][2] < best or dist == float('inf')):
			dist = table[y + 1][x][1] + 1
			if table[y][x][3] == 'D':
				best = table[y + 1][x][2]
			else:
				best = table[y + 1][x][2] + 1
			if table[y][x][0] != 'D':
				table[y][x][0] = 'D'
	if x + 1 < M:
		if table[y][x + 1][1] != None and table[y][x + 1][1] + 1 <= K and (table[y][x + 1][2] < best or dist == float('inf')):
			dist = table[y][x + 1][1] + 1
			if table[y][x][3] == 'R':
				best = table[y][x + 1][2]
			else:
				best = table[y][x + 1][2] + 1
			if table[y][x][0] != 'R':
				table[y][x][0] = 'R'
	if y - 1 >= 0:
		if table[y - 1][x][1] != None and table[y - 1][x][1] + 1 <= K and (table[y - 1][x][2] < best or dist == float('inf')):
			dist = table[y - 1][x][1] + 1
			if table[y][x][3] == 'U':
				best = table[y - 1][x][2]
			else:
				best = table[y - 1][x][2] + 1
			if table[y][x][0] != 'U':
				table[y][x][0] = 'U'
	if x - 1 >= 0:
		if table[y][x - 1][1] != None and table[y][x - 1][1] + 1 <= K and (table[y][x - 1][2] < best or dist == float('inf')):
			dist = table[y][x - 1][1] + 1
			if table[y][x][3] == 'L':
				best = table[y][x - 1][2]
			else:
				best = table[y][x - 1][2] + 1
			if table[y][x][0] != 'L':
				table[y][x][0] = 'L'
	if prevCount == best and prevDist == dist and (prevDir == table[y][x][0]):
		changed = False
	else:
		changed = True
	if dist > K:
		return (float('inf'), 0, changed)
	else:
		return (dist, best, changed)

def checkNearby(table, x1, y1, x2, y2, K):
	if table[y1][x1][1] == K:
		return False
	if table[y1][x1][2] < table[y2][x2][2] or table[y2][x2][1] == float('inf'):
		return True
	else:
		return False
NMK = input().strip()
N = int(NMK.split(' ')[0])
M = int(NMK.split(' ')[1])
K = int(NMK.split(' ')[2])
table = []
for row in range(N):
	table.append([])
	for char in input().strip():
		table[row].append([char, None, 0, char])
endpt = findEnd(table)
table[endpt[0]][endpt[1]][1] = 0
print(traverseTable(table, endpt[1], endpt[0], K, N, M))


import sys

def is_dead_step(trow, tcol, step, K, row, col):
	dist = abs(row - trow) + abs(col - tcol)
	return step + dist > K

def dfs(step, K, board, cur_changes, row, col, min_changes, max_row, max_col, trow, tcol):
	if step <= K and 0 <= row < max_row and (0 <= col < max_col) and (cur_changes < min_changes[row][col]) and (not is_dead_step(trow, tcol, step, K, row, col)):
		min_changes[row][col] = cur_changes
		grid = board[row][col]
		dfs(step + 1, K, board, cur_changes + int(grid != 'L'), row, col - 1, min_changes, max_row, max_col, trow, tcol)
		dfs(step + 1, K, board, cur_changes + int(grid != 'R'), row, col + 1, min_changes, max_row, max_col, trow, tcol)
		dfs(step + 1, K, board, cur_changes + int(grid != 'U'), row - 1, col, min_changes, max_row, max_col, trow, tcol)
		dfs(step + 1, K, board, cur_changes + int(grid != 'D'), row + 1, col, min_changes, max_row, max_col, trow, tcol)
(N, M, K) = [int(x) for x in sys.stdin.readline().split()]
board = sys.stdin.read().splitlines()
min_changes = []
for i in range(N):
	min_changes.append([9999] * M)
for i in range(N):
	for j in range(M):
		if board[i][j] == '*':
			(trow, tcol) = (i, j)
			break
dfs(0, K, board, 0, 0, 0, min_changes, N, M, trow, tcol)
changes = min_changes[trow][tcol]
if changes == 9999:
	print(-1)
else:
	print(changes)


(n, m, K) = [int(x) for x in input().split()]
grid = [list(input()) for x in range(n)]
mem = {}

def dp(cell, k, memo):
	if k < 0 or cell[0] < 0 or cell[0] == n or (cell[1] < 0) or (cell[1] == m):
		return K + 1
	if grid[cell[0]][cell[1]] == '*':
		return 0
	if (cell[0], cell[1], k) not in memo:
		paths = []
		paths.append(dp((cell[0], cell[1] - 1), k - 1, memo) + (grid[cell[0]][cell[1]] != 'L'))
		paths.append(dp((cell[0] - 1, cell[1]), k - 1, memo) + (grid[cell[0]][cell[1]] != 'U'))
		paths.append(dp((cell[0], cell[1] + 1), k - 1, memo) + (grid[cell[0]][cell[1]] != 'R'))
		paths.append(dp((cell[0] + 1, cell[1]), k - 1, memo) + (grid[cell[0]][cell[1]] != 'D'))
		memo[cell[0], cell[1], k] = min(paths)
	return memo[cell[0], cell[1], k]
foo = dp((0, 0), K, mem)
print(foo if foo <= K else -1)


(n, m, k) = map(int, input().split())
arr = []
for i in range(n):
	arr.append(list(input()))

def inbound(x, y):
	return x >= 0 and x <= n - 1 and (y >= 0) and (y <= m - 1)
starX = 0
starY = 0
min = [[[-1] * (k + 1) for i in range(m)] for j in range(n)]
min[0][0][0] = 0
for f in range(k):
	for i in range(n):
		for j in range(m):
			if arr[i][j] != '*' and min[i][j][f] != -1:
				r = min[i][j][f] + 1
				l = r
				d = r
				u = r
				if arr[i][j] == 'R':
					r -= 1
				elif arr[i][j] == 'L':
					l -= 1
				elif arr[i][j] == 'D':
					d -= 1
				elif arr[i][j] == 'U':
					u -= 1
				if inbound(i, j + 1):
					if min[i][j + 1][f + 1] < 0:
						min[i][j + 1][f + 1] = r
					elif min[i][j + 1][f + 1] > r:
						min[i][j + 1][f + 1] = r
				if inbound(i, j - 1):
					if min[i][j - 1][f + 1] < 0:
						min[i][j - 1][f + 1] = l
					elif min[i][j - 1][f + 1] > l:
						min[i][j - 1][f + 1] = l
				if inbound(i + 1, j):
					if min[i + 1][j][f + 1] < 0:
						min[i + 1][j][f + 1] = d
					elif min[i + 1][j][f + 1] > d:
						min[i + 1][j][f + 1] = d
				if inbound(i - 1, j):
					if min[i - 1][j][f + 1] < 0:
						min[i - 1][j][f + 1] = u
					elif min[i - 1][j][f + 1] > u:
						min[i - 1][j][f + 1] = u
			elif arr[i][j] == '*':
				starX = i
				starY = j
minK = -1
for i in range(k + 1):
	if min[starX][starY][i] > -1:
		if minK > -1:
			if min[starX][starY][i] < minK:
				minK = min[starX][starY][i]
		else:
			minK = min[starX][starY][i]
print(minK)


def coin_on_the_table(N, M, K, B):
	C = [[999999 for _ in range(M)] for _ in range(N)]

	def search(i, j, S, T):
		if 0 <= i < N and 0 <= j < M and (S <= K) and (T < C[i][j]):
			C[i][j] = T
			search(i - 1, j, S + 1, T + (B[i][j] != 'U'))
			search(i + 1, j, S + 1, T + (B[i][j] != 'D'))
			search(i, j - 1, S + 1, T + (B[i][j] != 'L'))
			search(i, j + 1, S + 1, T + (B[i][j] != 'R'))
	search(0, 0, 0, 0)
	for i in range(N):
		for j in range(M):
			if B[i][j] == '*':
				return C[i][j]
	return None

def main():
	(N, M, K) = [int(i) for i in input().split()]
	B = [input() for _ in range(N)]
	C = coin_on_the_table(N, M, K, B)
	print(-1 if C == 999999 else C)
main()


MAX_INT = 2 ** 64

def find_goal(board):
	for (i, row) in enumerate(board):
		for (j, col) in enumerate(board[i]):
			if col == '*':
				return (i, j)
	return (-1, -1)

def min_operations(board, K):
	min_ops = list((list((list((0 for i in range(K + 1))) for j in range(len(board[0])))) for i in range(len(board))))
	for k in range(K + 1):
		for i in range(len(board)):
			for j in range(len(board[0])):
				if k == 0:
					min_ops[i][j][k] = 0 if i == 0 and j == 0 else MAX_INT
				else:
					p = min_ops[i][j][k - 1]
					u = min_ops[i - 1][j][k - 1] + (0 if board[i - 1][j] == 'D' else 1) if i > 0 else MAX_INT
					d = min_ops[i + 1][j][k - 1] + (0 if board[i + 1][j] == 'U' else 1) if i < len(board) - 1 else MAX_INT
					l = min_ops[i][j - 1][k - 1] + (0 if board[i][j - 1] == 'R' else 1) if j > 0 else MAX_INT
					r = min_ops[i][j + 1][k - 1] + (0 if board[i][j + 1] == 'L' else 1) if j < len(board[0]) - 1 else MAX_INT
					min_ops[i][j][k] = min(p, u, d, l, r)
	(i, j) = find_goal(board)
	ops = min_ops[i][j][K]
	return ops if ops < MAX_INT else -1
(n, m, k) = list(map(int, input().split()))
board = list()
for i in range(n):
	board.append(input().strip())
print(min_operations(board, k))


from sys import stderr

def main():
	(rows, cols, maxturns) = [int(fld) for fld in input().split()]
	dirtable = dict(U=(-1, 0), D=(1, 0), L=(0, -1), R=(0, 1))
	dirs = list(dirtable.values())
	dirtable['*'] = (0, 0)
	table = [[dirtable[c] for c in input().strip()] for _ in range(rows)]
	assert len(table) == rows and all((len(row) == cols for row in table))
	table = [[None] * (cols + 2)] + [[None] + row + [None] for row in table] + [[None] * (cols + 2)]
	inf = rows * cols + 1
	step = [[0 if dir == (0, 0) else inf for dir in row] for row in table]
	for k in range(maxturns):
		prevstep = tuple(map(tuple, step))
		for rnum in range(1, rows + 1):
			for cnum in range(1, cols + 1):
				step[rnum][cnum] = min(prevstep[rnum][cnum], min((prevstep[rnum + dr][cnum + dc] + (0 if (dr, dc) == table[rnum][cnum] else 1) for (dr, dc) in dirs)))
	corner = step[1][1]
	print(corner if corner != inf else -1)
main()


def d2i(c):
	if c == 'R':
		return 0
	if c == 'D':
		return 1
	if c == 'L':
		return 2
	if c == 'U':
		return 3
	return c

def parse(s):
	r = [d2i(c) for c in s]
	r.insert(0, '#')
	r.append('#')
	return r
(n, m, k) = tuple(map(int, input().split()))
d = [parse(input()) for i in range(n)]
d.insert(0, ['#'] * (m + 2))
d.append(['#'] * (m + 2))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def print_m(M):
	for row in M:
		print(''.join(map(str, row)))

def find_end(d, n, m):
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if d[i][j] == '*':
				return (i, j)
	return (None, None)
(X, Y) = find_end(d, n, m)
if X is None:
	print(-1)
	exit()
INF = 1 << 31
f = [[[INF] * (k + 2) for j in range(m + 2)] for i in range(n + 2)]
(x, y) = (1, 1)
finish = False
for i in range(0, k + 1):
	f[x][y][i] = 0
	if finish:
		continue
	nd = d[x][y]
	if nd == '*':
		finish = True
		continue
	if isinstance(nd, int) and 1 <= x + dx[nd] <= n and (1 <= y + dy[nd] <= m):
		x = x + dx[nd]
		y = y + dy[nd]
for l in range(0, k + 1):
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if d[i][j] != '*' and f[i][j][l] != INF:
				for cd in range(4):
					if 1 <= i + dx[cd] <= n and 1 <= j + dy[cd] <= m:
						f[i + dx[cd]][j + dy[cd]][l + 1] = min(f[i + dx[cd]][j + dy[cd]][l + 1], f[i][j][l] + (cd != d[i][j] and 1 or 0))
r = min(f[X][Y][:k + 1])
if r == INF:
	print(-1)
else:
	print(r)


def solve(arr, i, j, n, m, k):
	if i < 0 or j < 0 or i > n - 1 or (j > m - 1) or (k < 0) or (k == 0 and arr[i][j] != '*'):
		return 100000
	if arr[i][j] == '*':
		return 0
	if mem[i][j][k] != -1:
		return mem[i][j][k]
	min_val = 100000
	x = solve(arr, i, j + 1, n, m, k - 1)
	if x != 100000:
		x = x + (0 if arr[i][j] == 'R' else 1)
	min_val = min(min_val, x)
	x = solve(arr, i, j - 1, n, m, k - 1)
	if x != 100000:
		x = x + (0 if arr[i][j] == 'L' else 1)
	min_val = min(min_val, x)
	x = solve(arr, i - 1, j, n, m, k - 1)
	if x != 100000:
		x = x + (0 if arr[i][j] == 'U' else 1)
	min_val = min(min_val, x)
	x = solve(arr, i + 1, j, n, m, k - 1)
	if x != 100000:
		x = x + (0 if arr[i][j] == 'D' else 1)
	min_val = min(min_val, x)
	mem[i][j][k] = min_val
	return min_val
(n, m, k) = input().split()
n = int(n)
m = int(m)
k = int(k)
arr = [[' ' for j in range(m)] for i in range(n)]
for i in range(n):
	str = input()
	arr[i] = list(str)
mem = [[[-1 for i in range(200)] for j in range(200)] for l in range(1100)]
x = solve(arr, 0, 0, n, m, k)
print(x if x != 100000 else -1)


inf = float('inf')

def printMat(A):
	for row in A:
		for val in row:
			print(val, ' ', end='')
		print('')
	print('')
(N, M, K) = list(map(int, input().strip().split(' ')))
A = []
for i in range(N):
	temp = list(input().strip())
	A.append(temp)
for i in range(N):
	for j in range(M):
		if A[i][j] == '*':
			i_star = i
			j_star = j
			break
F = [[[inf for k in range(K + 1)] for j in range(M)] for i in range(N)]
for k in range(K + 1):
	F[i_star][j_star][k] = 0

def getNeigh(i, j, N, M):
	Neigh = [(i - 1, j, 'U'), (i + 1, j, 'D'), (i, j - 1, 'L'), (i, j + 1, 'R')]
	Neigh = [t for t in Neigh if 0 <= t[0] < N and 0 <= t[1] < M]
	return Neigh
for k in range(1, K + 1):
	for i in range(N):
		for j in range(M):
			Neigh = getNeigh(i, j, N, M)
			for s in Neigh:
				(p, q, act) = s
				if A[i][j] == act:
					print
					temp = F[p][q][k - 1]
				else:
					temp = F[p][q][k - 1] + 1
				F[i][j][k] = min(F[i][j][k], temp)
ans = F[0][0][K]
if ans is inf:
	ans = -1
print(ans)


line = input().split()
n = int(line[0])
m = int(line[1])
K = int(line[2])
a = [[] for each in range(n)]
i = 0
x = 0
y = 0
for b in range(n):
	line = list(input().rstrip())
	for j in range(len(line)):
		a[b].append(line[j])
		if line[j] == '*':
			y = j
			x = i
	i += 1
INF = 999999999
f = [[[INF] * m for each in range(n)] for each in range(K + 1)]
ans = INF
for k in range(K + 1):
	for i in range(n):
		for j in range(m):
			if k == 0:
				if i == 0 and j == 0:
					f[k][i][j] = 0
				else:
					f[k][i][j] = INF
			else:
				res = INF
				if i > 0:
					if a[i - 1][j] == 'D':
						res = min(res, f[k - 1][i - 1][j])
					else:
						res = min(res, f[k - 1][i - 1][j] + 1)
				if i < n - 1:
					if a[i + 1][j] == 'U':
						res = min(res, f[k - 1][i + 1][j])
					else:
						res = min(res, f[k - 1][i + 1][j] + 1)
				if j > 0:
					if a[i][j - 1] == 'R':
						res = min(res, f[k - 1][i][j - 1])
					else:
						res = min(res, f[k - 1][i][j - 1] + 1)
				if j < m - 1:
					try:
						if a[i][j + 1] == 'L':
							res = min(res, f[k - 1][i][j + 1])
						else:
							res = min(res, f[k - 1][i][j + 1] + 1)
					except IndexError:
						print('Values of i,j,k and n are ', i, j, k, n)
				f[k][i][j] = min(res, f[k - 1][i][j])
ans = f[K][x][y]
if ans == INF:
	print('-1')
else:
	print(ans)


from heapq import heappush, heappop
(R, C, K) = tuple(map(int, input().split()))
iMap = [list(input()) for _ in range(R)]
iCost = [[(65535, 65535, 65535, 65535) for c in range(C)] for _ in range(R)]
iCost[0][0] = (0, 0, 0, 0)
minHeap = []
visited = set([])
heappush(minHeap, (iCost[0][0], (0, 0)))
while len(minHeap) > 0:
	(cost, v) = heappop(minHeap)
	(r, c) = v
	if iMap[r][c] == '*':
		print(cost[2] if cost[0] + cost[1] == 0 else -1)
		break
	if r > 0:
		if sum(cost) < K:
			newcost = (cost[0], cost[1], cost[2], cost[3] + 1) if iMap[r][c] == 'U' else (cost[0], cost[1], cost[2] + 1, cost[3])
			if newcost < iCost[r - 1][c]:
				iCost[r - 1][c] = newcost
				heappush(minHeap, (newcost, (r - 1, c)))
		else:
			newcost = (cost[0], cost[1] + 1, cost[2], cost[3]) if iMap[r][c] == 'U' else (cost[0] + 1, cost[1], cost[2], cost[3])
			if newcost < iCost[r - 1][c]:
				iCost[r - 1][c] = newcost
				heappush(minHeap, (newcost, (r - 1, c)))
	if r < R - 1:
		if sum(cost) < K:
			newcost = (cost[0], cost[1], cost[2], cost[3] + 1) if iMap[r][c] == 'D' else (cost[0], cost[1], cost[2] + 1, cost[3])
			if newcost < iCost[r + 1][c]:
				iCost[r + 1][c] = newcost
				heappush(minHeap, (newcost, (r + 1, c)))
		else:
			newcost = (cost[0], cost[1] + 1, cost[2], cost[3]) if iMap[r][c] == 'D' else (cost[0] + 1, cost[1], cost[2], cost[3])
			if newcost < iCost[r + 1][c]:
				iCost[r + 1][c] = newcost
				heappush(minHeap, (newcost, (r + 1, c)))
	if c > 0:
		if sum(cost) < K:
			newcost = (cost[0], cost[1], cost[2], cost[3] + 1) if iMap[r][c] == 'L' else (cost[0], cost[1], cost[2] + 1, cost[3])
			if newcost < iCost[r][c - 1]:
				iCost[r][c - 1] = newcost
				heappush(minHeap, (newcost, (r, c - 1)))
		else:
			newcost = (cost[0], cost[1] + 1, cost[2], cost[3]) if iMap[r][c] == 'L' else (cost[0] + 1, cost[1], cost[2], cost[3])
			if newcost < iCost[r][c - 1]:
				iCost[r][c - 1] = newcost
				heappush(minHeap, (newcost, (r, c - 1)))
	if c < C - 1:
		if sum(cost) < K:
			newcost = (cost[0], cost[1], cost[2], cost[3] + 1) if iMap[r][c] == 'R' else (cost[0], cost[1], cost[2] + 1, cost[3])
			if newcost < iCost[r][c + 1]:
				iCost[r][c + 1] = newcost
				heappush(minHeap, (newcost, (r, c + 1)))
		else:
			newcost = (cost[0], cost[1] + 1, cost[2], cost[3]) if iMap[r][c] == 'R' else (cost[0] + 1, cost[1], cost[2], cost[3])
			if newcost < iCost[r][c + 1]:
				iCost[r][c + 1] = newcost
				heappush(minHeap, (newcost, (r, c + 1)))


def delta(i_new, j_new, i_old, j_old, field):
	letter = field[i_old][j_old]
	h = (0, 0)
	if letter is 'U':
		return not i_old - 1 == i_new
	elif letter is 'L':
		return not j_old - 1 == j_new
	elif letter is 'D':
		return not i_old + 1 == i_new
	elif letter is 'R':
		return not j_old + 1 == j_new
	else:
		return 1 << 29

def fmain():
	(n, m, k) = (2, 2, 3)
	field = [['R', 'D'], ['*', 'L']]
	return find_min(n, m, k, field)

def main(D=False):
	(n, m, k) = map(lambda x: int(x), input().split())
	field = [list(input()) for _ in range(n)]
	x = 0
	y = 0
	for (i, l) in enumerate(field):
		try:
			y = l.index('*')
			x = i
		except ValueError:
			continue
	if D:
		print('Found * at (%d, %d)' % (x + 1, y + 1))
	f = [[[1 << 29 for _ in range(m)] for _ in range(n)] for _ in range(k + 1)]
	for t in range(len(f)):
		f[t][0][0] = 0
	for t in range(len(f)):
		for i in range(len(f[t])):
			for j in range(len(f[t][i])):
				cost = 1 << 29
				if t == 0:
					continue
				if i > 0:
					cost = min(cost, f[t - 1][i - 1][j] + delta(i, j, i - 1, j, field))
				if i < n - 1:
					cost = min(cost, f[t - 1][i + 1][j] + delta(i, j, i + 1, j, field))
				if j > 0:
					cost = min(cost, f[t - 1][i][j - 1] + delta(i, j, i, j - 1, field))
				if j < m - 1:
					cost = min(cost, f[t - 1][i][j + 1] + delta(i, j, i, j + 1, field))
				f[t][i][j] = min(cost, f[t][i][j])
		if D:
			print(f[t])
	min_cost = 1 << 29
	for t in range(len(f)):
		min_cost = min(min_cost, f[t][x][y])
	if min_cost == 1 << 29:
		return -1
	return min_cost
print(main())


def delta(i, j, x, y):
	if i == x:
		if j + 1 == y:
			if a[i][j] == 'R':
				return 0
			else:
				return 1
		elif a[i][j] == 'L':
			return 0
		else:
			return 1
	elif i + 1 == x:
		if a[i][j] == 'D':
			return 0
		else:
			return 1
	elif a[i][j] == 'U':
		return 0
	else:
		return 1
line = input().split()
n = int(line[0])
m = int(line[1])
K = int(line[2])
a = [[] for each in range(n)]
i = 0
x = 0
y = 0
for b in range(n):
	line = list(input().rstrip())
	for j in range(len(line)):
		a[b].append(line[j])
		if line[j] == '*':
			y = j
			x = i
	i += 1
INF = 999999999
f = [[[INF] * m for each in range(n)] for each in range(K + 1)]
ans = INF
for k in range(K + 1):
	for i in range(n):
		for j in range(m):
			if k == 0:
				if i == 0 and j == 0:
					f[k][i][j] = 0
				else:
					f[k][i][j] = INF
			else:
				res = INF
				if i > 0:
					res = min(res, f[k - 1][i - 1][j] + delta(i - 1, j, i, j))
				if i < n - 1:
					res = min(res, f[k - 1][i + 1][j] + delta(i + 1, j, i, j))
				if j > 0:
					res = min(res, f[k - 1][i][j - 1] + delta(i, j - 1, i, j))
				if j < m - 1:
					res = min(res, f[k - 1][i][j + 1] + delta(i, j + 1, i, j))
				f[k][i][j] = min(res, f[k - 1][i][j])
ans = f[K][x][y]
if ans == INF:
	print('-1')
else:
	print(ans)


import sys
directions = set(['L', 'R', 'U', 'D'])

def make_move(r, c, move):
	if move == 'D':
		r += 1
	elif move == 'U':
		r -= 1
	elif move == 'R':
		c += 1
	elif move == 'L':
		c -= 1
	out = [r, c]
	return out

def print_board(reach):
	for i in range(len(reach)):
		line = ''.join((str(x) for x in reach[i]))
		print(line)

def search(board):
	reach = [[0 for i in range(M)] for i in range(N)]
	reacht = [[0 for i in range(M)] for i in range(N)]
	visited = [[0 for i in range(M)] for i in range(N)]
	next_visit_list = list()
	total_visited = 0
	k = 0
	r = 0
	c = 0
	t = 0
	reach[r][c] = 0
	reacht[r][c] = t
	visited[r][c] = 1
	move = board[r][c]
	next_visit_list.append(tuple([r, c]))
	[r, c] = make_move(r, c, move)
	traverse = True
	while traverse:
		t += 1
		if r < 0 or c >= N:
			traverse = False
			continue
		if c < 0 or c >= M:
			traverse = False
			continue
		move = board[r][c]
		if visited[r][c]:
			traverse = False
			continue
		reach[r][c] = k
		reacht[r][c] = t
		visited[r][c] = 1
		total_visited += 1
		next_visit_list.append(tuple([r, c]))
		[r, c] = make_move(r, c, move)
	while total_visited < M * N - 1:
		k += 1
		this_visit_list = next_visit_list
		next_visit_list = list()
		while len(this_visit_list) > 0:
			start = this_visit_list.pop()
			r = start[0]
			c = start[1]
			board_move = board[r][c]
			possible_moves = [x for x in directions if x not in board_move]
			for i in range(3):
				r = start[0]
				c = start[1]
				move = possible_moves[i]
				[r, c] = make_move(r, c, move)
				traverse = True
				while traverse:
					if r < 0 or r >= N:
						traverse = False
						continue
					if c < 0 or c >= M:
						traverse = False
						continue
					move = board[r][c]
					if visited[r][c]:
						if k < reach[r][c]:
							reach[r][c] = k
						traverse = False
						continue
					t = reacht[r][c] + 1
					reach[r][c] = k
					reacht[r][c] = k
					visited[r][c] = 1
					total_visited += 1
					next_visit_list.append(tuple([r, c]))
					[r, c] = make_move(r, c, move)
	val = reach[r_star][c_star]
	valt = reacht[r_star][c_star]
	if valt > K:
		if val > K:
			out1 = -1
		else:
			out1 = 1
	else:
		out1 = val
	out = [val, valt]
	return out1
(N, M, K) = [int(q_temp) for q_temp in input().strip().split(' ')]
board = list()
for i in range(N):
	line = input().strip()
	board.append(line)
	if line.find('*') > -1:
		r_star = i
		c_star = line.find('*')
out = search(board)
print(out)


def fun(i, j, x, y):
	if i == x:
		if j + 1 == y:
			if a[i][j] == 'R':
				return 0
			else:
				return 1
		elif a[i][j] == 'L':
			return 0
		else:
			return 1
	elif i + 1 == x:
		if a[i][j] == 'D':
			return 0
		else:
			return 1
	elif a[i][j] == 'U':
		return 0
	else:
		return 1
(n, m, k) = list(map(int, input().split()))
a = []
for i in range(n):
	b = input()
	a.append(b)
for i in range(n):
	for j in range(m):
		if a[i][j] == '*':
			p = i
			q = j
inf = 999999
x = p + q
i = 0
j = 0
l = [[[inf] * m for j in range(n)] for d in range(k + 1)]
for d in range(k + 1):
	for i in range(n):
		for j in range(m):
			if d == 0:
				if i == 0 and j == 0:
					l[d][i][j] = 0
				else:
					l[d][i][j] = inf
			else:
				z = inf
				if i > 0:
					z = min(z, l[d - 1][i - 1][j] + fun(i - 1, j, i, j))
				if i < n - 1:
					z = min(z, l[d - 1][i + 1][j] + fun(i + 1, j, i, j))
				if j > 0:
					z = min(z, l[d - 1][i][j - 1] + fun(i, j - 1, i, j))
				if j < m - 1:
					z = min(z, l[d - 1][i][j + 1] + fun(i, j + 1, i, j))
				l[d][i][j] = min(z, l[d - 1][i][j])
z = l[k][p][q]
if z == inf:
	print('-1')
else:
	print(z)


def delta(i, j, x, y):
	if i == x:
		if j + 1 == y:
			if a[i][j] == 'R':
				return 0
			else:
				return 1
		elif a[i][j] == 'L':
			return 0
		else:
			return 1
	elif i + 1 == x:
		if a[i][j] == 'D':
			return 0
		else:
			return 1
	elif a[i][j] == 'U':
		return 0
	else:
		return 1
line = input().split()
n = int(line[0])
m = int(line[1])
K = int(line[2])
a = [[] for each in range(n)]
i = 0
x = 0
y = 0
for b in range(n):
	line = list(input().rstrip())
	for j in range(len(line)):
		a[b].append(line[j])
		if line[j] == '*':
			y = j
			x = i
	i += 1
INF = 999999999
f = [[[INF] * m for each in range(n)] for each in range(K + 1)]
ans = INF
for k in range(K + 1):
	for i in range(n):
		for j in range(m):
			if k == 0:
				if i == 0 and j == 0:
					f[k][i][j] = 0
				else:
					f[k][i][j] = INF
			else:
				res = INF
				if i > 0:
					res = min(res, f[k - 1][i - 1][j] + delta(i - 1, j, i, j))
				if i < n - 1:
					res = min(res, f[k - 1][i + 1][j] + delta(i + 1, j, i, j))
				if j > 0:
					res = min(res, f[k - 1][i][j - 1] + delta(i, j - 1, i, j))
				if j < m - 1:
					res = min(res, f[k - 1][i][j + 1] + delta(i, j + 1, i, j))
				f[k][i][j] = min(res, f[k - 1][i][j])
ans = f[K][x][y]
if ans == INF:
	print('-1')
else:
	print(ans)


class Element:

	def __init__(self, data, next):
		self.data = data
		self.next = next

class Queue:

	def __init__(self):
		self.head = None

	def __str__(self):
		ptr = self.head
		if self.head == None:
			string = 'Front < > Back'
		else:
			string = 'Front < '
			while ptr:
				string += '%s ' % str(ptr.data)
				ptr = ptr.next
			string += '> Back'
		return string

	def enQueue(self, data):
		ptr = self.head
		if ptr == None:
			self.head = Element(data, self.head)
		else:
			while ptr.next:
				ptr = ptr.next
			ptr.next = Element(data, None)

	def deQueue(self):
		if self.head == None:
			return None
		ptr = self.head
		self.head = self.head.next
		ptr.next = None
		return ptr.data

def findEnd(table):
	for (ri, row) in enumerate(table):
		for (ci, column) in enumerate(row):
			if column[0] == '*':
				return (ri, ci)
	return None

def traverseTable(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	queue = Queue()
	followUp = Queue()
	queue.enQueue((x, y))
	first = queue.deQueue()
	while first:
		followUp.enQueue(first)
		x = first[0]
		y = first[1]
		if x - 1 >= 0 and table[y][x - 1][1] == None:
			(table[y][x - 1][1], table[y][x - 1][2]) = computeCount(table, x - 1, y, K, N, M)
			queue.enQueue((x - 1, y))
		if y - 1 >= 0 and table[y - 1][x][1] == None:
			(table[y - 1][x][1], table[y - 1][x][2]) = computeCount(table, x, y - 1, K, N, M)
			queue.enQueue((x, y - 1))
		if x + 1 < M and table[y][x + 1][1] == None:
			(table[y][x + 1][1], table[y][x + 1][2]) = computeCount(table, x + 1, y, K, N, M)
			queue.enQueue((x + 1, y))
		if y + 1 < N and table[y + 1][x][1] == None:
			(table[y + 1][x][1], table[y + 1][x][2]) = computeCount(table, x, y + 1, K, N, M)
			queue.enQueue((x, y + 1))
		first = queue.deQueue()
	second = followUp.deQueue()
	while second:
		x = second[0]
		y = second[1]
		(table[y][x][1], table[y][x][2], changed) = searchNearby(table, x, y, table[y][x][1], table[y][x][2], K, N, M, followUp)
		if changed:
			if x - 1 >= 0:
				if checkNearby(table, x, y, x - 1, y, K):
					followUp.enQueue((x - 1, y))
			if y - 1 >= 0:
				if checkNearby(table, x, y, x, y - 1, K):
					followUp.enQueue((x, y - 1))
			if x + 1 < M:
				if checkNearby(table, x, y, x + 1, y, K):
					followUp.enQueue((x + 1, y))
			if y + 1 < N:
				if checkNearby(table, x, y, x, y + 1, K):
					followUp.enQueue((x, y + 1))
		second = followUp.deQueue()
	if table[0][0][1] == float('inf'):
		return -1
	else:
		return table[0][0][2]

def computeCount(table, startX, startY, K, N, M):
	(x, y) = (startX, startY)
	ptr = table[y][x]
	if ptr[0] == 'U':
		y -= 1
	elif ptr[0] == 'D':
		y += 1
	elif ptr[0] == 'L':
		x -= 1
	elif ptr[0] == 'R':
		x += 1
	if x < 0 or x >= M or y < 0 or (y >= N):
		return (float('inf'), 0)
	else:
		if table[y][x][1] == None:
			dist = float('inf')
		else:
			dist = table[y][x][1] + 1
		count = table[y][x][2]
		if dist > K:
			(dist, count, changed) = searchNearby(table, startX, startY, dist, count, K, N, M)
		return (dist, count)

def searchNearby(table, x, y, dist, count, K, N, M, queue=None):
	ptr = table[y][x]
	best = count
	prevCount = count
	prevDist = dist
	prevDir = table[y][x][0]
	if y + 1 < N:
		if table[y + 1][x][1] != None and table[y + 1][x][1] + 1 <= K and (table[y + 1][x][2] < best or dist == float('inf')):
			dist = table[y + 1][x][1] + 1
			if table[y][x][3] == 'D':
				best = table[y + 1][x][2]
			else:
				best = table[y + 1][x][2] + 1
			if table[y][x][0] != 'D':
				table[y][x][0] = 'D'
	if x + 1 < M:
		if table[y][x + 1][1] != None and table[y][x + 1][1] + 1 <= K and (table[y][x + 1][2] < best or dist == float('inf')):
			dist = table[y][x + 1][1] + 1
			if table[y][x][3] == 'R':
				best = table[y][x + 1][2]
			else:
				best = table[y][x + 1][2] + 1
			if table[y][x][0] != 'R':
				table[y][x][0] = 'R'
	if y - 1 >= 0:
		if table[y - 1][x][1] != None and table[y - 1][x][1] + 1 <= K and (table[y - 1][x][2] < best or dist == float('inf')):
			dist = table[y - 1][x][1] + 1
			if table[y][x][3] == 'U':
				best = table[y - 1][x][2]
			else:
				best = table[y - 1][x][2] + 1
			if table[y][x][0] != 'U':
				table[y][x][0] = 'U'
	if x - 1 >= 0:
		if table[y][x - 1][1] != None and table[y][x - 1][1] + 1 <= K and (table[y][x - 1][2] < best or dist == float('inf')):
			dist = table[y][x - 1][1] + 1
			if table[y][x][3] == 'L':
				best = table[y][x - 1][2]
			else:
				best = table[y][x - 1][2] + 1
			if table[y][x][0] != 'L':
				table[y][x][0] = 'L'
	if prevCount == best and prevDist == dist and (prevDir == table[y][x][0]):
		changed = False
	else:
		changed = True
	if dist > K:
		return (float('inf'), 0, changed)
	else:
		return (dist, best, changed)

def checkNearby(table, x1, y1, x2, y2, K):
	if table[y1][x1][1] == K:
		return False
	if table[y1][x1][2] < table[y2][x2][2] or table[y2][x2][1] == float('inf'):
		return True
	else:
		return False
NMK = input().strip()
N = int(NMK.split(' ')[0])
M = int(NMK.split(' ')[1])
K = int(NMK.split(' ')[2])
table = []
for row in range(N):
	table.append([])
	for char in input().strip():
		table[row].append([char, None, 0, char])
endpt = findEnd(table)
table[endpt[0]][endpt[1]][1] = 0
print(traverseTable(table, endpt[1], endpt[0], K, N, M))


def init(board, dp, k):
	queue = []
	queue.append([0, 0, 0])
	new_reached = set([])
	while queue:
		v = queue.pop(0)
		if (v[0] < 0 or v[0] >= len(board[0])) or (v[1] < 0 or v[1] >= len(board)):
			continue
		if dp[v[0]][v[1]] != -1:
			continue
		if v[2] > k:
			continue
		dp[v[0]][v[1]] = v[2]
		if board[v[0]][v[1]] == 'R':
			queue.append([v[0], v[1] + 1, dp[v[0]][v[1]] + 1])
		elif board[v[0]][v[1]] == 'L':
			queue.append([v[0], v[1] - 1, dp[v[0]][v[1]] + 1])
		elif board[v[0]][v[1]] == 'U':
			queue.append([v[0] - 1, v[1], dp[v[0]][v[1]] + 1])
		elif board[v[0]][v[1]] == 'D':
			queue.append([v[0] + 1, v[1], dp[v[0]][v[1]] + 1])
		new_reached.add(v[0] << 16 | v[1])
	return new_reached

def step(time, board, dp, reached):
	new_reached = set([])
	for r in reached:
		row = r >> 16
		col = r & 255
		new_reached.add(r)
		str = 'RLUD'
		tmp = board[row][col]
		for s in str:
			if s != tmp:
				board[row][col] = s
				dfs(row, col, s, board, dp, new_reached, k)
		board[row][col] = tmp
	return new_reached

def dfs(row, col, s, board, dp, new_reached, k):
	queue = []
	queue.append([row, col, dp[row][col]])
	start = True
	while queue:
		v = queue.pop(0)
		if (v[0] < 0 or v[0] >= len(board)) or (v[1] < 0 or v[1] >= len(board[0])):
			continue
		if start == False:
			if dp[v[0]][v[1]] != -1:
				if v[2] >= dp[v[0]][v[1]]:
					continue
		start = False
		if v[2] > k:
			continue
		dp[v[0]][v[1]] = v[2]
		if board[v[0]][v[1]] == 'R':
			queue.append([v[0], v[1] + 1, dp[v[0]][v[1]] + 1])
		elif board[v[0]][v[1]] == 'L':
			queue.append([v[0], v[1] - 1, dp[v[0]][v[1]] + 1])
		elif board[v[0]][v[1]] == 'U':
			queue.append([v[0] - 1, v[1], dp[v[0]][v[1]] + 1])
		elif board[v[0]][v[1]] == 'D':
			queue.append([v[0] + 1, v[1], dp[v[0]][v[1]] + 1])
		new_reached.add(v[0] << 16 | v[1])
	return 0
str = input().split()
n = int(str[0])
m = int(str[1])
k = int(str[2])
board = [[None] * m for i in range(n)]
star_row = -1
star_col = -1
for i in range(n):
	str = input()
	for j in range(m):
		board[i][j] = str[j]
	if str.find('*') != -1:
		star_row = i
		star_col = str.find('*')
dp = [[-1 for i in range(m)] for i in range(n)]
new_reached = init(board, dp, k)
if dp[star_row][star_col] != -1:
	print('0')
	exit()
for i in range(k):
	new_reached = step(i + 1, board, dp, new_reached)
	if dp[star_row][star_col] != -1:
		print(i + 1)
		exit()
print(-1)


from queue import Queue
(n, m, k) = map(int, input().split())
table = [input() for i in range(n)]
for i in range(n):
	flag = True
	for j in range(m):
		if table[i][j] == '*':
			flag = False
			break
	if not flag:
		break
if i + j > k:
	print(-1)
else:
	arr = [[1001 for i in range(m)] for j in range(n)]
	queue = Queue()
	queue.put((i, j, 0))
	while not queue.empty():
		(i, j, c) = queue.get()
		arr[i][j] = c
		if j > 0 and arr[i][j - 1] == 1001 and (table[i][j - 1] == 'R'):
			queue.put((i, j - 1, c + 1))
		if j < m - 1 and arr[i][j + 1] == 1001 and (table[i][j + 1] == 'L'):
			queue.put((i, j + 1, c + 1))
		if i > 0 and arr[i - 1][j] == 1001 and (table[i - 1][j] == 'D'):
			queue.put((i - 1, j, c + 1))
		if i < n - 1 and arr[i + 1][j] == 1001 and (table[i + 1][j] == 'U'):
			queue.put((i + 1, j, c + 1))
	count = 0
	while arr[0][0] > k:
		narr = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m):
				curr = arr[i][j]
				if i > 0:
					curr = min(curr, 1 + arr[i - 1][j])
				if i < n - 1:
					curr = min(curr, 1 + arr[i + 1][j])
				if j > 0:
					curr = min(curr, 1 + arr[i][j - 1])
				if j < m - 1:
					curr = min(curr, 1 + arr[i][j + 1])
				narr[i][j] = curr
				if narr[i][j] != 1001:
					queue.put((i, j, curr))
		while not queue.empty():
			(i, j, c) = queue.get()
			narr[i][j] = c
			if j > 0 and narr[i][j - 1] == 1001 and (table[i][j - 1] == 'R'):
				queue.put((i, j - 1, c + 1))
			if j < m - 1 and narr[i][j + 1] == 1001 and (table[i][j + 1] == 'L'):
				queue.put((i, j + 1, c + 1))
			if i > 0 and narr[i - 1][j] == 1001 and (table[i - 1][j] == 'D'):
				queue.put((i - 1, j, c + 1))
			if i < n - 1 and narr[i + 1][j] == 1001 and (table[i + 1][j] == 'U'):
				queue.put((i + 1, j, c + 1))
		arr = [[narr[i][j] for j in range(m)] for i in range(n)]
		count += 1
	print(count)


import sys
from collections import namedtuple
cell = namedtuple('cell', 'id row column')

def cellId(row, column, columns):
	return row * columns + column

def validCell(cell, rows, columns):
	return (0 <= cell.row and cell.row < rows) and (0 <= cell.column and cell.column < columns)
(rows, columns, steps) = input().strip().split(' ')
(rows, columns, steps) = [int(rows), int(columns), int(steps)]
grid = [list(input().strip()) for row in range(rows)]
cellQty = rows * columns
cells = [() for c in range(cellQty)]
neighbors = [[] for c in range(cellQty)]
next = [() for c in range(cellQty)]
goal = ()
for row in range(rows):
	for column in range(columns):
		id = cellId(row, column, columns)
		cells[id] = cell(id, row, column)
		up = cell(cellId(row - 1, column, columns), row - 1, column)
		down = cell(cellId(row + 1, column, columns), row + 1, column)
		left = cell(cellId(row, column - 1, columns), row, column - 1)
		right = cell(cellId(row, column + 1, columns), row, column + 1)
		if validCell(up, rows, columns):
			neighbors[id].append(up)
		if validCell(down, rows, columns):
			neighbors[id].append(down)
		if validCell(left, rows, columns):
			neighbors[id].append(left)
		if validCell(right, rows, columns):
			neighbors[id].append(right)
		if grid[row][column] == 'U':
			next[id] = up
		if grid[row][column] == 'D':
			next[id] = down
		if grid[row][column] == 'L':
			next[id] = left
		if grid[row][column] == 'R':
			next[id] = right
		if grid[row][column] == '*':
			goal = cells[id]
			next[id] = cells[id]
operations = [[-1 for step in range(steps + 1)] for c in range(cellQty)]
operations[goal.id][0] = 0
for step in range(1, steps + 1):
	for cell in cells:
		if cell.id == goal.id:
			operations[cell.id][step] = 0
			continue
		validNeighbors = [n for n in neighbors[cell.id] if operations[n.id][step - 1] >= 0]
		nextId = next[cell.id].id
		changes = [operations[n.id][step - 1] + (0 if nextId == n.id else 1) for n in validNeighbors]
		if len(changes) > 0:
			operations[cell.id][step] = min(changes)
minRequired = operations[0][steps]
print(minRequired)


def pr(v, vv, delta, k, temp, i, j, kk):
	yes = False
	for (x, y) in v.items():
		if y < k and x + delta < kk:
			yy = vv.get(x + delta, k + 1)
			if y + 1 < yy:
				yes = True
				vv[x + delta] = y + 1
	if yes:
		if delta:
			temp.insert(0, (i, j))
		else:
			temp.append((i, j))
(n, m, k) = map(int, input().split())
data = []
for i in range(n):
	data.append(list(map(lambda x: (x, {}), input().strip())))
queue = [(0, 0)]
ii = None
jj = None
kk = k + 1
data[0][0][1][0] = 0
while queue:
	temp = []
	(i, j) = queue.pop()
	(u, v) = data[i][j]
	if u == '*':
		ii = i
		jj = j
		kk = min(data[ii][jj][1].keys())
	else:
		if i > 0:
			delta = u != 'U'
			vv = data[i - 1][j][1]
			pr(v, vv, delta, k, temp, i - 1, j, kk)
		if j > 0:
			delta = u != 'L'
			vv = data[i][j - 1][1]
			pr(v, vv, delta, k, temp, i, j - 1, kk)
		if i < n - 1:
			delta = u != 'D'
			vv = data[i + 1][j][1]
			pr(v, vv, delta, k, temp, i + 1, j, kk)
		if j < m - 1:
			delta = u != 'R'
			vv = data[i][j + 1][1]
			pr(v, vv, delta, k, temp, i, j + 1, kk)
		queue.extend(temp)
if ii is not None and jj is not None:
	print(min(data[ii][jj][1].keys()))
else:
	print(-1)


from math import inf

def coin_on_table(n, m, k, matrix):
	(si, sj) = (0, 0)
	to_visit = [(si, sj, 0)]
	dists = [[inf] * m for _ in range(n)]
	dists[si][sj] = 0
	(ni, nj) = next_step(n, m, matrix, si, sj)
	for (ni, nj) in find_all_reachables(n, m, k, matrix, ni, nj, 1, dists):
		to_visit.append((ni, nj, 0))
	while to_visit:
		(ci, cj, cc) = to_visit.pop(0)
		if matrix[ci][cj] == '*':
			return cc
		dist_so_far = dists[ci][cj]
		for (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
			(ni, nj) = (ci + di, cj + dj)
			dc = 0 if (ni, nj) == next_step(n, m, matrix, ci, cj) else 1
			for (i, j) in find_all_reachables(n, m, k, matrix, ni, nj, dist_so_far + 1, dists):
				to_visit.append((i, j, cc + dc))
	return -1

def find_all_reachables(n, m, k, matrix, ci, cj, dist_so_far, dists):
	while True:
		if ci not in range(n) or cj not in range(m):
			break
		if dist_so_far > k or dist_so_far >= dists[ci][cj]:
			break
		dists[ci][cj] = dist_so_far
		yield (ci, cj)
		(ci, cj) = next_step(n, m, matrix, ci, cj)
		dist_so_far += 1

def next_step(n, m, matrix, i, j):
	cur_mark = matrix[i][j]
	if cur_mark == 'U':
		return (i - 1, j)
	elif cur_mark == 'D':
		return (i + 1, j)
	elif cur_mark == 'L':
		return (i, j - 1)
	elif cur_mark == 'R':
		return (i, j + 1)
	elif cur_mark == '*':
		return (i, j)
	else:
		assert False, 'unknown mark'
	assert False, 'cannot reach here'

def main():
	(n, m, k) = map(int, input().split())
	matrix = [input().strip() for _ in range(n)]
	print(coin_on_table(n, m, k, matrix))
main()


import sys
inf = float('inf')

def cache_and_return_min_at_point(n, m, b, row, col, ln, cache, inf):
	if (row, col) == (0, 0):
		cache[row, col, ln] = 0
		return 0
	csh_get = cache.get
	my_min = min
	ln1 = ln - 1
	mn = inf
	for ((r, c), symb) in (((row - 1, col), 'D'), ((row, col - 1), 'R'), ((row, col + 1), 'L'), ((row + 1, col), 'U')):
		if 0 <= r < n and 0 <= c < m and (b[r][c] != '*'):
			prev_mn = csh_get((r, c, ln1), inf)
			mn = my_min(mn, prev_mn if symb == b[r][c] else prev_mn + 1)
	cache[row, col, ln] = mn
	return mn

def fill_up_cache(n, m, k, b, cache):
	c_and_r = cache_and_return_min_at_point
	visited = set()
	frontier = [(0, 0)]
	nxt = []
	for ln in range(0, k + 1):
		for (row, col) in frontier:
			if (row, col, ln) not in visited:
				visited.add((row, col, ln))
				mn = c_and_r(n, m, b, row, col, ln, cache, inf)
				for (r, c) in ((row - 1, col), (row, col - 1), (row, col + 1), (row + 1, col)):
					if 0 <= r < n and 0 <= c < m:
						nxt.append((r, c))
		frontier = nxt[:]

def find_star(n, m, b):
	for row in range(n):
		for col in range(m):
			if b[row][col] == '*':
				return (row, col)

def min_operations(n, m, k, b):
	cache = {}
	fill_up_cache(n, m, k, b, cache)
	(row, col) = find_star(n, m, b)
	m = cache.get((row, col, k), inf)
	return m if m < inf else -1

def enter_data():
	(n, m, k) = [int(x.strip()) for x in sys.stdin.readline().split()]
	b = tuple((tuple(sys.stdin.readline()) for j in range(n)))
	return min_operations(n, m, k, b)
print(enter_data())


from pprint import pprint

class CoinOnTheTable:

	def __init__(self):
		self.direction = {}
		self.direction[-1, 0] = 'D'
		self.direction[1, 0] = 'U'
		self.direction[0, -1] = 'R'
		self.direction[0, 1] = 'L'

	def read_numbers(self, string):
		(self.N, self.M, self.K) = [int(x) for x in string.split()]
		self.cache = [[[float('inf') for _ in range(self.M)] for _ in range(self.N)] for _ in range(self.K + 1)]

	def read_board(self, string):
		self.board = [[0 for _ in range(self.M)] for _ in range(self.N)]
		for (i, row) in enumerate(string.split('\n')):
			for j in range(self.M):
				self.board[i][j] = row[j]
		self.board_init = [[x for x in row] for row in self.board]

	def print_board(self, board):
		for row in board:
			print(''.join(row))
		print('-' * self.M)

	def print_cache(self, t):
		print('t = %d' % t)
		for row in self.cache[t]:
			print(row)

	def solve(self):
		self.cache[0][0][0] = 0
		ret = float('inf')
		for t in range(1, self.K + 1):
			for i in range(self.N):
				for j in range(self.M):
					if i + j > self.K:
						continue
					self.cache[t][i][j] = self.check_neighbor(t, i, j)
					if self.board[i][j] == '*':
						ret = min(ret, self.cache[t][i][j])
		if ret == float('inf'):
			print(-1)
		else:
			print(ret)
		return ret

	def check_neighbor(self, t, i, j):
		ret = float('inf')
		for (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
			if not self.is_in_board(i + di, j + dj):
				continue
			cand = self.cache[t - 1][i + di][j + dj]
			if self.board[i + di][j + dj] != self.direction[di, dj]:
				cand += 1
			ret = min(ret, cand)
		return ret

	def is_in_board(self, i, j):
		if 0 <= i < self.N and 0 <= j < self.M:
			return True
		else:
			return False

def main():
	cot = CoinOnTheTable()
	cot.read_numbers(input())
	board = []
	for n in range(cot.N):
		board.append(input())
	board_str = '\n'.join(board)
	cot.read_board(board_str)
	cot.solve()
main()


a = input().split()
N = int(a[0])
M = int(a[1])
K = int(a[2])
table = []
for i in range(N):
	table.append(input())
count = {}
direction = {'L': (0, -1), 'R': (0, 1), 'U': (-1, 0), 'D': (1, 0)}

def minichange(i, j, k):
	if k < 0:
		return -1
	if i < 0 or i >= N or j < 0 or (j >= M):
		return -1
	if (i, j, k) in count:
		return count[i, j, k]
	if table[i][j] == '*':
		count[i, j, k] = 0
		return 0
	min_vert = 2500
	flag = False
	for char in direction.keys():
		d = direction[char]
		next_ver = minichange(i + d[0], j + d[1], k - 1)
		if next_ver != -1 and (char != table[i][j]) + next_ver < min_vert:
			flag = True
			min_vert = (char != table[i][j]) + next_ver
	if not flag:
		count[i, j, k] = -1
		return -1
	else:
		count[i, j, k] = min_vert
		return min_vert
print(minichange(0, 0, K))


import sys

def delta(i, j, x, y):
	if i == x:
		if j + 1 == y:
			if board[i][j] == 'R':
				return 0
		elif board[i][j] == 'L':
			return 0
		return 1
	else:
		if i + 1 == x:
			if board[i][j] == 'D':
				return 0
		elif board[i][j] == 'U':
			return 0
		return 1
[N, M, K] = [int(i) for i in input().split()]
(x, y) = (0, 0)
board = []
for i in range(N):
	temp = input()
	board += [temp.strip()]
	if '*' in temp:
		(x, y) = (len(board) - 1, temp.index('*'))
T = [[[sys.maxsize for j in range(M)] for i in range(N)] for k in range(K + 1)]
for k in range(K + 1):
	for i in range(N):
		for j in range(M):
			if k == 0:
				if i == 0 and j == 0:
					T[k][i][j] = 0
			else:
				res = sys.maxsize
				if i > 0:
					res = min(res, T[k - 1][i - 1][j] + delta(i - 1, j, i, j))
				if i + 1 < N:
					res = min(res, T[k - 1][i + 1][j] + delta(i + 1, j, i, j))
				if j > 0:
					res = min(res, T[k - 1][i][j - 1] + delta(i, j - 1, i, j))
				if j + 1 < M:
					res = min(res, T[k - 1][i][j + 1] + delta(i, j + 1, i, j))
				T[k][i][j] = min(res, T[k - 1][i][j])
if T[K][x][y] == sys.maxsize:
	print('-1')
else:
	print(T[K][x][y])


from collections import deque

def solve(n, m, k, board):
	minsteps = [[[float('Inf') for _ in range(n + m + 2)] for _ in range(m)] for _ in range(n)]
	minsteps[0][0][0] = 0
	directions = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
	todo = deque([(0, 0, 0)])
	while todo:
		(i, j, changes) = todo.popleft()
		if changes > m + n or board[i][j] == '*':
			continue
		steps = minsteps[i][j][changes]
		for dir in 'UDRL':
			changes2 = changes
			if board[i][j] != dir:
				changes2 += 1
			(di, dj) = directions[dir]
			(i2, j2) = (i + di, j + dj)
			if 0 <= i2 < n and 0 <= j2 < m and (minsteps[i2][j2][changes2] > steps + 1):
				minsteps[i2][j2][changes2] = steps + 1
				todo.append((i2, j2, changes2))
	for i in range(n):
		for j in range(m):
			if board[i][j] == '*':
				for changes in range(m + n + 1):
					if minsteps[i][j][changes] <= k:
						return changes
	return -1
(n, m, k) = [int(x) for x in input().split()]
board = [input().strip() for _ in range(n)]
ans = solve(n, m, k, board)
print(ans)


from queue import PriorityQueue
(n, m, k) = map(int, input().split())
b = []
for i in range(n):
	b.append(input())
vis = [[False for i in range(m)] for i in range(n)]
Q = PriorityQueue()
Q.put((0, 0, 0, 0))
vis[0][0] = True
while not Q.empty():
	(s, t, x, y) = Q.get()
	vis[x][y] = True
	if b[x][y] == '*':
		print(s)
		exit(0)
	if t >= k:
		continue
	if x > 0:
		if not vis[x - 1][y]:
			if b[x][y] == 'U':
				Q.put((s, t + 1, x - 1, y))
			else:
				Q.put((s + 1, t + 1, x - 1, y))
	if y > 0:
		if not vis[x][y - 1]:
			if b[x][y] == 'L':
				Q.put((s, t + 1, x, y - 1))
			else:
				Q.put((s + 1, t + 1, x, y - 1))
	if x + 1 < n:
		if not vis[x + 1][y]:
			if b[x][y] == 'D':
				Q.put((s, t + 1, x + 1, y))
			else:
				Q.put((s + 1, t + 1, x + 1, y))
	if y + 1 < m:
		if not vis[x][y + 1]:
			if b[x][y] == 'R':
				Q.put((s, t + 1, x, y + 1))
			else:
				Q.put((s + 1, t + 1, x, y + 1))
print('-1')


import heapq
(N, M, K) = map(int, input().split())
grid = []
for i in range(N):
	grid.append(input().strip())
active = [(0, 0, 0, 0)]
oldchange = [[-1] * M for i in range(N)]
oldtime = [[0] * M for i in range(N)]
while active:
	(change, time, i, j) = heapq.heappop(active)
	if oldchange[i][j] < change:
		oldchange[i][j] = change
	elif oldtime[i][j] <= time:
		continue
	oldtime[i][j] = time
	c = grid[i][j]
	if c == '*':
		print(change)
		break
	if time < K:
		if i > 0:
			heapq.heappush(active, (change + (c != 'U'), time + 1, i - 1, j))
		if j > 0:
			heapq.heappush(active, (change + (c != 'L'), time + 1, i, j - 1))
		if i + 1 < N:
			heapq.heappush(active, (change + (c != 'D'), time + 1, i + 1, j))
		if j + 1 < M:
			heapq.heappush(active, (change + (c != 'R'), time + 1, i, j + 1))
else:
	print(-1)


import os
import sys

def inBoard(i, j):
	if 0 <= i < n and 0 <= j < m:
		return True
	else:
		return False

def dfs(i, j, cost, step, costs, board):
	if not inBoard(i, j) or 0 <= costs[i][j] <= cost:
		return
	costs[i][j] = cost
	if board[i][j] == '*':
		return
	if step == k:
		return
	dfs(i - 1, j, cost if board[i][j] == 'U' else cost + 1, step + 1, costs, board)
	dfs(i + 1, j, cost if board[i][j] == 'D' else cost + 1, step + 1, costs, board)
	dfs(i, j - 1, cost if board[i][j] == 'L' else cost + 1, step + 1, costs, board)
	dfs(i, j + 1, cost if board[i][j] == 'R' else cost + 1, step + 1, costs, board)

def coinOnTheTable(m, k, board):
	n = len(board)
	costs = [[-1] * m for _ in range(n)]
	dfs(0, 0, 0, 0, costs, board)
	for i in range(n):
		for j in range(m):
			if board[i][j] == '*':
				return costs[i][j]
nmk = input().split()
n = int(nmk[0])
m = int(nmk[1])
k = int(nmk[2])
board = []
for _ in range(n):
	board_item = input()
	board.append(board_item)
result = coinOnTheTable(m, k, board)
print(result)


(n, m, K) = list(map(int, input().split()))
x = -1
y = -1
arr = [[None for j in range(m)] for i in range(n)]
for i in range(n):
	arr[i] = input()
	for j in range(m):
		if arr[i][j] == '*':
			x = i
			y = j
temp = [[[0 for x in range(m)] for j in range(n)] for i in range(K + 1)]
temp[0][0][0] = 0
for k in range(K + 1):
	for i in range(n):
		for j in range(m):
			if k == 0:
				temp[k][i][j] = 0 if i is 0 and j is 0 else 999999999
			else:
				res = 999999999
				if i > 0:
					res = min(res, temp[k - 1][i - 1][j] + (0 if arr[i - 1][j] == 'D' else 1))
				if i < n - 1:
					res = min(res, temp[k - 1][i + 1][j] + (0 if arr[i + 1][j] == 'U' else 1))
				if j > 0:
					res = min(res, temp[k - 1][i][j - 1] + (0 if arr[i][j - 1] == 'R' else 1))
				if j < m - 1:
					res = min(res, temp[k - 1][i][j + 1] + (0 if arr[i][j + 1] == 'L' else 1))
				temp[k][i][j] = res
ans = 999999999
for k in range(K + 1):
	ans = min(ans, temp[k][x][y])
if ans != 999999999:
	print(ans)
else:
	print(-1)


import sys

def coinOnTheTable(board, k):
	m = len(board)
	n = len(board[0])
	maxdist = n + m + 1
	distances = [[maxdist] * n for _ in range(m)]
	distances[0][0] = 0

	def dist(i, j, direction):
		if 0 <= i < n and 0 <= j < m:
			if board[j][i] == direction:
				return distances[j][i]
			else:
				return distances[j][i] + 1
		return maxdist
	for _ in range(k):
		d2 = [[0] * n for _ in range(m)]
		for i in range(n):
			for j in range(m):
				d2[j][i] = min(distances[j][i], dist(i + 0, j + 1, 'U'), dist(i + 0, j - 1, 'D'), dist(i - 1, j + 0, 'R'), dist(i + 1, j + 0, 'L'))
		distances = d2
	for i in range(n):
		for j in range(m):
			if board[j][i] == '*':
				if distances[j][i] < maxdist:
					return distances[j][i]
				return -1
	assert False

def main():
	fp = sys.stdin
	if 1:
		(n, m, k) = map(int, fp.readline().split())
		board = []
		for _ in range(n):
			board_item = fp.readline()
			board.append(board_item.strip())
		print(coinOnTheTable(board, k))
main()


import sys
sys.setrecursionlimit(2000)
(rows, _, max_steps_count) = tuple(map(int, input().strip().split()))
grid = [list(input().strip()) for _ in range(rows)]
letter_coord_modifs = (('U', (-1, 0)), ('D', (1, 0)), ('L', (0, -1)), ('R', (0, 1)))
memo = {}

def find_min_changes_count(row, col, steps_count):
	stored_res = memo.get((row, col, steps_count))
	if stored_res is not None:
		return stored_res
	if not (0 <= row < len(grid) and 0 <= col < len(grid[0])) or steps_count > max_steps_count:
		return sys.maxsize
	curr_letter = grid[row][col]
	if curr_letter == '*':
		return 0
	min_changes_count = sys.maxsize
	for (new_letter, (row_modif, col_modif)) in letter_coord_modifs:
		grid[row][col] = new_letter
		min_changes_count = min(min_changes_count, 1 * (new_letter != curr_letter) + find_min_changes_count(row + row_modif, col + col_modif, steps_count + 1))
		grid[row][col] = curr_letter
		if min_changes_count == 0:
			break
	memo[row, col, steps_count] = min_changes_count
	return min_changes_count
res = find_min_changes_count(0, 0, 0)
print(res if res < sys.maxsize else -1)