上海计算机学会2022年3月月赛C++乙组T1最大空方阵
发布时间
阅读量：
阅读量
最大空方阵
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 n×n 个字符，每个字符只能是 0 或 1，请从中找到一个完全由 0 构成的正方形区域，且正方形的边长达到最大。
输入格式
第一行：单个整数表示 n；
接下来有 n×n 个字符，表示给定的字符方阵，只由 0 及 1 构成。
输出格式
单个整数：表示只由 0 构成的最大方阵边长。
数据范围
- 对于 30% 的数据， 1≤n≤50；
- 对于 60% 的数据， 1≤n≤500；
- 对于 1000% 的数据， 1≤n≤3000。
样例数据
输入:
5
11111
10000
10000
00000
11111
输出:
3
输入:
2
11
11
输出:
0
解析：
动态规划，详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
string a[3005];
int dp[3005][3005];//dp[i][j]表示以ij位置为右下角的最大空方阵
int ans = 0;
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
//默认为0
if(a[i][j - 1] == '0') {//如果当前位置为0
//取左边，上边，左上三个位置的最小值加1
dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
}
ans = max(ans, dp[i][j]);//取最大值为答案
}
}
cout << ans;
return 0;
}
全部评论 (0)
还没有任何评论哟~