from collections import deque grid_size = 60 # 迷宮の大きさ max_hp = 1500 # 初期体力 dy = [-1, 1, 0, 0] dx = [0, 0, -1, 1] dir = "UDLR" # 敵クラス class Enemy: def __init__(self, y, x, d, num): self.y = y self.x = x self.d = d self.num = num self.destroyed = False # 座標が迷宮の範囲外かどうかを判断する関数 def range_out(y, x): if y < 0 or y >= grid_size: return True if x < 0 or x >= grid_size: return True return False # スタート地点からゴール地点までの最短経路を求める関数 def find_path(sy, sx, gy, gx, S): siz = len(S) dist = [[-1] * siz for _ in range(siz)] dist[sy][sx] = 0 q = deque([(sy, sx)]) while q: y, x = q.popleft() for k in range(4): ny = y + dy[k] nx = x + dx[k] if range_out(ny, nx): continue if dist[ny][nx] != -1: continue cell = S[ny][nx] if cell == '#' or cell == 'B' or cell == 'E': continue dist[ny][nx] = dist[y][x] + 1 q.append((ny, nx)) res = "" if dist[gy][gx] == -1: return res, None, None now_y, now_x, now_d = gy, gx, dist[gy][gx] while now_y != sy or now_x != sx: moved = False for k in range(4): new_y = now_y + dy[k] new_x = now_x + dx[k] if range_out(new_y, new_x): continue if dist[new_y][new_x] != now_d - 1: continue now_y, now_x = new_y, new_x now_d -= 1 res += dir[k ^ 1] moved = True break assert moved return res[::-1], now_y, now_x # メイン処理 def main(): N, D, H = map(int, input().split()) S = [input() for _ in range(N)] M = int(input()) E = [] for _ in range(M): y, x, d = map(int, input().split()) E.append(Enemy(y, x, d, len(E))) ans = "" # 各座標を初期化 sy, sx, ky, kx, jy, jx, gy, gx = None, None, None, None, None, None, None, None # 迷宮の各セルをループして、スタート地点(S)、鍵の位置(K)、宝石の位置(J)、ゴール地点(G)の座標を取得する for i in range(N): for j in range(N): if S[i][j] == 'S': sy, sx = i, j elif S[i][j] == 'K': ky, kx = i, j elif S[i][j] == 'J': jy, jx = i, j elif S[i][j] == 'G': gy, gx = i, j # スタート地点から鍵の位置までの経路を見つける find_key, current_y, current_x = find_path(sy, sx, ky, kx, S) ans += find_key # 鍵の位置からゴール地点までの経路を見つける goal, _, _ = find_path(current_y, current_x, gy, gx, S) ans += goal # 経路を出力する for c in ans: print("M", c) if __name__ == '__main__': main()