DPL_3_A: Largest Square

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// Q076 最大正方形 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_A&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 5");
            WillReturn.Add("0 0 1 0 0");
            WillReturn.Add("1 0 0 0 0");
            WillReturn.Add("0 0 0 1 0");
            WillReturn.Add("0 0 0 1 0");
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        int H = wkArr[0];
        int W = wkArr[1];

        int UB_X = W - 1;
        int UB_Y = H - 1;

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

        for (int I = 1; I <= H; I++) {
            SplitAct(InputList[I]);
            for (int J = 0; J <= wkArr.GetUpperBound(0); J++) {
                BanArr[J, I - 1] = wkArr[J];
            }
        }

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

        Func<int, int, int> GetValFunc = (pX, pY) =>
        {
            if (pX < 0 || UB_X < pX) return 0;
            if (pY < 0 || UB_Y < pY) return 0;

            return CntArr[pX, pY];
        };

        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (BanArr[LoopX, LoopY] == 1)
                    CntArr[LoopX, LoopY] = 0;
                else {
                    int Cnt1 = GetValFunc(LoopX - 1, LoopY - 1);
                    int Cnt2 = GetValFunc(LoopX, LoopY - 1);
                    int Cnt3 = GetValFunc(LoopX - 1, LoopY);

                    int CntMin = Math.Min(Cnt1, Cnt2);
                    CntMin = Math.Min(CntMin, Cnt3);

                    CntArr[LoopX, LoopY] = CntMin + 1;
                }
            }
        }
        int MaxSeihoukeiLength = CntArr.Cast<int>().Max();
        Console.WriteLine(MaxSeihoukeiLength * MaxSeihoukeiLength);
    }

    // 2次元配列のデバッグ出力
    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();
        }
    }
}

解説

最大の正方形は、下記のロジックで、2次元配列を順に走査して求めることができます。
●汚れたタイルなら0をセット
●綺麗なタイルなら、(左、左上、上の3つの座標の中での最小値)+1をセット

yukicoder402 最も海から遠い場所