0小秋的矩陣 - 藍橋云課

問題描述

給你一個 n 行 m 列只包含 0 和 1 的矩陣，求它的所有子矩陣中，是方陣而且恰好包含 k 個 0 的數量。

方陣是行數和列數相等的矩陣。

子矩陣是從一個矩陣當中選取某些行和某些列交叉位置所組成的新矩陣（保持行與列的相對順序），被稱為原矩陣的一個子矩陣。

輸入格式

第 1 行輸入 3 個整數 n, m, k，表示矩陣的行數，列數和所求子矩陣包含 0 的數量。

接下來 n 行，每行輸入 m 個整數，第 i 行表示給定矩陣的第 i 行。

輸出格式

輸出僅一行，包含 1 個整數，表示答案。

樣例輸入

3 4 2
0 1 1 0
1 0 0 1
0 1 0 0

樣例輸出

4

說明

共有 4 個階數為 2 的方陣符合條件，左上角的坐標分別為 (1,1), (1,2), (1,3), (2,1)。

評測數據規模

• 對于 20% 的評測數據，1 ≤ n × m ≤ 103。
• 對于 40% 的評測數據，1 ≤ n × m ≤ 103。
• 對于 100% 的評測數據，1 ≤ n × m ≤ 10?，0 ≤ k ≤ n × m。

運行限制

語言	最大運行時間	最大運行內存
C	1s	256M
C++	1s	256M
Python3	3s	256M
Java	2s	256M
PyPy3	3s	256M
Go	3s	256M

---

思路：

我們可以把0變成1，1變成0.這樣計算0的數量就變成計算1的數量。之后就是正常的二維前綴和，枚舉正方形。

有兩個點：

1.找出每一個正方形的（x1,y1),(x2,y2)

2.邊長的取值范圍
代碼如下：

#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1e3+10;
int n,m,k,ans;
int a[N][N];
int pre[N][N];
int main() 
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m >> k;for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= m ; j++)//0和1變換，然后求出子矩陣包含k個1的數量 {int temp;cin >> temp;if(temp == 1)a[i][j] = 0;else if(temp == 0) a[i][j] = 1; }}for(int i = 1 ; i <= n ; i++){for(int j = 1 ; j <= m ; j++){pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];}} int ans = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {int max_len = min(n - i + 1, m - j + 1);for (int l = 1; l <= max_len; l++)// 枚舉邊長 {int x2 = i + l - 1;int y2 = j + l - 1;int x1 = i;int y1 = j; int sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];if (sum == k) {ans++;}}}}cout << ans;return 0;
}