P1387 最大正方形

2018-06-17 22:35:24来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

在一个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
 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 }
AC
 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 }
四维30

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:c++ 端口扫描程序

下一篇:P1855 榨取kkksc03