那美克星人的家爱博客

 /**
 * 
 * 时间限制(普通/Java):6000MS/20000MS 运行内存限制:65536KByte
 * 总提交:131 测试通过:32
 * 描述
 * 在一个0,1方阵中找出其中最大的全0子矩阵，所谓最大是指O的个数最多
 * 输入
 * 单组数据第一行为整数N，其中1<=N<=2000，为方阵的大小，紧接着N行每行均有N个0或1，相邻两数间严格用一个空格隔开
 * 输出
 * 输出仅一行包含一个整数表示要求的最大的全零子矩阵中零的个数
 * 样例输入
 * 5
 * 0 1 0 1 0
 * 0 0 0 0 0
 * 0 0 0 0 1
 * 1 0 0 0 0
 * 0 1 0 0 0
 * 样例输出
 * 9
 */

package graph;
/**
 * 
 * 时间限制(普通/Java):6000MS/20000MS 运行内存限制:65536KByte
 * 总提交:131 测试通过:32
 * 描述
 * 在一个0,1方阵中找出其中最大的全0子矩阵，所谓最大是指O的个数最多
 * 输入
 * 单组数据第一行为整数N，其中1<=N<=2000，为方阵的大小，紧接着N行每行均有N个0或1，相邻两数间严格用一个空格隔开
 * 输出
 * 输出仅一行包含一个整数表示要求的最大的全零子矩阵中零的个数
 * 样例输入
 * 5
 * 0 1 0 1 0
 * 0 0 0 0 0
 * 0 0 0 0 1
 * 1 0 0 0 0
 * 0 1 0 0 0
 * 样例输出
 * 9
 * 
 * @author Leon.Chen
 *
 */
public class AllZeroMatrix {
	/**
	 * 输入矩阵
	 */
	public int[][] matrix;
	/**
	 * 矩阵最大行
	 */
	public int maxRow;
	/**
	 * 矩阵最大列
	 */
	public int maxColumn;
	/**
	 * 被乘数
	 */
	public int multiplicand;
	/**
	 * 最大全零矩阵
	 */
	public int totalCount;

	/**
	 * 每个点向下，向右扩张矩形，取最大的矩形
	 * 
	 * @param row
	 * @param column
	 */
	public void spread(int row, int column) {
		int rowStart = row;
		int rowEnd = row;
		while (rowEnd < maxRow) {
			if (matrix[rowEnd][column] == 0) {
				rowEnd++;
			} else {
				break;
			}
		}
		this.multiplicand = 0;
		spreadMatrixRight(rowStart, rowEnd, column);
		int count = (rowEnd - rowStart) * multiplicand;
		if (totalCount < count) {
			totalCount = count;
		}
		int columnStart = column;
		int columnEnd = column;
		while (columnEnd < maxColumn) {
			if (matrix[row][columnEnd] == 0) {
				columnEnd++;
			} else {
				break;
			}
		}
		this.multiplicand = 0;
		spreadMatrixbelow(columnStart, columnEnd, row);
		count = (columnEnd - columnStart) * multiplicand;
		if (totalCount < count) {
			totalCount = count;
		}
	}

	/**
	 * 矩阵的向右扩张
	 * 
	 * @param start
	 * @param end
	 * @param column
	 */

	public void spreadMatrixRight(int start, int end, int column) {
		boolean flg = true;
		for (int i = start; i < end; i++) {
			if (matrix[i][column] == 1) {
				flg = false;
				break;
			}
		}
		if (flg) {
			multiplicand++;
			int nextColumn = column;
			nextColumn++;
			if (nextColumn < maxColumn) {
				spreadMatrixRight(start, end, nextColumn);
			}
		}
	}

	/**
	 * 矩阵的向下扩张
	 * 
	 * @param start
	 * @param end
	 * @param row
	 */
	public void spreadMatrixbelow(int start, int end, int row) {
		boolean flg = true;
		for (int i = start; i < end; i++) {
			if (matrix[row][i] == 1) {
				flg = false;
				break;
			}
		}
		if (flg) {
			multiplicand++;
			int nextRow = row;
			nextRow++;
			if (nextRow < maxRow) {
				spreadMatrixbelow(start, end, nextRow);
			}
		}
	}

	/**
	 * 得到最大全零矩阵的大小
	 * 
	 * @param printMatrix
	 */
	public void getAllZeroMatrix(int[][] printMatrix) {
		matrix = printMatrix;
		maxRow = matrix.length;
		maxColumn = matrix[0].length;
		for (int i = 0; i < maxRow; i++) {
			for (int j = 0; j < maxColumn; j++) {
				int count = (maxRow - i) * (maxColumn - j);
				if (count <= totalCount) {
					continue;
				}
				if (matrix[i][j] != 1) {
					spread(i, j);
				}
			}
		}
		System.out.println(totalCount);
	}
	
	public static void main(String[] args) {
		int[][] printMatrix = new int[][]{
				{0,1,0,1,0},
				{0,0,0,0,0},
				{0,0,0,0,1},
				{1,0,0,0,0},
				{0,1,0,0,0},
		};
		long start = System.currentTimeMillis();
		new AllZeroMatrix().getAllZeroMatrix(printMatrix);
		long end = System.currentTimeMillis();
		System.out.println((end-start)+"ms");
	}
}