結果
| 問題 | No.5006 Hidden Maze |
| ユーザー |
 inani_waon
|
| 提出日時 | 2022-06-12 19:13:18 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 511 ms / 2,000 ms |
| コード長 | 9,775 bytes |
| コンパイル時間 | 10,677 ms |
| 実行使用メモリ | 57,820 KB |
| スコア | 4,900 |
| 平均クエリ数 | 952.00 |
| 最終ジャッジ日時 | 2022-06-12 19:14:20 |
| 合計ジャッジ時間 | 56,842 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
コンパイルメッセージ
Determining projects to restore... Restored /home/judge/data/code/main.csproj (in 107 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 = 10000.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 + Math.Pow(wallCost, wallRate);
priorityQueue.Enqueue(pos - N, currentCost + cost);
}
if (cell.Y < N - 1)
{
var wallRate = wallRateV[cell.EdgeIds[Direction.Down]];
var cost = 1 + Math.Pow(wallCost, wallRate);
priorityQueue.Enqueue(pos + N, currentCost + cost);
}
if (cell.X > 0)
{
var wallRate = wallRateH[cell.EdgeIds[Direction.Left]];
var cost = 1 + Math.Pow(wallCost, wallRate);
priorityQueue.Enqueue(pos - 1, currentCost + cost);
}
if (cell.Y < N - 1)
{
var wallRate = wallRateH[cell.EdgeIds[Direction.Right]];
var cost = 1 + Math.Pow(wallCost, wallRate);
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<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]); // 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;
/// <summary>関係セル [index]</summary>
public List<Cell> RelationCells;
public int[] EdgeIds = new int[4];
}