AOJ 0092 正方形探索

■■■問題■■■

縦にn行、横にn列並べられた、合計 n×n のマス目があります。
いくつかのマス目には印がついています。

各マス目の印の状態を読み込み、印のついていないマス目だけからなる
最大の正方形の辺の長さを出力として表示するプログラムを作成してください。

たとえば各データセットで以下のようなデータが与えられます。

10
...*....**
..........
**....**..
........*.
..*.......
..........
.*........
..........
....*..***
.*....*...

入力データの一行が、一行のマス目を表現します。
入力データの文字列のうち、
.（ピリオド）は印のついていないマス目、
*（アスタリスク）は印のついているマス目を示しています。

上記の例では、下図の0で示される正方形が最大となります。

...*....**
..........
**....**..
...00000*.
..*00000..
...00000..
.*.00000..
...00000..
....*..***
.*....*...

よって、5と出力すれば正解になります。

なお、すべてのマス目に印がついている場合には、0を出力してください。

■■■入力■■■

上記形式で複数のデータセットが与えられます。
nが0のとき入力の最後とします。
nは1000以下とします。
入力データの文字列には、ピリオド、アスタリスク、改行以外の文字は含まれません。
データセットの数は50を超えません。

■■■出力■■■

各データセットに対し、最大の正方形の辺の長さ (整数) を１行に出力して下さい。

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

    static IEnumerable<string> GetInputEnum()
    {
        if (InputPattern == "Input1") {
            yield return "10";
            yield return "...*....**";
            yield return "..........";
            yield return "**....**..";
            yield return "........*.";
            yield return "..*.......";
            yield return "..........";
            yield return ".*........";
            yield return "..........";
            yield return "....*..***";
            yield return ".*....*...";
            yield return "10";
            yield return "****.*****";
            yield return "*..*.*....";
            yield return "****.*....";
            yield return "*....*....";
            yield return "*....*****";
            yield return "..........";
            yield return "****.*****";
            yield return "*..*...*..";
            yield return "****...*..";
            yield return "*..*...*..";
            yield return "0";
            //5
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) yield return wkStr;
        }
    }

    static int UB;

    static void Main()
    {
        IEnumerable<string> InputEnum = GetInputEnum();

        int CurrY = -1;

        char[,] BanArr = null;

        foreach (string EachStr in InputEnum) {
            if (CurrY == -1) {
                int n = int.Parse(EachStr);
                if (n == 0) return;
                UB = n - 1;

                CurrY = 0;
                BanArr = new char[UB + 1, UB + 1];
                continue;
            }

            for (int X = 0; X <= UB; X++) {
                BanArr[X, CurrY] = EachStr[X];
            }
            if (++CurrY > UB) {
                EachSolve(BanArr);
                CurrY = -1;
            }
        }
    }

    static void EachSolve(char[,] pBanArr)
    {
        int[,] CntArr = new int[UB + 1, UB + 1];

        Func<int, int, int> wkFunc = (pX, pY) =>
        {
            if (pX < 0 || UB < pX) return 0;
            if (pY < 0 || UB < pY) return 0;

            return CntArr[pX, pY];
        };

        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                if (pBanArr[LoopX, LoopY] == '*') //印のついているマスの場合
                    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;
                }
            }
        }
        Console.WriteLine(CntArr.Cast<int>().Max());
    }
}

解説

下記のロジックで、2次元配列を順に走査して最大正方形を求めてます。
●印のついているマスなら0をセット
●印のついてないマスなら、(左、左上、上の3つの座標の中での最小値)+1をセット