結果
問題 | No.5006 Hidden Maze |
ユーザー |
![]() |
提出日時 | 2022-06-12 17:52:02 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 378 ms / 2,000 ms |
コード長 | 9,742 bytes |
コンパイル時間 | 8,137 ms |
実行使用メモリ | 56,920 KB |
スコア | 0 |
平均クエリ数 | 1001.00 |
最終ジャッジ日時 | 2022-06-12 17:53:16 |
合計ジャッジ時間 | 45,323 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
コンパイルメッセージ
Determining projects to restore... Restored /home/judge/data/code/main.csproj (in 105 ms). .NET 向け Microsoft (R) Build Engine バージョン 17.0.0-preview-21470-01+cb055d28f Copyright (C) Microsoft Corporation.All rights reserved. プレビュー版の .NET を使用しています。https://aka.ms/dotnet-core-preview をご覧ください main -> /home/judge/data/code/bin/Release/net6.0/main.dll main -> /home/judge/data/code/bin/Release/net6.0/publish/
ソースコード
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<int, double>();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.Append(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<Cell>() };}}}/// <summary>関係セルに4近傍の連結セルを追加する</summary>/// <param name="mask">立っているビットの位置のみ生成する 1:up 2:left 4:down 8:right</param>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<Cell>();baseCell.RelationCells = relation;// 上下左右でループしないケース用if ((mask & 1) != 0 && y > 0) relation.Add(Cells[pos - Width]); // upif ((mask & 2) != 0 && x > 0) relation.Add(Cells[pos - 1]); // leftif ((mask & 4) != 0 && y < Height - 1) relation.Add(Cells[pos + Width]); // downif ((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;/// <summary>関係セル [index]</summary>public List<Cell> RelationCells;public int[] EdgeIds = new int[4];}