問題は ：
1.s と 0 を含む次数 M x N の行列が与えられた場合、形成できる最大正方形の数を見つける必要があります。正方形は、1 を含む隣接するセルをグループ化することによって形成されます。最大正方形は、別の正方形に完全に含まれていない正方形です。部分的に重なり合う最大の正方形は、別々にカウントされます。単位正方形 (辺の長さ = 1) もカウントする必要があります。四角形は塗りつぶされていることに注意してください。つまり、0.s を含めることはできません。可能な限り最良のアルゴリズムは何ですか?
例 ：
次の 4x5 行列の場合、入力は次のようになります。
入力と出力の例:
11001
11110
11011
11001
出力：
9
S(i,j)を右下隅の最大正方形のサイズとする(i,j)。(私のインデックスは上から下、左から右に実行され、1 から始まります。) 全体SはM x N整数の行列です。コンピューティングSは、動的計画法の非常に古典的な問題であり、O(MN) 時間の計算量を持つことが知られています。(覚えていない場合は、次のようにしますA。 が入力行列であるとします。 S(i,j) = 0ifA(i,j) = 0を設定し、 S(i,j) = min(S(i-1,j), S(i,j-1), S(i-1,j-1))+1ifを設定します。必要に応じてA(i,j) = 1設定S(0,j) = S(i,0) = 0できます。)
次に、行列を調べて最大二乗を抽出しますS。がゼロでなく、 、およびより大きいか等しい(i,j)場合に限り、 が右下隅の正方形は最大になります。(お好みで設定してください。) このステップにも O(MN) 時間がかかります。S(i,j)S(i+1,j)S(i,j+1)S(i+1,j+1)S(M+1,j) = 0S(i,N+1) = 0
可能な 4x4 の正方形の左上は (0,0) と (1,0) です。
考えられる 3x3 の正方形は、(0,0)、(1,0)、(2,0)、(0,1)、(1,1)、(2,1) に左上があります。
考えられる 2x2 の正方形は、左上が (0,0)、(1,0)、(2,0)、(3,0)、(0,1)、(1,1)、(2,1)、 (3,1)、(0,2)、(1,2)、(2,2)、(3,2)。
考えられる 1x1 の正方形は、すべての座標で左上になります。
したがって、アルゴリズムは次のようになります。
4x4 のテストから開始し、すべて 1 の場合は、4x4 に属するものとしてマークし、カウントを増やします。
次に、3x3 をテストし、すべてが 1 で、4x4 に属するものとしてマークされていない場合は、3x3 に属するものとしてマークし、カウントをインクリメントします。
次に、2x2 をテストし、すべてが 1 で、4x4 または 3x3 に属するものとしてマークされていない場合は、2x2 に属するものとしてマークし、カウントをインクリメントします。
次に、1x1 をテストし、1 でまったくマークされていない場合は、カウントを増やします。
カウントを返します。
セルをマークする方法は言語固有です。たとえば、C ではビットフィールドを使用します。
編集:楽しみのために、Bitset を使用して Java でこれを実装しました。
import java.util.BitSet;
public class Program
{
// Right-shift bits by 'n' places
private static BitSet RightShift(BitSet x, int n)
{
return x.get(n, Math.max(n, x.length()));
}
// Test square of dimension 'size' with top-left at position (h,w) for maximal-ness
public static boolean IsMaximalSquare(BitSet [][] matrix, int h, int w, int size)
{
boolean isMaximal = true;
for (int a = 0; a < size; a++)
{
for (int b = 0; b < size; b++)
{
BitSet x = matrix[h + a][w + b];
if (!x.get(0))
return false;
x = RightShift(x, size + 1);
if (!x.isEmpty())
isMaximal = false;
}
}
if (!isMaximal)
return false;
for (int a = 0; a < size; a++)
{
for (int b = 0; b < size; b++)
matrix[h + a][w + b].set(size);
}
return true;
}
// Populate a 2d array of bitsets from string array
public static BitSet [][] BuildMatrix(String rows[])
{
BitSet [][] matrix = new BitSet[4][5];
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 5; j++)
{
matrix[i][j] = new BitSet(5);
matrix[i][j].set(0, '1' == rows[i].charAt(j));
}
}
return matrix;
}
// Return number of maximal squares from string representation of array
public static int Solve(String rows[])
{
BitSet [][] matrix = BuildMatrix(rows);
int count = 0;
for (int size = 4; size > 0; size--) // test squares of size 4x4, 3x3, 2x2 and 1x1
{
for (int h = 0; h < 5 - size; h++) // iterate the rows
{
for (int w = 0; w < 6 - size; w++) // iterate the columns
{
if (IsMaximalSquare(matrix, h, w, size))
count++;
}
}
}
return count;
}
public static void main(String[] args)
{
String rows1[] = {"11001","11110","11011","11001"}; // original question
String rows2[] = {"11111","11111","11111","11111"}; // additional test case 1
String rows3[] = {"00000","00000","00000","00000"}; // additional test case 2
String rows4[] = {"11100","11111","11111","00111"}; // additional test case 3
String rows5[] = {"11101","11111","11111","10111"}; // additional test case 4
System.out.println(Solve(rows1));
System.out.println(Solve(rows2));
System.out.println(Solve(rows3));
System.out.println(Solve(rows4));
System.out.println(Solve(rows5));
}
}