AOJ本-999 最大正方形

■■■問題■■■

一辺が1cm のタイルが、H × W 個並べられています。
タイルは汚れているもの、綺麗なもののいずれかです。
綺麗なタイルのみを使ってできる正方形の面積の最大値を求めてください。

■■■入力■■■

H W
c1,1 c1,2 ・・・ c1,W
c2,1 c2,2 ・・・ c2,W
・
・
・
cH,1 cH,2 ・・・ cH,W

１行目に２つの整数 H、W が空白区切りで与えられます。
続くH行でタイルを表す H × W 個の整数 ci,j が与えられます。
ci,j が1のとき汚れたタイル、0のとき綺麗なタイルを表します。

●1 <= H, W <= 1400

■■■出力■■■

面積の最大値を１行に出力してください。

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("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 int UB_X;
    static int UB_Y;

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

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

        int H = wkArr[0];
        int W = wkArr[1];

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

        for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
            SplitAct(InputList[LoopY + 1]);
            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                BanArr[LoopX, LoopY] = wkArr[LoopX];
            }
        }

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

        Func<int, int, int> wkFunc = (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 = wkFunc(LoopX - 1, LoopY - 1);
                    int Cnt2 = wkFunc(LoopX, LoopY - 1);
                    int Cnt3 = wkFunc(LoopX - 1, LoopY);

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

                    CntArr[LoopX, LoopY] = wkMin + 1;
                }
            }
        }

        int MaxSeihoukeiLength = CntArr.Cast<int>().Max();
        Console.WriteLine(MaxSeihoukeiLength * MaxSeihoukeiLength);
    }
}

解説

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