描述

    童年的我们，充满了新奇的想法。这天，小朋友们用彩虹画笔在云霞上绘制了世界上最美丽的图画。那描绘的是一条大河波浪宽，风吹稻花香两岸的情景。欣赏着自己的作品，小朋友们别提多开心了。这时，Q小朋友对C小朋友说：你看，河面上那一弯弯船儿，多漂亮啊！可是，这么多船儿，哪一只最大呢？

    C小朋友最在意他在Q小朋友心目中的形象了，当然想完美地回答这个问题了。你能帮帮他么？

    船的定义为：中间是长宽比例为1：2的矩形，两头是两个等腰直角三角形的等腰梯形。注意：必须保证在船所占据的矩形中除了船的图形外都是空白，见样例。

输入格式

第一行两个数n、m,表示云霞的长宽

以下n行，每行m个字母，表示图案。0表示空白，1表示有图案。

输出格式

第一行两个数x、y，表示找到的最大的船的左上角的坐标。

以下若干行若干列，为找到的图形。

注意：在（9，22）点起始的图形是合法的最小的船。如果不存在船，输出：'Oh,my god!'。如果多解，输出最靠上的一个。如果仍多解，输出最靠左的一个。

测试样例1

输入

10 30 

000000000000000000000000000000 

000000000001111111111111100000 

000000000000111111111111000000 

000000000000011111111110100000 

000000000000001111111100000000 

000000000000000000000000000000 

001111111111000000000000000000 

000111111110000000000000000000 

000011111100000000000111111000 

000000000000000000000011110000

输出

7 3 

1111111111 

0111111110 

0011111100

备注

【限制】

20％的数据，n<=10,m<=10

40％的数据，n<=100,m<=100

60％的数据，n<=500,m<=500

100％的数据，n<=2000,m<=2000

【样例解释】

尽管以(2，12)起始有个更大的“船”，但是由于（4，25）这个该“船”占据的矩形中的点不是空白，该船不合法。所以答案是左上角坐标为（7，3）的船。由SRC原创

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=2010;int n,m,a[N][N],b[N][N],c[N][N],d[N][N],e[N][N],f[N][N],g[N][N],h[N][N],ans,sy,sx;char map[N][N];void read(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%s",map[i]+1);}void go(){//以i,j为左下角的1三角形的大小 checkedfor(int j=1;j<=m;j++)if(map[1][j]=='1') a[1][j]=1;for(int i=2;i<=n;i++)    for(int j=1;j<=m;j++)        if(map[i][j]=='1') a[i][j]=min(a[i-1][j],a[i-1][j+1])+1;//以i,j为左下角的0三角形的大小 checkedfor(int j=1;j<=m;j++)    if(map[1][j]=='0') b[1][j]=1;for(int i=2;i<=n;i++)    for(int j=m;j>=1;j--)        if(map[i][j]=='0') b[i][j]=min(b[i-1][j+1],b[i][j+1])+1;//以i,j为右下角的1三角形的大小 checkedfor(int j=1;j<=m;j++)     if(map[1][j]=='1') c[1][j]=1; for(int i=2;i<=n;i++)    for(int j=1;j<=m;j++)    if(map[i][j]=='1') c[i][j]=min(c[i-1][j-1],c[i-1][j])+1; //以i,j为右下角的0三角形的大小 checkedfor(int j=1;j<=m;j++)     if(map[1][j]=='0') d[1][j]=1;for(int i=2;i<=n;i++)    for(int j=1;j<=m;j++)        if(map[i][j]=='0') d[i][j]=min(d[i-1][j-1],d[i][j-1])+1;//以i,j为右下角的1正方形的大小 checkedfor(int j=1;j<=m;j++)     if(map[1][j]=='1') e[1][j]=1; for(int i=2;i<=n;i++)    for(int j=1;j<=m;j++)        if(map[i][j]=='1') e[i][j]=min(min(e[i-1][j],e[i][j-1]),e[i-1][j-1])+1;        //以i,j为左下角的1正方形的大小 checkedfor(int j=1;j<=m;j++)     if(map[1][j]=='1') f[1][j]=1; for(int i=2;i<=n;i++)    for(int j=m;j>=1;j--)        if(map[i][j]=='1') f[i][j]=min(min(f[i-1][j],f[i][j+1]),f[i-1][j+1])+1;        //checkedfor(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)    {if(b[i][j+1]!=0) b[i][j+1]++;        g[i][j]=min(a[i][j],b[i][j+1]);        if(d[i][j-1]!=0) d[i][j-1]++;        h[i][j]=min(c[i][j],d[i][j-1]);}//c为以i,j为右下角的直角梯形，d为以i,j为左下角的直角梯形    memset(c,0,sizeof c);memset(d,0,sizeof d);for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)    {        a[i][j]=min(g[i][j],e[i][j]);        b[i][j]=min(h[i][j],f[i][j]);        if(a[i][j]!=0) c[i][j-a[i][j]+1]=a[i][j];        if(b[i][j]!=0) d[i][j+b[i][j]-1]=b[i][j];}for(int i=1;i<=n;i++)    for(int j=1;j
          
           ans){ans=sk;sx=i-ans+1;sy=j-ans-ans+2;}}if(ans!=0){printf("%d %d\n",sx,sy);for(int i=sx;i<=sx+ans-1;i++){    for(int j=sy;j<=sy+4*ans-3;j++)        printf("%c",map[i][j]);    printf("\n");}}else printf("Oh,my god!\n");}int main(){read();go();system("pause");return 0;}