P1387 最大正方形
2018-06-17 22:35:24来源:未知 阅读 ()
题目描述
在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形,输出边长。
输入输出格式
输入格式:输入文件第一行为两个整数n,m(1<=n,m<=100),接下来n行,每行m个数字,用空格隔开,0或1.
输出格式:一个整数,最大正方形的边长
输入输出样例
4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1
2
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 int map[101][101]; 7 int dp[101][101]; 8 int main() 9 { 10 int n,m; 11 scanf("%d%d",&n,&m); 12 for(int i=1;i<=n;i++) 13 for(int j=1;j<=m;j++) 14 { 15 scanf("%d",&map[i][j]); 16 if(map[i][j]) 17 dp[i][j]=1; 18 } 19 for(int i=1;i<=n;i++) 20 for(int j=1;j<=m;j++) 21 { 22 if(map[i][j]) 23 { 24 dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1; 25 } 26 } 27 int ans=-1; 28 for(int i=1;i<=n;i++) 29 { 30 for(int j=1;j<=m;j++) 31 { 32 ans=max(ans,dp[i][j]); 33 } 34 } 35 printf("%d",ans); 36 return 0; 37 }
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 int map[101][101]; 7 int dp[80][80][80][80]; 8 int main() 9 { 10 int n,m; 11 scanf("%d%d",&n,&m); 12 for(int i=1;i<=n;i++) 13 for(int j=1;j<=m;j++) 14 { 15 scanf("%d",&map[i][j]); 16 if(map[i][j]) 17 dp[i][j][i][j]=1; 18 } 19 20 for(int i=1;i<=n;i++) 21 { 22 for(int j=1;j<=m;j++) 23 { 24 if(map[i][j]) 25 { 26 for(int k=i;k<=n;k++) 27 { 28 for(int l=j;l<=m;l++) 29 { 30 /*if(k-1==0) 31 dp[i][j][k][l]=dp[i][j][k][l]||(dp[i][j][k][l-1]&&map[k][l]); 32 else if(l-1==0) 33 dp[i][j][k][l]=dp[i][j][k][l]||(dp[i][j][k-1][l]&&map[k][l]); 34 else*/ 35 dp[i][j][k][l]=dp[i][j][k][l]||((dp[i][j][k-1][l]||dp[i][j][k][l-1])&&map[k][l]); 36 } 37 } 38 } 39 40 } 41 } 42 for(int i=1;i<=n;i++) 43 { 44 for(int j=1;j<=m;j++) 45 { 46 if(map[i][j]) 47 { 48 for(int k=i;k<=n;k++) 49 { 50 for(int l=j;l<=m;l++) 51 { 52 /*if(k-1==0) 53 dp[i][j][k][l]=dp[i][j][k][l]||(dp[i][j][k][l-1]&&map[k][l]); 54 else if(l-1==0) 55 dp[i][j][k][l]=dp[i][j][k][l]||(dp[i][j][k-1][l]&&map[k][l]); 56 else*/ 57 if(dp[i][j][k-1][l-1]&&dp[i][j][k-1][l]&&dp[i][j][k][l-1]&&map[k][l]==1) 58 dp[i][j][k][l]=max(dp[i][j][k][l],dp[i][j][k-1][l-1]+1); 59 } 60 } 61 } 62 63 } 64 } 65 int ans=-1; 66 for(int i=1;i<=n;i++) 67 { 68 for(int j=1;j<=m;j++) 69 { 70 for(int k=1;k<=n;k++) 71 { 72 for(int l=1;l<=m;l++) 73 { 74 ans=max(ans,dp[i][j][k][l]); 75 } 76 } 77 } 78 } 79 printf("%d",ans); 80 return 0; 81 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:c++ 端口扫描程序
下一篇:P1855 榨取kkksc03
- 动态规划:最大子串和 2020-01-30
- 最小割最大流定理&残量网络的性质 2019-12-17
- 剑指offer64:滑动窗口的最大值 2019-08-31
- Qt无边框窗体-最大化时支持拖拽还原 2019-08-27
- 【学习笔记】RMQ-Range Minimum/Maximum Query (区间最小/ 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash