首页 > 代码库 > 《Cracking the Coding Interview》——第18章:难题——题目11
《Cracking the Coding Interview》——第18章:难题——题目11
2014-04-29 04:30
题目:给定一个由‘0’或者‘1’构成的二维数组,找出一个四条边全部由‘1’构成的正方形(矩形中间可以有‘0’),使得矩形面积最大。
解法:用动态规划思想,记录二维数组每个元素向上下左右四个方向各有多少个连续的‘1’,然后用O(n^3)时间计算出满足条件的最大正方形。时间复杂度O(n^3),空间复杂度O(n^2)。
代码:
1 // 18.11 Given an NxN matrix of 0s and 1s, find out a subsquare whose all four borders are all 1s. If multiple satisfies the condition, any one is OK. 2 // I‘ll return the size and the left top corner of the subsquare. 3 #include <iostream> 4 #include <vector> 5 using namespace std; 6 7 class Solution { 8 public: 9 void maxSubsquare(const vector<vector<int> > &matrix, int &max_left, int &max_top, int &max_size) { 10 int n = matrix.size(); 11 12 max_left = max_top = max_size = -1; 13 14 if (n <= 1) { 15 return; 16 } 17 18 vector<vector<int> > top (n, vector<int>(n)); 19 vector<vector<int> > bottom(n, vector<int>(n)); 20 vector<vector<int> > left (n, vector<int>(n)); 21 vector<vector<int> > right (n, vector<int>(n)); 22 23 int i, j; 24 int tmp; 25 26 // use DP to preprocess the data, count how many consecutive 1s are there to the left, right, top, bottom of matrix[i][j]. 27 for (i = 0; i <= n - 1; ++i) { 28 tmp = 0; 29 for (j = 0; j <= n - 1; ++j) { 30 left[i][j] = matrix[i][j] ? (++tmp) : (tmp = 0); 31 } 32 } 33 for (j = 0; j <= n - 1; ++j) { 34 tmp = 0; 35 for (i = 0; i <= n - 1; ++i) { 36 top[i][j] = matrix[i][j] ? (++tmp) : (tmp = 0); 37 } 38 } 39 for (i = n - 1; i >= 0; --i) { 40 tmp = 0; 41 for (j = n - 1; j >= 0; --j) { 42 right[i][j] = matrix[i][j] ? (++tmp) : (tmp = 0); 43 } 44 } 45 for (j = n - 1; j >= 0; --j) { 46 tmp = 0; 47 for (i = n - 1; i >= 0; --i) { 48 bottom[i][j] = matrix[i][j] ? (++tmp) : (tmp = 0); 49 } 50 } 51 52 int len; 53 // O(n ^ 3) solution with O(n ^ 2) space usage. 54 for (i = 0; i < n; ++i) { 55 for (j = 0; j < n; ++j) { 56 for (len = 2; len + i <= n && len + j <= n; ++len) { 57 if (right[i][j] < len || bottom[i][j] < len) { 58 continue; 59 } 60 if (left[i][j + len - 1] < len || bottom[i][j + len - 1] < len) { 61 continue; 62 } 63 if (right[i + len - 1][j] < len || top[i + len - 1][j] < len) { 64 continue; 65 } 66 if (left[i + len - 1][j + len - 1] < len || top[i + len - 1][j + len - 1] < len) { 67 continue; 68 } 69 // all four borders are ‘1‘s. 70 if (len > max_size) { 71 max_top = i; 72 max_left = j; 73 max_size = len; 74 } 75 } 76 } 77 } 78 79 // clear up data 80 for (i = 0; i < n; ++i) { 81 left[i].clear(); 82 right[i].clear(); 83 top[i].clear(); 84 bottom[i].clear(); 85 } 86 left.clear(); 87 right.clear(); 88 top.clear(); 89 bottom.clear(); 90 }; 91 }; 92 93 int main() 94 { 95 int n; 96 int i, j; 97 vector<vector<int> > matrix; 98 Solution sol; 99 int max_left, max_top, max_size; 100 101 while (cin >> n && n > 0) { 102 matrix.resize(n); 103 for (i = 0; i < n; ++i) { 104 matrix[i].resize(n); 105 } 106 107 for (i = 0; i < n; ++i) { 108 for (j = 0; j < n; ++j) { 109 cin >> matrix[i][j]; 110 } 111 } 112 113 sol.maxSubsquare(matrix, max_left, max_top, max_size); 114 if (max_size > 0) { 115 cout << max_top << ‘ ‘ << max_left << endl; 116 cout << max_top << ‘ ‘ << max_left + max_size - 1 << endl; 117 cout << max_top + max_size - 1 << ‘ ‘ << max_left << endl; 118 cout << max_top + max_size - 1 << ‘ ‘ << max_left + max_size - 1 << endl; 119 } else { 120 cout << "No subsquare found." << endl; 121 } 122 123 for (i = 0; i < n; ++i) { 124 matrix[i].clear(); 125 } 126 matrix.clear(); 127 } 128 129 return 0; 130 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。