ABC443-E Climbing Silver

問題へのリンク

C#のソース

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("5");
            WillReturn.Add("5 3");
            WillReturn.Add(".###.");
            WillReturn.Add("..#..");
            WillReturn.Add("#.#.#");
            WillReturn.Add("#...#");
            WillReturn.Add("##..#");
            WillReturn.Add("2 2");
            WillReturn.Add("##");
            WillReturn.Add("..");
            WillReturn.Add("4 1");
            WillReturn.Add("####");
            WillReturn.Add("####");
            WillReturn.Add("####");
            WillReturn.Add(".###");
            WillReturn.Add("3 3");
            WillReturn.Add("...");
            WillReturn.Add("...");
            WillReturn.Add("...");
            WillReturn.Add("10 3");
            WillReturn.Add("##.##.##.#");
            WillReturn.Add(".####..#..");
            WillReturn.Add("...#.#..#.");
            WillReturn.Add(".#.#.#.#..");
            WillReturn.Add("...####...");
            WillReturn.Add("#.#.##....");
            WillReturn.Add(".##...#...");
            WillReturn.Add("#.##.....#");
            WillReturn.Add("#....###.#");
            WillReturn.Add(".#..#.#...");
            //10111
            //11
            //1000
            //111
            //0011010010
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        int CurrInd = 1;
        while (CurrInd < InputList.Count - 1) {
            SplitAct(InputList[CurrInd]);

            long N = wkArr[0];
            long C = wkArr[1] - 1;

            char[,] BanArr = CreateBanArr(InputList.Skip(CurrInd + 1).Take((int)N));

            string Result = Solve(C, BanArr);
            Console.WriteLine(Result);

            CurrInd += 1 + (int)N;
        }
    }

    static string Solve(long pC, char[,] pBanArr)
    {
        long UB = pBanArr.GetUpperBound(0);

        // Y座標のList[X座標]なDict
        var YListDict = new Dictionary<long, List<long>>();

        for (long X = 0; X <= UB; X++) {
            YListDict[X] = new List<long>();
        }

        for (long X = 0; X <= UB; X++) {
            for (long Y = 0; Y <= UB; Y++) {
                if (pBanArr[X, Y] == '#') {
                    YListDict[X].Add(Y);
                }
            }
        }

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrX = pC;
        WillEnqueue.CurrY = UB;
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<long>();

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            // クリア判定
            if (Dequeued.CurrY == 0) continue;

            Action<long, long> EnqueueAct = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB < pNewX) return;

                if (pBanArr[pNewX, pNewY] == '#') {
                    var CurrYList = YListDict[pNewX];
                    if (GetListRangeValueCnt.GetMoreStrictCnt(CurrYList, pNewY) > 0) {
                        return;
                    }
                    CurrYList.Clear();
                }
                long Hash = GetHash(pNewX, pNewY);
                if (VisitedSet.Add(Hash)) {
                    WillEnqueue.CurrX = pNewX;
                    WillEnqueue.CurrY = pNewY;
                    Que.Enqueue(WillEnqueue);
                }
            };
            EnqueueAct(Dequeued.CurrX - 1, Dequeued.CurrY - 1);
            EnqueueAct(Dequeued.CurrX + 0, Dequeued.CurrY - 1);
            EnqueueAct(Dequeued.CurrX + 1, Dequeued.CurrY - 1);
        }

        var sb = new System.Text.StringBuilder();
        for (long X = 0; X <= UB; X++) {
            long Hash = GetHash(X, 0);
            if (VisitedSet.Contains(Hash)) {
                sb.Append(1);
            }
            else {
                sb.Append(0);
            }
        }

        return sb.ToString();
    }

    struct JyoutaiDef
    {
        internal long CurrX;
        internal long CurrY;
    }

    // 座標のハッシュ値
    static long GetHash(long pX, long pY)
    {
        return pX * 10000 + pY;
    }

    ////////////////////////////////////////////////////////////////
    // 2次元配列(char型)のデバッグ出力
    ////////////////////////////////////////////////////////////////
    static void PrintBan(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }
    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をcharの2次元配列に設定
    ////////////////////////////////////////////////////////////////
    static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new char[0, 0];
        }
        int UB_X = StrList[0].Length - 1;
        int UB_Y = StrList.Count - 1;

        char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = StrList[Y][X];
            }
        }
        return WillReturn;
    }
}

#region GetListRangeValueCnt
// {昇順にソートされたList,Min,Max}を引数とし、
// Min以上Max以下な値の個数を返す
internal class GetListRangeValueCnt
{
    // 機能01 Min以上な値の個数を返す
    static internal long GetMoreOrEqualCnt(List<long> pSortedList, long pMinVal)
    {
        int ResultInd = ExecNibunhou_LowerBound(pMinVal, pSortedList);

        if (ResultInd == -1) return 0;
        return (pSortedList.Count - 1) - ResultInd + 1;
    }

    // 機能02 Min超えな値の個数を返す
    static internal long GetMoreStrictCnt(List<long> pSortedList, long pMinVal)
    {
        int ResultInd = ExecNibunhou_UpperBound(pMinVal, pSortedList);

        if (ResultInd == -1) return 0;
        return (pSortedList.Count - 1) - ResultInd + 1;
    }

    // 機能03 Max以下な値の個数を返す
    static internal long GetLessOrEqualCnt(List<long> pSortedList, long pMaxVal)
    {
        int ResultInd = ExecNibunhou_LowerOrEqual_Max(pMaxVal, pSortedList);

        if (ResultInd == -1) return 0;
        return ResultInd + 1;
    }

    // 機能04 Max未満な値の個数を返す
    static internal long GetLessStrictCnt(List<long> pSortedList, long pMaxVal)
    {
        int ResultInd = ExecNibunhou_LowerMax(pMaxVal, pSortedList);

        if (ResultInd == -1) return 0;
        return ResultInd + 1;
    }

    // 機能05 Min以上Max以下な値の個数を返す
    static internal long GetRangeCnt(List<long> pSortedList, long pMinVal, long pMaxVal)
    {
        if (pMinVal > pMaxVal) {
            throw new Exception("pMinVal > pMaxVal");
        }

        int ResultInd1 = ExecNibunhou_LowerBound(pMinVal, pSortedList);
        if (ResultInd1 == -1) return 0;

        int ResultInd2 = ExecNibunhou_LowerOrEqual_Max(pMaxVal, pSortedList);
        if (ResultInd2 == -1) return 0;

        return ResultInd2 - ResultInd1 + 1;
    }

    // 二分法で、Val以上で最小の値を持つ、添字を返す
    static private int ExecNibunhou_LowerBound(long pVal, List<long> pList)
    {
        if (pList.Count == 0) return -1;

        // 最後の要素がVal未満の特殊ケース
        if (pVal > pList[pList.Count - 1]) {
            return -1;
        }
        // 最初の要素がVal以上の特殊ケース
        if (pVal <= pList[0]) {
            return 0;
        }

        int L = 0;
        int R = pList.Count - 1;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (pList[Mid] >= pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }

    // 二分法で、Val超えで最小の値を持つ、添字を返す
    static private int ExecNibunhou_UpperBound(long pVal, List<long> pList)
    {
        // 要素が0件のケース
        if (pList.Count == 0) return -1;

        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pList[pList.Count - 1]) {
            return -1;
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pList[0]) {
            return 0;
        }

        int L = 0;
        int R = pList.Count - 1;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (pList[Mid] > pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }

    // 二分法で、Val以下で最大の値を持つ、添字を返す
    static private int ExecNibunhou_LowerOrEqual_Max(long pVal, List<long> pList)
    {
        if (pList.Count == 0) return -1;

        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pList[pList.Count - 1]) {
            return pList.Count - 1;
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pList[0]) {
            return -1;
        }

        int L = 0;
        int R = pList.Count - 1;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (pList[Mid] <= pVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }

    // 二分法で、Val未満で最大の値を持つ、添字を返す
    static private int ExecNibunhou_LowerMax(long pVal, List<long> pList)
    {
        if (pList.Count == 0) return -1;

        // 最後の要素がVal未満の特殊ケース
        if (pVal > pList[pList.Count - 1]) {
            return pList.Count - 1;
        }
        // 最初の要素がVal以上の特殊ケース
        if (pVal <= pList[0]) {
            return -1;
        }

        int L = 0;
        int R = pList.Count - 1;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (pList[Mid] < pVal) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        return L;
    }
}
#endregion

解説

BFSでY座標の降順に、訪問可能な座標を求めてます。
訪問可否に興味があるので、
X座標ごとで、いずれかの壁に訪問可能であれば、そのX座標の壁には全て訪問可能です。
なので、BFS全体での計算量削減で、そのX座標の壁をClearしてます。

ダイソーのオセロセットで
下記の盤面を用意すると分かりやすいです。

□□壁□壁壁□壁
壁□□□□壁壁壁
壁□壁□壁□壁□
□壁□壁□□□壁
壁□□□□□壁□
□壁□□□壁□□
□□壁□壁壁□□
□□□Ｓ□壁□□