using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using static Constants; public static class Constants { public static readonly int N = 20; public static readonly Point[] Dirs = { new Point(-1, 0), // 左 new Point(0, -1), // 上 new Point(1, 0), // 右 new Point(0, 1), // 下 }; } public class PriorityQueue { SortedDictionary> dict = new SortedDictionary>(); int count; Random random = new Random(); public int Count { get { return count; } } public void Enqueue(TKey key, TValue value) { List set; if (!dict.TryGetValue(key, out set)) { set = new List(); dict[key] = set; } set.Add(value); count++; } public KeyValuePair Dequeue() { var queue = dict.First(); if (queue.Value.Count <= 1) { dict.Remove(queue.Key); } var list = queue.Value; var i = random.Next(list.Count); var val = list[i]; count--; if (list.Count > 1) { (list[i], list[list.Count - 1]) = (list[list.Count - 1], list[i]); list.RemoveAt(list.Count - 1); } return new KeyValuePair(queue.Key, val); } } public struct Point { public int X; public int Y; public static readonly Point Invalid = new Point(-1, -1); public static readonly Point Left = new Point(-1, 0); public static readonly Point Up = new Point(0, -1); public static readonly Point Right = new Point(1, 0); public static readonly Point Down = new Point(0, 1); public Point(Point p) { X = p.X; Y = p.Y; } public Point(int x, int y) { X = x; Y = y; } public static bool operator ==(Point a, Point b) { return (a.X == b.X && a.Y == b.Y); } public static bool operator !=(Point a, Point b) { return !(a == b); } //objと自分自身が等価のときはtrueを返す public override bool Equals(object obj) { if (!(obj is Point)) { return false; } Point p = (Point)obj; return (X == p.X && Y == p.Y); } //Equalsがtrueを返すときに同じ値を返す public override int GetHashCode() { return (X << 16) ^ Y; } public Point Clone() { return new Point(X, Y); } public void Reverse() { X = -X; Y = -Y; } public static Point operator +(Point a, Point b) { return new Point(a.X + b.X, a.Y + b.Y); } public static Point operator -(Point a, Point b) { return new Point(a.X - b.X, a.Y - b.Y); } public static Point operator *(Point a, int i) { return new Point(a.X * i, a.Y * i); } public static Point operator /(Point a, int i) { return new Point(a.X / i, a.Y / i); } public static Point operator +(Point a) { return new Point(+a.X, +a.Y); } public static Point operator -(Point a) { return new Point(-a.X, -a.Y); } public override string ToString() { return string.Format("({0},{1})", Y, X); } public Point Sign() { return new Point(Math.Sign(X), Math.Sign(Y)); } public int Distance(Point p) { return Math.Abs(this.X - p.X) + Math.Abs(this.Y - p.Y); } public char ToDirStr() { if (X < 0) { return 'L'; } if (X > 0) { return 'R'; } if (Y < 0) { return 'U'; } return 'D'; } public bool InRange() { return 0 <= X && X < N && 0 <= Y && Y < N; } } public class Solver { readonly double P; int[,] RWall; // -1:壁はない 0以上:移動失敗回数 int[,] DWall; List[,] Neighbors; public Solver(double p) { P = p; RWall = new int[N, N]; DWall = new int[N, N]; InitNeighbors(); } void InitNeighbors() { Neighbors = new List[N, N]; for (int y = 0; y < N; y++) { for (int x = 0; x < N; x++) { Neighbors[y, x] = new List(); var p = new Point(x, y); foreach (var dir in Dirs) { var nei = p + dir; if (nei.InRange()) { Neighbors[y, x].Add(nei); } } } } } int GetWallValue(Point cur, Point next) { var dir = next - cur; if (dir.Y == 0) { return RWall[cur.Y, Math.Min(cur.X, next.X)]; } return DWall[Math.Min(cur.Y, next.Y), cur.X]; } double GetProb(Point cur, Point next) { const double wallProb = 150.0 / 760.0; // 100~200 / 全壁 var dir = next - cur; var wall = GetWallValue(cur, next); if (wall == -1) { return 1; } // X:k回移動失敗としたとき,ベイズの定理より // P(壁|X) = P(X|壁)P(壁) / (P(X|壁)P(壁) + P(X|非壁)P(非壁)) // ここで,P(X|壁)=1 より // P(壁|X) = P(壁) / (P(壁) + p^k*(1-P(壁)) return 1 - wallProb / (wallProb + Math.Pow(P, wall) * (1 - wallProb)); } public (string, List) GetAction() { var start = new Point(0, 0); var goal = new Point(N - 1, N - 1); var prev = new Dictionary(); var queue = new PriorityQueue(); // 確率の降順 queue.Enqueue(-1, start); prev[start] = start; while (queue.Count > 0) { var kv = queue.Dequeue(); var cur = kv.Value; var prob = -kv.Key; foreach (var next in Neighbors[cur.Y, cur.X]) { if (prev.ContainsKey(next)) { continue; } var nextProb = prob * GetProb(cur, next) * (1 - P); queue.Enqueue(-nextProb, next); prev[next] = cur; if (next == goal) { break; } } } var way = new List(); for (var p = goal; p != start; p = prev[p]) { way.Add(p); } way.Add(start); way.Reverse(); var acts = new StringBuilder(); var pr = start; foreach (var p in way.Skip(1)) { var dir = p - pr; acts.Append(dir.ToDirStr()); pr = p; } return (acts.ToString(), way); } public void SetResult(List way, int step) { for (int i = 0; i < step; i++) { var cur = way[i]; var next = way[i + 1]; var dir = next - cur; if (dir.Y == 0) { var y = cur.Y; var x = Math.Min(cur.X, next.X); RWall[y, x] = -1; } else { var y = Math.Min(cur.Y, next.Y); var x = cur.X; DWall[y, x] = -1; } } { var cur = way[step]; var next = way[step + 1]; var dir = next - cur; if (dir.Y == 0) { var y = cur.Y; var x = Math.Min(cur.X, next.X); if (RWall[y, x] >= 0) { RWall[y, x]++; } } else { var y = Math.Min(cur.Y, next.Y); var x = cur.X; if (DWall[y, x] >= 0) { DWall[y, x]++; } } } } } public static class Solution { public static void Main() { var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); var h = vals[0]; var w = vals[1]; var p = vals[2] * 0.01; var solver = new Solver(p); try { while (true) { (var acts, var way) = solver.GetAction(); Console.WriteLine(acts); var step = int.Parse(Console.ReadLine()); if (step < 0) { break; } solver.SetResult(way, step); } } catch (Exception e) { Console.Error.WriteLine(e); } } }