結果

問題 No.5006 Hidden Maze
ユーザー inani_waoninani_waon
提出日時 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/

ソースコード

diff #
プレゼンテーションモードにする

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]); // 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];
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0