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; } }