日々精進

新しく学んだことを書き留めていきます

SRM494 Div1 Easy

TopCoder Statistics - Problem Statement
問題文
キャンバスの各点ごとに白のままとしておくべきところ、黒く塗るべきところを指示される。
指示通りに塗ることができる最大の正方形の大きさを求めなさい。
方針
DPを使って各点を最も右下とする最大の正方形の大きさを求める。
その後、各点を塗ることができる最大の正方形の大きさを求める。


入力は以下のように与えられます。(文字列の配列として渡される。)
BBBB
BBBB
WBBB
BBBB
BBBB
BBBB

DPを使って各点を最も右下とする最大の正方形の大きさを求めると↓となります。
1111
1222
0123
1123
1223
1233

たとえば、[1,1]には2が入っているため、[0,0],[0,1],[1,0]は大きさ2の正方形で塗れることがわかります。
そこで、[0,0],[0,1],[1,0]を2に書き換えます。
2211
2222
0123
1123
1223
1233

これを繰り返すと最終的に以下となります。
2333
2333
0333
3333
3333
3333

[0,0],[0,1]は大きさ2の正方形でしか塗れないため、この絵を描ける最大の正方形の辺の長さは2となります。

上記処理を実装したコードは以下となります。

using System;
using System.Collections.Generic;
using System.Text;

public class Painting
{
    public int largestBrush(string[] picture)
    {
        int h = picture.Length;
        int w = picture[0].Length;
        int[,] dp = new int[w, h];
        for (int i = 0; i < w; i++)
            for (int j = 0; j < h; j++)
                if (picture[j][i].Equals('B'))
                    dp[i, j] = 1;

        for (int y = 1; y < h; y++)
            for (int x = 1; x < w; x++)
                if (dp[x, y].Equals(1))
                    dp[x, y] = Math.Min(Math.Min(dp[x - 1, y], dp[x, y - 1]), dp[x - 1, y - 1]) + 1;

        for(int x = 0;x < w;x++)
            for(int y = 0;y < h;y++)
                if(dp[x, y] != 0)
                {
                    int maxSize = dp[x, y];
                    for (int i = x - maxSize + 1; i <= x; i++)
                        for (int j = y - maxSize + 1; j <= y; j++)
                            if(dp[i, j] < maxSize)
                                dp[i, j] = maxSize;
                }

        int ans = int.MaxValue;
        for (int y = 0; y < h; y++)
            for (int x = 0; x < w; x++)
                if (!dp[x, y].Equals(0))
                    ans = Math.Min(ans, dp[x, y]);
        return ans;
    }

    // debug用
    public string debugPrint(int[,] nums)
    {
        string str = "";
        for(int i = 0;i < nums.GetLength(1);i++)
        {
            for (int j = 0;j < nums.GetLength(0); j++)
                str += nums[j, i];
            str += "\n";
        }
        return str;
    }
}