刚才看了http://topic.csdn.net/u/20120307/10/9cec9f97-a27f-41d5-a6f1-559f81ad6797.html?6310，鄙人这里也有一道题，特此分享。我们有一个正方形的矩阵，里面的元素不是1就是0。我们要做的工作就是统计里面全部为1的小正方形(大小至少是2x2的)的个数。比如说：
101111
001111
111111
001111
101101
111001对于这个矩阵我们可以得到结果：
2 10
3 4
4 1 意思是里面有2x2的且全部元素为1的矩阵10个，3x3的且全部元素为1的矩阵4个，4x4的且全部元素为1的矩阵1个。这个题目网上有，大家自己想想吧，很有意思的。
101111
001111
111111
001111
101101
111001对于这个矩阵我们可以得到结果：
2 10
3 4
4 1 意思是里面有2x2的且全部元素为1的矩阵10个，3x3的且全部元素为1的矩阵4个，4x4的且全部元素为1的矩阵1个。这个题目网上有，大家自己想想吧，很有意思的。
思路，来看一下一个n*n(假设n为3)的子矩阵的情况
1 0 0 1
1 1 0 1
1 1 n 1
0 1 1 n+1
那么，(0,0)到(n,n)是否满足都是1的情况，就是该矩阵的和是否=n*n，比如一个2x2矩阵，全部元素都是1，则所有元素的和为2*2=4，一个3x3矩阵，如果全部元素都是1，则所有元素的和为3*3=9，等等
那么，从某个点开始求一个n*n矩阵的和很简单，这里采用了取巧的方法，当从n*n矩阵变到(n+1)*(n+1)矩阵的时候，实际上矩阵的和就是在n*n矩阵的和的基础上，加上n+1所在的行和列的元素的和，这样，我们就不用每次都从头开始计算一次矩阵的和，只需要循环不断的增加n，并加上n所在的行和列的值求总和，然后判断和是否满足n*n就可以了
import java.util.*;
public class Test {
public static void main(String[] args) throws Throwable {
int[][] matrix = {
{1,0,1,1,1,1},
{0,0,1,1,1,1},
{1,1,1,1,1,1},
{0,0,1,1,1,1},
{1,0,1,1,0,1},
{1,1,1,0,0,1}
};
countMatrix(matrix);
} public static void countMatrix(int[][] matrix) {
if (matrix==null || matrix.length==0 || matrix[0].length==0) {
System.out.println("no matrix.");
return;
} List<Integer> list = new ArrayList<Integer>(); //用集合保存每种矩阵的个数
for (int i=0; i<matrix.length; i++) {
list.add(0); //list(0)保存1x1矩阵的个数，list(1)保存2x2矩阵个数，等等
} int sum = 0;
for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[i].length; j++) {
sum = 0; //如果不统计1x1矩阵，把这里初始化为 sum = matrix[i][j];
//然后把下面的for循环改为从k=1开始就可以了
for (int k=0; i+k<matrix.length && j+k<matrix[i].length; k++) {
//从某个(i,j)点开始，不断地寻找k*k矩阵，k循环增大
if (k==0) {
sum += matrix[i][j]; //计算矩阵起点的值
} else {
for (int m=0; m<k; m++) {
sum += matrix[i+m][j+k]; //计算k元素所在的行和列的值
sum += matrix[i+k][j+m]; //这里不包含k元素本身
}
sum += matrix[i+k][j+k]; //计算k元素本身的值
}
if (sum == (k+1)*(k+1)) { //判断矩阵元素的和是否满足n*n
list.set(k, list.get(k)+1); //把结果保存到集合中
}
}
}
} for (int i=0; i<list.size(); i++) {
System.out.printf("matrix:%dx%d, count:%d\n", i+1, i+1, list.get(i));
}
}
}
你的算法是四次方级的
你可以跑一下下面这个数据试试 看看能不能在0.01秒内出结果
http://115.com/file/c2ls6epi
#input.txt
修改了一下程序，思路不变，采用boolean类型，判断n*n的子矩阵中，只要有一个元素为0，就不符合条件，退出下一层矩阵(n+1)*(n+1)的循环修改的程序跑了一遍你的测试数据input.txt，忽略文件读入的时间，算法上所花时间我的机器上为31毫秒
import java.util.*;
public class Test {
public static void main(String[] args) throws Throwable {
/*
char[][] matrix = {
{'1','0','1','1','1','1'},
{'0','0','1','1','1','1'},
{'1','1','1','1','1','1'},
{'0','0','1','1','1','1'},
{'1','0','1','1','0','1'},
{'1','1','1','0','0','1'}
};
*/
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("f:\\input.txt")));
List<char[]> data = new ArrayList<char[]>();
for (String buf=br.readLine(); buf!=null; buf=br.readLine()) {
data.add(buf.toCharArray());
}
char[][] matrix = new char[data.size()][];
for (int i=0; i<matrix.length; i++) {
matrix[i] = data.get(i);
}
long t1 = System.currentTimeMillis();
countMatrix(matrix);
long t2 = System.currentTimeMillis();
System.out.printf("time=%dms\n", t2-t1);
} public static void countMatrix(char[][] matrix) {
if (matrix==null || matrix.length==0 || matrix[0].length==0) {
System.out.println("no matrix.");
return;
} List<int[]> list = new ArrayList<int[]>();
boolean f = true;
for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[i].length; j++) {
if (matrix[i][j] == '0') continue;
f = true;
for (int k=1; i+k<matrix.length && j+k<matrix[i].length; k++) {
for (int m=0; m<k; m++) {
f &= (matrix[i+m][j+k]=='1');
if (!f) break; f &= (matrix[i+k][j+m]=='1');
if (!f) break;
}
if (!f) break;
f &= (matrix[i+k][j+k]=='1');
if (!f) break; if (list.size() < k) {
list.add(new int[]{k+1, 1});
} else {
list.get(k-1)[1]++;
}
}
}
} for (int[] m : list) {
System.out.printf("matrix:%dx%d, count:%d\n", m[0], m[0], m[1]);
}
}
}
先把整理的一部分贴出来来看一个全部元素都是1的6X6的矩阵
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
那么元素都是1的子矩阵的情况有
1
1X1:(6-1+1)^2=361 1
1 1
2X2:(6-2+1)^2=251 1 1
1 1 1
1 1 1
3X3:(6-3+1)^2=161 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
4X4:(6-4+1)^2=91 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
5X5:(6-5+1)^2=4
也就是说，元素全是1的n*n矩阵，k*k子矩阵的个数有 (n-k+1)^2接下来看看某个元素（只有1个元素）为0时，会造成多少个子矩阵不成立
先看一个特殊值 c= n/2 + n%2，n=6时，c=3，也就是中间位置
对于i行j列元素为0(先不看j列)，当i>=k && i<=n-k，最多影响 min(c,k) 个 k*k矩阵，当i从中间往外扩展，依次减少1个，同样的，j列也如此，所以总共影响的的个数为 i行影响的个数*j列影响的个数
i行j列影响的个数可以总结如下：1X1: [1, 1, 1, 1, 1, 1] 不管i行j列位置如何，都只影响1个矩阵
2X2: [1, 2, 2, 2, 2, 1] 0行2列影响的个数有 p[i]*p[j]=1*2=2个 1行3列有 p[1]*p[3]=2*2=4个
3X3: [1, 2, 3, 3, 2, 1] 2行3列影响的个数有 p[2]*p[3]=3*3=9个 1行3列有 p[1]*p[3]=2*3=6个
4X4: [1, 2, 3, 3, 2, 1] 例子同上
5X5: [1, 2, 2, 2, 2, 1] 例子同上
6X6: [1, 1, 1, 1, 1, 1] 例子同上从表中，我们还发现，2X2和5X5的影响相同，3X3和4X4的影响相同，也就是从中间位置 c 往外扩展的情况是一样的再看多个元素同时为0的情况，此时会有重复的情况，目前还没找到重复的规律，以后有空再继续思考了，找到规律后再补充了。
算法在注释中