P1387 最大正方形

題目描述

在一個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
吐槽：(⊙o⊙)…，洛谷的雙倍經驗真多。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ans,map[1100][1100],f[1100][1100];
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&map[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(!map[i][j])    continue;f[i][j]=min(f[i-1][j],min(f[i-1][j-1],f[i][j-1]))+1;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans=max(ans,f[i][j]);cout<<ans;
}

?

?

轉載于:https://www.cnblogs.com/cangT-Tlan/p/7435964.html

總結

以上是生活随笔為你收集整理的洛谷 P1387 最大正方形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。