結果

問題 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つずつある。
            //壁を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;

        //片方の空洞の連結空白を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());
    }
}
0