题目描述
有一个方阵，其中每个单元(像素)非黑即白(非0即1)，请设计一个高效算法，找到四条边颜色相同的最大子方阵。
给定一个01方阵mat，同时给定方阵的边长n，请返回最大子方阵的边长。保证方阵变长小于等于100。
测试样例：
[[1,1,1],[1,0,1],[1,1,1]],3
返回：3
要看清题目，题目说的是四条边同一种颜色，不是四条边都是1。想法就是记录每个点右侧与下侧的连续0或1的个数，这样在给定一个左上角坐标与边长时，可以以O(1)的时间判断是否构成矩形。总的时候复杂度为O(N^3)。
class SubMatrix {
public:
struct cell {
int right, down;
cell() : right(), down(){}
};
int maxSubMatrix(vector<vector<int> > mat, int n) {
// write code here
vector<vector<cell>> mmat1(n, vector<cell>(n));
vector<vector<cell>> mmat2(n, vector<cell>(n));
int tmp1, tmp2, res;
for (int i = n - ; i >= ; --i) {
for (int j = n - ; j >= ; --j) {
if (j == n - ) tmp1 = tmp2 = ;
else tmp1 = mmat1[i][j+].right, tmp2 = mmat2[i][j+].right;
if (mat[i][j] == ) mmat1[i][j].right = tmp1 + ;
else mmat2[i][j].right = tmp2 + ;
if (i == n - ) tmp1 = tmp2 = ;
else tmp1 = mmat1[i+][j].down, tmp2 = mmat2[i+][j].down;
if (mat[i][j] == ) mmat1[i][j].down = tmp1 + ;
else mmat2[i][j].down = tmp2 + ;
}
}
for (int i = n; i > ; --i) {
if (isOK(mmat1, n, i) || isOK(mmat2, n, i)) return i;
}
return ;
}
bool isOK(vector<vector<cell>> &mat, int n, int size) {
for (int i = ; i <= n - size; ++i) {
for (int j = ; j <= n - size; ++j) {
if (isSquare(mat, i, j, size)) return true;
}
}
return false;
}
bool isSquare(vector<vector<cell>> &mat, int x, int y, int size) {
cell &lefttop = mat[x][y], &leftdown = mat[x+size-][y], &righttop = mat[x][y+size-];
if (lefttop.right < size) return false;
if (lefttop.down < size) return false;
if (leftdown.right < size) return false;
if (righttop.down < size) return false;
return true;
}
};