ARC041-B アメーバ

問題へのリンク

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("3 3");
            WillReturn.Add("010");
            WillReturn.Add("101");
            WillReturn.Add("010");
            //000
            //010
            //000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 4");
            WillReturn.Add("0230");
            WillReturn.Add("2323");
            WillReturn.Add("0230");
            //0000
            //0230
            //0000
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 5");
            WillReturn.Add("00100");
            WillReturn.Add("03040");
            WillReturn.Add("20903");
            WillReturn.Add("05060");
            WillReturn.Add("00300");
            //00000
            //00100
            //02030
            //00300
            //00000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int[,] mAnswerBanArr;
    static int[,] mBanArr;
    static int UB_X;
    static int UB_Y;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mBanArr = CreateBanArr(InputList.Skip(1));
        UB_X = mBanArr.GetUpperBound(0);
        UB_Y = mBanArr.GetUpperBound(1);

        mAnswerBanArr = new int[UB_X + 1, UB_Y + 1];

        // 端のアメーバは、移動元を確定できるので、確定させる
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (mBanArr[LoopX, LoopY] == 0) continue;

                Action<int, int> UpdateAct = (pToX, pToY) =>
                {
                    int MoveVal = mBanArr[LoopX, LoopY];
                    mAnswerBanArr[pToX, pToY] += MoveVal;
                    ExecMinus(pToX, pToY, MoveVal);
                };

                if (LoopX == 0) UpdateAct(LoopX + 1, LoopY);
                if (LoopX == UB_X) UpdateAct(LoopX - 1, LoopY);
                if (LoopY == 0) UpdateAct(LoopX, LoopY + 1);
                if (LoopY == UB_Y) UpdateAct(LoopX, LoopY - 1);
            }
        }

        // 4近傍全てにアメーバがいたら、その最小数の移動元にする
        for (int LoopX = 1; LoopX <= UB_X - 1; LoopX++) {
            for (int LoopY = 1; LoopY <= UB_Y - 1; LoopY++) {
                var CntList = new List<int>();
                CntList.Add(mBanArr[LoopX, LoopY - 1]);
                CntList.Add(mBanArr[LoopX, LoopY + 1]);
                CntList.Add(mBanArr[LoopX - 1, LoopY]);
                CntList.Add(mBanArr[LoopX + 1, LoopY]);
                if (CntList.TrueForAll(pX => pX > 0)) {
                    int MoveVal = CntList.Min();
                    mAnswerBanArr[LoopX, LoopY] += MoveVal;
                    ExecMinus(LoopX, LoopY, MoveVal);
                }
            }
        }
        PrintBan(mAnswerBanArr);
    }

    // 指定した座標の4近傍から、引数の値を引く
    static void ExecMinus(int pX, int pY, int pMinusVal)
    {
        mBanArr[pX, pY - 1] -= pMinusVal;
        mBanArr[pX, pY + 1] -= pMinusVal;
        mBanArr[pX - 1, pY] -= pMinusVal;
        mBanArr[pX + 1, pY] -= pMinusVal;
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をintの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static int[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new int[0, 0];
        }

        int UB_X = StrList[0].Length - 1;
        int UB_Y = StrList.Count - 1;

        int[,] WillReturn = new int[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] - '0';
            }
        }
        return WillReturn;
    }

    ////////////////////////////////////////////////////////////////
    // 2次元配列(int型)のデバッグ出力
    ////////////////////////////////////////////////////////////////
    static void PrintBan(int[,] pBanArr)
    {
        for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
                Console.Write(pBanArr[X, Y]);
            }
            Console.WriteLine();
        }
    }
}

解説

まず、端に存在するアメーバは、移動元を確定できるので確定させます。

次に、左上から右下へのループで、
4近傍全てにアメーバが存在する座標から調べ、
移動元のアメーバーの数を確定させてます。