結果
問題 | No.157 2つの空洞 |
ユーザー |
![]() |
提出日時 | 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.
ソースコード
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つずつある。//壁を3つどければ2つの空洞はつながる。}else if (InputPattern == "Input2") {WillReturn.Add("8 5");WillReturn.Add("########");WillReturn.Add("####..##");WillReturn.Add("#..#..##");WillReturn.Add("#...####");WillReturn.Add("########");//1//壁を1つどければ2つの空洞はつながる。}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;//片方の空洞の連結空白をRemoveSpacePointList.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());}}