题目：链接

题意

给定一个字符矩阵，找到矩阵中的最大正方形。

思路

关键在于如何确定一个正方形。枚举正方形的四个顶点，有8层for循环，显然不可取。所以根据正方形的特点，只需要枚举正方形的对角线的两个顶点，只需要4层for循环。确定好正方形以后，就是寻找最大的正方形，根据几何知识，边长（对角线）越长，正方形越大，所以只需比较每次找到的正方形的边长（对角线）即可。

心得

读取一个整数及矩阵的时候，要统一用cin或者scanf，不能一个cin一个scanf，会出错。

在枚举的过程中，枚举一个顶点就判断一下是否符合要求，再进入下一步，会减少不必要的枚举次数。

如何通过两个顶点的坐标计算出另外两个顶点的坐标，算法入门课中讲的是找到对角线上的两个顶点，但是寻找相邻两个顶点再去计算另外两个顶点会简单些，避免了小数。计算得到的新顶点还要判断一下是否再原来的字符矩阵中，计算方式如下：

x3=x1+y2-y1;
y3=y1-(x2-x1);
x4=x2+y2-y1;
y4=y2-(x2-x1);

代码

using namespace std;

int n;
char ch[110][110];
int ans[4][2];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>ch[i][j];
    int x1,y1,x2,y2,x3,y3,x4,y4;
    double len,maxx=0;
    for(x1=1;x1<=n;x1++)
        for(y1=1;y1<=n;y1++)
            if(ch[x1][y1]=='#')
                for(x2=1;x2<=n;x2++)
                    for(y2=1;y2<=n;y2++)
                        if(ch[x2][y2]=='#')
                        {
                            x3=x1+y2-y1;
                            y3=y1-(x2-x1);
                            x4=x2+y2-y1;
                            y4=y2-(x2-x1);
                            if(x3>=1&&x3<=n&&x4>=1&&x4<=n&&y3>=1&&y3<=n&&y4>=1&&y4<=n)
                                if(ch[x3][y3]=='#'&&ch[x4][y4]=='#')
                                {
                                    len=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
                                    if(len>maxx)
                                    {
                                        maxx=len;
                                        ans[0][0]=x1;
                                        ans[0][1]=y1;
                                        ans[1][0]=x2;
                                        ans[1][1]=y2;
                                        ans[2][0]=x3;
                                        ans[2][1]=y3;
                                        ans[3][0]=x4;
                                        ans[3][1]=y4;
                                    }
                                }
                        }
    
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<2;j++)
            cout<<ans[i][j]<<' ';
        cout<<endl;
    }    
    return 0;
}