题解 | 最大正方形

/*这道题需要懂得这样一点，就是正方形已知三点就可以通过横纵坐标差值求出第四点
	因此我们对于每个为井号的点，从这个点出发开始往右下进行遍历，
	通过手动构造的点的横纵坐标差值，构造出剩余两个点的坐标，
	注意检查是否越界，然后看构造出的点是不是井号就行了
	实时更新最大值与最大值对应的四个点坐标
*/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

void solve()
{
    int n;cin>>n;
    vector<string>v;
    for (int i = 0;i < n;i++)
    {
        string s;cin>>s;
        v.push_back(s);
    }

    // 由于井号比较少，并且最大的正方形就是本身，所以我们可以直接开始遍历
    vector<vector<int>>res(4,vector<int>(2));
    int m_s = 0;
    auto check = [&](int i,int j){
        // 只要dx+dy相等就都可以是正方形
        // 检查其中3个就行了
        for (int k = i;k < 100;k ++)
        {
            if (k > n-1)    break;
            for (int l = j;l < 100;l++)
            {
                if (v[k][l] != '#') continue;
                if (l > n-1)  break;

                // 表示四个角的坐标
                
                int dx = k-i,dy = l-j;
                // 先检查是否越界，在检查是否为井号
                int p3x = k+dy,p3y = l-dx;
                int p4x = p3x-dx,p4y = p3y-dy;
                if (p3x > n-1||p3y < 0||p3y >n-1||p3x < 0) continue;
                if (p4x < 0||p4y > n-1||p4x >n-1||p4y <0)continue;
                if (v[p3x][p3y] == '#'&&v[p4x][p4y] == '#')
                {
                    if (dx*dx+ dy*dy > m_s)
                    {
                        res[0] = {i+1,1+j};
                        res[1] = {k+1,l+1};
                        res[2] = {p3x+1,1+p3y};
                        res[3] = {p4x+1,p4y+1};
                        m_s = dx*dx+dy*dy;
                    }
                } 
            }
        }
    };

    for (int i = 0;i < n;i++)
    {
        for (int j = 0;j < n;j++)
        {
            if (v[i][j] == '#')
                check(i,j);
        }
    }

    for(auto vv:res)
    {
        for (int m:vv)
        {
            cout<<m<<' ';
        }
        cout<<'\n';
    }
}
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;
}

// 今晚可以10公里了吧要不现在就去怎么样，然后晚sang睡个好觉