# B - ハイパーお掃除ロボット テストプレイ解
#
# 方針
# 縦横で繋がっていると判断してUnionFind
# 大きい繋がりを一気に取る
# 500回分くらいの移動を先に決め、後で柱の移動方法を決める
# 同じ値が全てつながっていないことがある
# 一度取得したセルは移動中に使えるので、移動したセルを経由して繋げれるなら繋ぐ
# 最初に繋がっていない状態で移動してしまうと損なので、移動して繋げれるようなら移動する
# 繋がりの中での移動方法は移動コストを少し工夫して2-opt
# コスト
# 移動回数*1000
# 移動経路にある柱*300
# 移動距離*1
# コスト計算用の柱の位置は移動が決まったら、移動経路から削除し、移動に必要な柱を残す
# 移動方法が決まると、i回目の移動時に柱があるべきかないべきかが決まる
# 移動経路から消すときには、最も小さいiで必要なセルに移動する
# 必要なセルがなければ、ないべきセルで最もiが大きいセル
# 必要な柱を持ってくるときには、上記の逆
#
# その他(?)
# 実装が面倒だったのでpythonにしたが、時間が足りてない
# 実行によってスコアにばらつきがあるので、全体を何度かやるのが有効だけどできてない
# 2-optの試行回数も少なめ
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random
inf = 10**20
def LI(): return list(map(int, sys.stdin.readline().split()))
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)
class UnionFind:
def __init__(self, size):
self.table = [-1 for _ in range(size)]
def find(self, x):
if self.table[x] < 0:
return x
else:
self.table[x] = self.find(self.table[x])
return self.table[x]
def union(self, x, y):
s1 = self.find(x)
s2 = self.find(y)
if s1 != s2:
if self.table[s1] <= self.table[s2]:
self.table[s1] += self.table[s2]
self.table[s2] = s1
else:
self.table[s2] += self.table[s1]
self.table[s1] = s2
return True
return False
def usize(self, x):
return -self.table[self.find(x)]
def reset(self, t):
for k in [x for x in range(len(self.table)) if self.find(x) == t]:
self.table[k] = -1
def subset(self, x):
t = self.find(x)
return [x for x in range(len(self.table)) if self.find(x) == t]
def main():
MAX_A = 26
N, P, M = LI()
B = [[c for c in S()] for _ in range(N)]
A = [[ord(c) - ord('A') + 1 for c in S()] for _ in range(N)]
C = [0] * (MAX_A + 1)
cr = cc = -1
for i in range(N):
for j in range(N):
C[A[i][j]] += 1
if B[i][j] == 'o':
cr = i
cc = j
B[i][j] = '-'
pe(sorted(C))
uf = UnionFind(N*N)
for i in range(N):
for j in range(N):
ij = i*N+j
a = A[i][j]
for k in range(N):
if A[k][j] == a:
uf.union(ij, k*N+j)
if A[i][k] == a:
uf.union(ij, i*N+k)
scs = [[] for _ in range(N*N)]
sci = [0] * (N*N)
def set_koho(t,cr,cc,nr,nc):
mr = mc = -1
mf = 0
mi = -1
for i in range(N):
for j in range(N):
if B[i][j] == 'x' or (cr == i and cc == j) or (nr == i and nc == j):
continue
ij = i*N+j
sc = scs[ij]
si = sci[ij]
while sc[si][0] < t:
sci[ij] += 1
si += 1
ti, f = sc[si]
if mf == 1:
if f == 1 and ti < mi:
mr, mc, mi, mf = i, j, ti, f
else:
if f == 1 or ti > mi:
mr, mc, mi, mf = i, j, ti, f
return mr, mc
def get_koho(t):
mr = mc = -1
mf = 1
mi = -1
for i in range(N):
for j in range(N):
if B[i][j] == '-':
continue
ij = i*N+j
sc = scs[ij]
si = sci[ij]
while sc[si][0] < t:
sci[ij] += 1
si += 1
ti, f = sc[si]
if mf == 0:
if f == 0 and ti < mi:
mr, mc, mi, mf = i, j, ti, f
else:
if f == 0 or ti > mi:
mr, mc, mi, mf = i, j, ti, f
return mr, mc
rr = []
# 直線のみ
def move(crc, nrc, t):
# pe(["mv", crc,nrc])
cr,cc = crc
nr,nc = nrc
pa = []
ma = []
mv = ''
if cr == nr:
if cc < nc:
mv = 'R'
if nc < N-1 and B[cr][nc+1] == '-':
ma.append((cr,nc+1))
for c in range(cc+1, nc+1):
if B[cr][c] == 'x':
pa.append((cr,c))
else:
mv = 'L'
if nc > 0 and B[cr][nc-1] == '-':
ma.append((cr,nc-1))
for c in range(cc-1, nc-1, -1):
if B[cr][c] == 'x':
pa.append((cr,c))
else:
if cr < nr:
mv = 'D'
if nr < N-1 and B[nr+1][cc] == '-':
ma.append((nr+1,cc))
for r in range(cr+1, nr+1):
if B[r][cc] == 'x':
pa.append((r,cc))
else:
mv = 'U'
if nr > 0 and B[nr-1][cc] == '-':
ma.append((nr-1,cc))
for r in range(cr-1, nr-1, -1):
if B[r][cc] == 'x':
pa.append((r,cc))
for i in range(max(len(pa), len(ma))):
if i < len(pa):
p = pa[i]
else:
p = get_koho(t)
if i < len(ma):
m = ma[i]
else:
m = set_koho(t,cr,cc,nr,nc)
rr.append(('P', p[0], p[1], m[0], m[1]))
B[p[0]][p[1]] = '-'
B[m[0]][m[1]] = 'x'
rr.append((mv,))
TA = [B[i][:] for i in range(N)]
def update_ta(crc, nrc):
cr, cc = crc
nr, nc = nrc
if nr < cr:
for r in range(nr,cr+1):
TA[r][cc] = '-'
if nr > 0:
TA[nr-1][cc]= 'x'
elif nr > cr:
for r in range(cr,nr+1):
TA[r][cc] = '-'
if nr < N-1:
TA[nr+1][cc]= 'x'
elif nc < cc:
for c in range(nc,cc+1):
TA[cr][c] = '-'
if nc > 0:
TA[nc-1][cc] = 'x'
else:
for c in range(cc,nc+1):
TA[cr][c] = '-'
if nc < N-1:
TA[nc+1][cc] = 'x'
cma = sorted(C)[-1]
cmi = sorted(C)[-5]
moves = [(cr,cc)]
while len(moves) < M * 0.55:
mr = mc = mm = -1
mf = False
for i in range(N):
if i != cr:
us = uf.usize(i*N+cc)
tf = C[A[i][cc]] == us
if ((not mf) and (us > mm or (us >= cmi and tf))) or (us >= mm and tf):
mr = i
mc = cc
mm = us
mf = us >= cmi and tf
if i != cc:
us = uf.usize(cr*N+i)
tf = C[A[cr][i]] == us
if ((not mf) and (us > mm or (us >= cmi and tf))) or (us >= mm and tf):
mr = i
mc = cc
mm = us
mf = us >= cmi and tf
if mm < C[A[mr][mc]] and C[A[mr][mc]] >= cma:
mf = False
for i in range(N):
if i != cr and C[A[i][cc]] < cmi:
for k in range(N):
if k == i or C[A[k][cc]] < cma:
continue
uff = uf.find(k*N+cc)
for l in range(N):
if l == cc or A[i][l] != A[k][cc]:
continue
if uf.find(i*N+l) != uff:
mf = True
if mf:
cr = i
break
if i != cc and C[A[cr][i]] < cmi:
for k in range(N):
if k == i or C[A[cr][k]] < cma:
continue
uff = uf.find(cr*N+k)
for l in range(N):
if l == cr or A[l][i] != A[cr][k]:
continue
if uf.find(l*N+i) != uff:
mf = True
if mf:
cc = i
break
if mf:
A[cr][cc] = 0
for i in range(N):
if i == cr or A[i][cc] == 0:
continue
for j in range(N):
if j != cc and A[cr][j] == A[i][cc]:
uf.union(i*N+cc, cr*N+j)
moves.append((cr,cc))
update_ta(moves[-2], moves[-1])
continue
mr = mc = mm = -1
for i in range(N):
if i != cr and uf.usize(i*N+cc) > mm:
mr = i
mc = cc
mm = uf.usize(i*N+cc)
if i != cc and uf.usize(cr*N+cc) > mm:
mr = cr
mc = cc
mm = uf.usize(cr*N+cc)
# pe(["crc",cr,cc,"mrc",mr,mc,mm, uf.find(mr*N+mc), 'C', C[A[mr][mc]]])
sa = [(x//N, x%N) for x in uf.subset(mr*N+mc)]
sl = len(sa)
# pe([sl, sa])
sa += [(i, j) for j in range(N) for i in range(N) if A[i][j] == 0]
e = collections.defaultdict(list)
for i in range(sl):
for j in range(i+1, len(sa)):
if sa[i][0] == sa[j][0]:
k1,k2 = sa[i][1], sa[j][1]
if k1 > k2:
k1,k2 = k2,k1
t = 1000 + k2 - k1
for k in range(k1, k2+1):
if TA[sa[i][0]][k] == 'x':
t += 300
e[i].append((j, t))
e[j].append((i, t))
if sa[i][1] == sa[j][1]:
k1,k2 = sa[i][0], sa[j][0]
if k1 > k2:
k1,k2 = k2,k1
t = 1000 + k2 - k1
for k in range(k1, k2+1):
if TA[k][sa[i][1]] == 'x':
t += 300
e[i].append((j, t))
e[j].append((i, t))
def search(s):
d = collections.defaultdict(lambda: inf)
d[s] = 0
q = []
heapq.heappush(q, (0, s))
v = collections.defaultdict(bool)
while len(q):
k, u = heapq.heappop(q)
if v[u]:
continue
v[u] = True
for uv,ud in e[u]:
if v[uv]:
continue
vd = k + ud
if d[uv] > vd:
d[uv] = vd
heapq.heappush(q, (vd, uv))
return d
d = {}
for i in range(sl):
d[i] = search(i)
# pe([sl, sa[:sl]])
path = list(range(sl))
for i in range(sl):
if sa[i] == (mr,mc):
path[0], path[i] = path[i], path[0]
break
k = 0
for i in range(sl-1):
k += d[path[i]][path[i+1]]
# pe(k)
pl = len(path)
for _ in range(pl ** 2 * 5):
a = random.randrange(sl-1) + 1
b = random.randrange(sl-2) + 1
if b >= a:
b += 1
if a > b:
a,b = b,a
pa = path[a]
pa1 = path[a-1]
pb = path[b]
ck1 = d[pa][pa1]
nk1 = d[pb][pa1]
if b < sl-1:
pb1 = path[b+1]
ck2 = d[pb][pb1]
nk2 = d[pa][pb1]
ck = ck1 + ck2
nk = nk1 + nk2
if nk < ck:
path[a:b+1] = path[a:b+1][::-1]
elif nk1 <= ck1:
path[a:b+1] = path[a:b+1][::-1]
k = 0
for i in range(sl-1):
k += d[path[i]][path[i+1]]
# pe(k)
update_ta((cr,cc), (mr,mc))
moves.append((mr,mc))
cr,cc = mr,mc
for i in range(sl-1):
c = path[i]
n = path[i+1]
while c != n:
if c < n:
k = d[c][n]
else:
k = d[n][c]
for t, td in e[c]:
if n >= sl and t >= sl:
continue
if ((t < n) and d[t][n] + td == k) or d[n][t] + td == k:
update_ta((cr,cc), sa[t])
moves.append(sa[t])
cr,cc = sa[t]
c = t
break
# pe([c,n,k])
for sr, sc in sa:
A[sr][sc] = 0
for sr, sc in sa:
for i in range(N):
if i == sr or A[i][sc] == 0:
continue
for j in range(N):
if j != sc and A[sr][j] == A[i][sc]:
uf.union(i*N+sc, sr*N+j)
uf.reset(uf.find(mr*N+mc))
cr,cc = moves[0]
for i in range(1, len(moves)):
nr,nc = moves[i]
if cr == nr:
if cc < nc:
if nc < N-1:
scs[cr*N+nc+1].append((i, 1))
for c in range(cc+1, nc+1):
scs[cr*N+c].append((i, 0))
else:
if nc > 0:
scs[cr*N+nc-1].append((i, 1))
for c in range(cc-1, nc-1, -1):
scs[cr*N+c].append((i, 0))
else:
if cr < nr:
if nr < N-1:
scs[(nr+1)*N+cc].append((i, 1))
for r in range(cr+1, nr+1):
scs[r*N+cc].append((i, 0))
else:
if nr > 0:
scs[(nr-1)*N+cc].append((i, 1))
for r in range(cr-1, nr-1, -1):
scs[r*N+cc].append((i, 0))
cr,cc = nr,nc
for i in range(N*N):
scs[i].append((M, 1))
crc = moves[0]
for i in range(1, len(moves)):
move(crc, moves[i], i)
crc = moves[i]
return JAA(rr[:M], "\n", " ")
print(main())