結果

問題 No.157 2つの空洞
ユーザー aketijyuuzou
提出日時 2024-10-10 23:01:10
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 30 ms / 2,000 ms
コード長 6,230 bytes
コンパイル時間 987 ms
コンパイル使用メモリ 108,800 KB
実行使用メモリ 18,048 KB
最終ジャッジ日時 2024-10-10 23:01:12
合計ジャッジ時間 2,409 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

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

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("9 5");
WillReturn.Add("#########");
WillReturn.Add("#.####.##");
WillReturn.Add("#..###.##");
WillReturn.Add("#..###..#");
WillReturn.Add("#########");
//3
//1
//32
}
else if (InputPattern == "Input2") {
WillReturn.Add("8 5");
WillReturn.Add("########");
WillReturn.Add("####..##");
WillReturn.Add("#..#..##");
WillReturn.Add("#...####");
WillReturn.Add("########");
//1
//12
}
else if (InputPattern == "Input3") {
WillReturn.Add("9 9");
WillReturn.Add("#########");
WillReturn.Add("#.......#");
WillReturn.Add("#.#####.#");
WillReturn.Add("#.#...#.#");
WillReturn.Add("#.#.#.#.#");
WillReturn.Add("#.#...#.#");
WillReturn.Add("#.#####.#");
WillReturn.Add("#.......#");
WillReturn.Add("#########");
//1
//2
}
else if (InputPattern == "Input4") {
WillReturn.Add("8 6");
WillReturn.Add("########");
WillReturn.Add("#....###");
WillReturn.Add("#.######");
WillReturn.Add("#.####.#");
WillReturn.Add("#.######");
WillReturn.Add("########");
//3
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct PointDef
{
internal int X;
internal int Y;
}
//
static List<PointDef> SpacePointList;
//
static PointDef[] RenketuSpacePointArr;
static int UB_X;
static int UB_Y;
static void Main()
{
List<string> InputList = GetInputList();
InputList.RemoveAt(0);
UB_X = InputList[1].Length - 1;
UB_Y = InputList.Count - 1;
char[,] BanArr = new char[UB_X + 1, UB_Y + 1];
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
BanArr[LoopX, LoopY] = InputList[LoopY][LoopX];
}
}
//PrintBan(BanArr);
//List
SpacePointList = DeriveSpacePointList(BanArr);
//
RenketuSpacePointArr = DeriveRenketuSpacePointArr(BanArr);
//Console.WriteLine("");
//foreach (PointDef EachPoint in RenketuSpacePointArr) {
// Console.Write("({0},{1}),", EachPoint.X, EachPoint.Y);
//}
//Console.WriteLine();
int Answer = int.MaxValue;
//Remove
SpacePointList.RemoveAll(A => Array.Exists(RenketuSpacePointArr,
B => B.X == A.X && B.Y == A.Y));
foreach (PointDef EachPoint1 in RenketuSpacePointArr) {
foreach (PointDef EachPoint2 in SpacePointList) {
//
int wkKyori = Math.Abs(EachPoint1.X - EachPoint2.X);
wkKyori += Math.Abs(EachPoint1.Y - EachPoint2.Y);
if (Answer > wkKyori)
Answer = wkKyori;
}
}
Console.WriteLine(Answer - 1);
}
//List
static List<PointDef> DeriveSpacePointList(char[,] pBanArr)
{
var WillReturn = new List<PointDef>();
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
if (pBanArr[LoopX, LoopY] != '.') continue;
WillReturn.Add(new PointDef() { X = LoopX, Y = LoopY });
}
}
return WillReturn;
}
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
}
//UnionFind
static PointDef[] DeriveRenketuSpacePointArr(char[,] pBanArr)
{
var VisitedList = new List<PointDef>();
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = SpacePointList[0].X;
WillPush.CurrY = SpacePointList[0].Y;
stk.Push(WillPush);
VisitedList.Add(SpacePointList[0]);
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
Action<int, int> PushAct = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB_X < pNewX) return;
if (pNewY < 0 || UB_Y < pNewY) return;
if (pBanArr[pNewX, pNewY] != '.') return;
//
if (VisitedList.Exists(A => A.X == pNewX && A.Y == pNewY))
return;
VisitedList.Add(new PointDef() { X = pNewX, Y = pNewY });
WillPush.CurrX = pNewX;
WillPush.CurrY = pNewY;
stk.Push(WillPush);
};
PushAct(Popped.CurrX, Popped.CurrY - 1);
PushAct(Popped.CurrX, Popped.CurrY + 1);
PushAct(Popped.CurrX - 1, Popped.CurrY);
PushAct(Popped.CurrX + 1, Popped.CurrY);
}
return VisitedList.ToArray();
}
//
static void PrintBan(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0