import sys
import math
import queue
r, c, a = [int(i) for i in input().split()]
actions = None
swapdict = {
"RIGHT": "LEFT",
"LEFT": "RIGHT",
"UP": "DOWN",
"DOWN": "UP" }
validactions = list(swapdict.values())
actiondict = {
"RIGHT": lambda lab,kr,kc : lab[kr][kc+1],
"LEFT": lambda lab,kr,kc : lab[kr][kc-1],
"UP": lambda lab,kr,kc : lab[kr-1][kc],
"DOWN": lambda lab,kr,kc : lab[kr+1][kc] }
coordict = {
"RIGHT": lambda kr,kc : (kr,kc+1),
"LEFT": lambda kr,kc : (kr,kc-1),
"UP": lambda kr,kc : (kr-1,kc),
"DOWN": lambda kr,kc : (kr+1,kc) }
nodes = {}
class Node:
"""
A Node in the search tree, representing a cell in the labyrinth,
with edges corresponding to the available actions.
"""
def __init__(self,kr,kc,labyrinth,action,parentnode=None):
self.kr = kr
self.kc = kc
if action == None:
self.parentaction = None
else:
self.parentaction = swapdict[action]
self.parentnode = parentnode
if parentnode == None:
self.distance = 0
else:
self.distance = parentnode.distance + 1
self.child = {}
if parentnode != None:
parentnode.child[action] = self
pnode = nodes.get((kr,kc))
if pnode == None:
nodes[(kr,kc)] = self
elif self.distance < pnode.distance:
nodes[(kr,kc)] = self
self.actions = None
def makeactions(self):
self.actions = []
(kr,kc) = (self.kr,self.kc)
for action in validactions:
if action == self.parentaction: continue
if actiondict[action](labyrinth,kr,kc) == "#": continue
xy = coordict[action](kr,kc)
pnode = nodes.get(xy)
print("Consider",(kr,kc),action,xy,pnode,file=sys.stderr,flush=True)
if pnode == None:
self.actions.append(action)
elif pnode.distance < self.distance:
print("shortcut",(pnode.kr,pnode.kc),(kr,kc),action,
file=sys.stderr,flush=True)
nodes[(kr,kc)] = Node(kr,kc,labyrinth,swapdict[action],pnode)
def returnaction(self):
pnode = nodes.get((self.kr,self.kc))
if pnode == None:
print("pnode == None",file=sys.stderr,flush=True)
r = (self.parentaction,self.parentnode)
elif pnode == self:
print("pnode == self",file=sys.stderr,flush=True)
r = (self.parentaction,self.parentnode)
elif self.distance < pnode.distance:
print("pnode makes detour",file=sys.stderr,flush=True)
r = (self.parentaction,self.parentnode)
else:
r = pnode.returnaction()
print("shortcut", file=sys.stderr)
print("returning", (kr,kc), r, file=sys.stderr)
return r
def getaction(self):
if self.actions == None: self.makeactions()
if len(self.actions) == 0:
return None
else:
action = self.actions.pop()
self.child[action] = None
return action
action = None
parentnode = None
node = None
def bfs(labyrinth,kr,kc):
Q = queue.Queue()
colour = { (kr,kc): "Grey" }
action = {}
Q.put( (kr,kc) )
target = None
while not Q.empty():
node = Q.get()
(kr1,kc1) = node
for v in validactions:
(r,c) = coordict[v](kr1,kc1)
print( "bfs", (r,c), file=sys.stderr, flush=True )
if labyrinth[r][c] == "T":
action[(r,c)] = (v,(kr1,kc1))
target = (r,c)
break
elif labyrinth[r][c] == ".":
if colour.get((r,c)) == None:
print( "bfs put", (r,c), file=sys.stderr, flush=True )
Q.put( (r,c) )
colour[(r,c)] = "Grey"
action[(r,c)] = (v,(kr1,kc1))
pass
actions = []
(r,c) = target
while (r,c) != (kr,kc):
(v,(r,c)) = action[(r,c)]
print(v,(r,c), file=sys.stderr, flush=True)
actions.append(v)
return actions
# game loop
while True:
kr, kc = [int(i) for i in input().split()]
labyrinth = []
for i in range(r):
row = input()
labyrinth.append(row)
if labyrinth[kr][kc] == "C":
actions = bfs(labyrinth,kr,kc)
print("RETURNING", file=sys.stderr, flush=True)
l = list(labyrinth[kr])
l[kc] = "*"
labyrinth[kr] = "".join(l)
for i in range(r):
print(labyrinth[i], file=sys.stderr, flush=True)
if actions != None:
action = actions.pop()
else:
if node == None:
node = Node(kr,kc,labyrinth,action,parentnode)
else:
assert (kr,kc) == (node.kr,node.kc)
action = node.getaction()
if action == None:
action = node.parentaction
node = node.parentnode
parentnode = node.parentnode
else:
parentnode = node
node = None
print(action)
