题目
原文：
Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
译文：
有一个正方形矩阵，里面的每一个小格子要么被涂上黑色要么被涂上白色。 设计算法，找到四条边都是黑色格子的最大子正方形。
解答
暴力法，从左到右，从上到下遍历格子，将它作为子正方形左上角的点。 固定了子正方形左上角的点，我们只需要知道边长，就能把子正方形确定下来。 我们按边长从大到小开始，去检查每一个子正方形的四条边是否都为黑色格子。 如果是，则记下当前最大的边长值。将子正方形左上角的点移动到下一行(即向下移动一格)， 进入下一轮循环。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_N = 100;
int matrix[MAX_N][MAX_N];
struct SubSquare{
int row, col, size;
};
inline int max(int a, int b){
return a > b ? a : b;
}
bool IsSquare(int row, int col, int size){
for(int i=0; i<size; ++i){
if(matrix[row][col+i] == 1)// 1代表白色，0代表黑色
return false;
if(matrix[row+size-1][col+i] == 1)
return false;
if(matrix[row+i][col] == 1)
return false;
if(matrix[row+i][col+size-1] == 1)
return false;
}
return true;
}
SubSquare FindSubSquare(int n){
int max_size = 0; //最大边长
int col = 0;
SubSquare sq;
while(n-col > max_size){
for(int row=0; row<n; ++row){
int size = n - max(row, col);
while(size > max_size){
if(IsSquare(row, col, size)){
max_size = size;
sq.row = row;
sq.col = col;
sq.size = size;
break;
}
--size;
}
}
++col;
}
return sq;
}
int main(){
freopen("20.11.in", "r", stdin);
int n;
cin>>n;
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
cin>>matrix[i][j];
SubSquare sq = FindSubSquare(n);
cout<<"top: "<<sq.row<<endl;
cout<<"bottom: "<<sq.row+sq.size-1<<endl;
cout<<"left: "<<sq.col<<endl;
cout<<"right: "<<sq.col+sq.size-1<<endl;
fclose(stdin);
return 0;
}
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/03/07/20.11/
