using System; using System.Collections.Generic; using System.Linq; using System.Text; class YukicoS5006 { public static void Main() { var nums = Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); var solver = new YukicoS5006Solver(nums[2]); while (true) { var cmd = solver.GetCommand(); Console.WriteLine(cmd); var res = int.Parse(Console.ReadLine()); if (res == -1) break; solver.UpdateWall(cmd, res); } } } class YukicoS5006Solver { const int N = 20; const int NN = N * N; const double InitWallRate = 150.0 / ((N - 1) * N * 2); readonly int _p; readonly double[] wallRateV = Enumerable.Repeat(InitWallRate, NN).ToArray(); readonly double[] wallRateH = Enumerable.Repeat(InitWallRate, NN).ToArray(); readonly Grid _grid; public YukicoS5006Solver(int p) { _p = p; _grid = new Grid(N, N); } public string GetCommand() { var wallCost = 100.0; var costs = GetRouteCost(wallCost); return GetRoute(costs); } double[] GetRouteCost(double wallCost) { var priorityQueue = new PriorityQueue(); priorityQueue.Enqueue(0, 0.0); var costs = Enumerable.Repeat(double.MaxValue, NN).ToArray(); var visited = new bool[NN]; while (priorityQueue.TryDequeue(out int pos, out double currentCost)) { if (visited[pos]) continue; // その頂点への最短経路のコストを更新 costs[pos] = currentCost; visited[pos] = true; var cell = _grid.Cells[pos]; if (cell.Y > 0) { var wallRate = wallRateV[cell.EdgeIds[Direction.Up]]; var cost = 1 + (wallRate * wallCost); priorityQueue.Enqueue(pos - N, currentCost + cost); } if (cell.Y < N - 1) { var wallRate = wallRateV[cell.EdgeIds[Direction.Down]]; var cost = 1 + (wallRate * wallCost); priorityQueue.Enqueue(pos + N, currentCost + cost); } if (cell.X > 0) { var wallRate = wallRateH[cell.EdgeIds[Direction.Left]]; var cost = 1 + (wallRate * wallCost); priorityQueue.Enqueue(pos - 1, currentCost + cost); } if (cell.Y < N - 1) { var wallRate = wallRateH[cell.EdgeIds[Direction.Right]]; var cost = 1 + (wallRate * wallCost); priorityQueue.Enqueue(pos + 1, currentCost + cost); } } return costs; } string GetRoute(double[] costs) { var sb = new StringBuilder(); var pos = 19 * N + 19; while (pos != 0) { var bestDir = 'X'; var bestNext = -1; var bestCost = double.MaxValue; var cell = _grid.Cells[pos]; if (cell.Y > 0) { var next = pos - N; var cost = costs[next]; if (cost < bestCost) { bestCost = cost; bestNext = next; bestDir = 'D'; } } if (cell.Y < N - 1) { var next = pos + N; var cost = costs[next]; if (cost < bestCost) { bestCost = cost; bestNext = next; bestDir = 'U'; } } if (cell.X > 0) { var next = pos - 1; var cost = costs[next]; if (cost < bestCost) { bestCost = cost; bestNext = next; bestDir = 'R'; } } if (cell.X < N - 1) { var next = pos + 1; var cost = costs[next]; if (cost < bestCost) { bestCost = cost; bestNext = next; bestDir = 'L'; } } sb.Insert(0, bestDir); pos = bestNext; } return sb.ToString(); } public void UpdateWall(string route, int moveCount) { int x = 0, y = 0; // 通過できた場所は確実に壁が無い for (var i = 0; i < moveCount; i++) { var pos = y * N + x; var c = route[i]; int edgeId; switch (c) { case 'U': edgeId = _grid.Cells[pos].EdgeIds[Direction.Up]; wallRateV[edgeId] = 0.0; y--; break; case 'D': edgeId = _grid.Cells[pos].EdgeIds[Direction.Down]; wallRateV[edgeId] = 0.0; y++; break; case 'L': edgeId = _grid.Cells[pos].EdgeIds[Direction.Left]; wallRateH[edgeId] = 0.0; x--; break; case 'R': edgeId = _grid.Cells[pos].EdgeIds[Direction.Right]; wallRateH[edgeId] = 0.0; x++; break; } } // 通過できなかった場所は壁がある、(正しく壁にぶつかったケース) // もしくは経路上のいずれか1箇所以上に壁がある(壁を誤認したケース) // (過去に通過したのにぶつかった場合は誤認であることが分かる) // 暫定で通過できなかった場所だけ壁率を上げる(計算も雑) { var pos = y * N + x; var c = route[moveCount]; int edgeId; switch (c) { case 'U': edgeId = _grid.Cells[pos].EdgeIds[Direction.Up]; if (wallRateV[edgeId] != 0.0) wallRateV[edgeId] = (wallRateV[edgeId] + (100 - _p) / 100.0) / 2; y--; break; case 'D': edgeId = _grid.Cells[pos].EdgeIds[Direction.Down]; if (wallRateV[edgeId] != 0.0) wallRateV[edgeId] = (wallRateV[edgeId] + (100 - _p) / 100.0) / 2; y++; break; case 'L': edgeId = _grid.Cells[pos].EdgeIds[Direction.Left]; if (wallRateH[edgeId] != 0.0) wallRateH[edgeId] = (wallRateV[edgeId] + (100 - _p) / 100.0) / 2; x--; break; case 'R': edgeId = _grid.Cells[pos].EdgeIds[Direction.Right]; if (wallRateH[edgeId] != 0.0) wallRateH[edgeId] = (wallRateV[edgeId] + (100 - _p) / 100.0) / 2; x++; break; } } } } public class Grid { public int Height; public int Width; public int AreaSize; public Cell[] Cells; public Grid(int height, int width) { Height = height; Width = width; AreaSize = height * width; InitCells(); Add4Connect(); SetEdgeId(); } void InitCells() { Cells = new Cell[AreaSize]; for (var y = 0; y < Height; y++) { for (var x = 0; x < Width; x++) { var pos = y * Width + x; Cells[pos] = new Cell() { X = x, Y = y, Pos = pos, RelationCells = new List() }; } } } /// 関係セルに4近傍の連結セルを追加する /// 立っているビットの位置のみ生成する 1:up 2:left 4:down 8:right public void Add4Connect(int mask = 15) { for (var y = 0; y < Height; y++) { for (var x = 0; x < Width; x++) { var pos = y * Width + x; var baseCell = Cells[pos]; var relation = new List(); baseCell.RelationCells = relation; // 上下左右でループしないケース用 if ((mask & 1) != 0 && y > 0) relation.Add(Cells[pos - Width]); // up if ((mask & 2) != 0 && x > 0) relation.Add(Cells[pos - 1]); // left if ((mask & 4) != 0 && y < Height - 1) relation.Add(Cells[pos + Width]); // down if ((mask & 8) != 0 && x < Width - 1) relation.Add(Cells[pos + 1]); // right } } } void SetEdgeId() { for (var y = 0; y < Height; y++) { for (var x = 0; x < Width; x++) { var pos = y * Width + x; var cell = Cells[pos]; cell.EdgeIds[Direction.Up] = x * (Height - 1) + y; cell.EdgeIds[Direction.Down] = x * (Height - 1) + y + 1; cell.EdgeIds[Direction.Left] = y * (Width - 1) + x; cell.EdgeIds[Direction.Right] = y * (Width - 1) + x + 1; } } } } public class Direction { public const int Up = 0; public const int Down = 1; public const int Left = 2; public const int Right = 3; } public class Cell { public int X; public int Y; public int Pos; /// 関係セル [index] public List RelationCells; public int[] EdgeIds = new int[4]; }