美团春招编程第一场第三题
题目
解答
- 思路-暴力解法
pair中存储从原点到包含当前元素的0,1数量，得到二维数组mat;
从头到尾遍历尺寸为i*i的矩形，计算完美矩形数量
#include <iostream>
#include <vector>
using namespace std;int main() {int n;cin >> n;vector<vector<pair<int, int>>> mat;vector<vector<int>> data;for (int i = 0; i < n; i++) {vector<pair<int, int>> dp(n);vector<int> tmp(n);if (i == 0) {for (int j = 0; j < n; j++) {int in;cin >> in;tmp[j] = in;if (j == 0) {dp[j] = {in == 1 ? 1 : 0, in == 0 ? 1 : 0};} else {dp[j] = {dp[j - 1].first + (in == 1 ? 1 : 0), dp[j - 1].second + (in == 0 ? 1 : 0)};}}} else {for (int j = 0; j < n; j++) {int in;cin >> in;tmp[j] = in;if (j == 0) dp[j] = {in == 1 ? 1 : 0, in == 0 ? 1 : 0};else dp[j] = {dp[j - 1].first + (in == 1 ? 1 : 0), dp[j - 1].second + (in == 0 ? 1 : 0)};}for (int j = 0; j < n; j++) {dp[j].first += mat[i - 1][j].first;dp[j].second += mat[i - 1][j].second;}}data.emplace_back(tmp);mat.emplace_back(dp);}for (int i = 1; i <= n; i++) {if (i == 1) {cout << 0 << endl;continue;} else {int ret = 0;for (int k = 0; k <= n - i; k++) {for (int p = 0; p <= n - i; p++) {if(k == 0 && p == 0) {if(mat[k+i-1][p+i-1].first == mat[k+i-1][p+i-1].second) ++ret;}else if(p == 0){if(mat[k+i-1][p+i-1].first - mat[k-1][p+i-1].first == mat[k+i-1][p+i-1].second - mat[k-1][p+i-1].second ){ret++; }}else if( k == 0){if(mat[k+i-1][p+i-1].first - mat[k+i-1][p-1].first == mat[k+i-1][p+i-1].second - mat[k+i-1][p-1].second ){ret++; }}else {if(mat[k+i-1][p+i-1].first - mat[k+i-1][p-1].first - mat[k-1][p+i-1].first + mat[k-1][p-1].first == mat[k+i-1][p+i-1].second - mat[k+i-1][p-1].second - mat[k-1][p+i-1].second + mat[k-1][p-1].second){ret++; }}}}cout << ret << endl;}}return 0;
}
