自己用电脑网站建设,河北三河建设局网站,常州高端网站制作公司排名,网页设计介绍说明题目描述
在一个nm 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形#xff0c;输出边长。
输入格式
输入文件第一行为两个整数n,m(1≤n,m≤100)#xff0c;接下来 n 行#xff0c;每行 m 个数字#xff0c;用空格隔开#xff0c;0 或 1。
输出格式
一个整数…题目描述
在一个n×m 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形输出边长。
输入格式
输入文件第一行为两个整数n,m(1≤n,m≤100)接下来 n 行每行 m 个数字用空格隔开0 或 1。
输出格式
一个整数最大正方形的边长。
输入输出样例
输入 #1
4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1输出 #1
2代码
#includeiostream
#includealgorithm
using namespace std;
int a[102][102];
int main()
{int n,m;cinnm;for(int i1;in;i){//输入n行m列个包含0和1的数for(int j1;jm;j){cina[i][j];}}for(int i1;in;i){for(int j1;jm;j){if(a[i][j]1){//计算二维数组每一行的前缀和a[i][j]a[i][j-1]1;}else a[i][j]a[i][j-1];}} for(int i1;im;i){for(int j1;jn;j){//计算二维数组每一列的前缀和。a[j][i]a[j][i]a[j-1][i];}} int mm1;//统计最大的正方形的边长最小为1。for(int i1;in;i){for(int j1;jm;j){//定位到每一个元素该元素是正方形的最右下角的数字for(int k1;kmin(i,j);k){//定位到的元素的位置确定正方形的边长用min(i,j)表示。int ta[i][j]-a[i][j-k]-a[i-k][j]a[i-k][j-k];//通过最右下角的元素以及要求正方形的边长求得矩形的总和。if(tk*kmmk){//如果求得的总和等于边长的长度则是要求的正方形并且寻找最大的正方形边长。mmk;}
// coutt\n;}}} coutmm;
// for(int i1;in;i){
// for(int j1;jm;j){
// couta[i][j] ;
// }cout\n;
// } return 0;
}
