枚举

枚举
1.特点：一一列举
2.要点：不重复不遗漏
但是不充复不遗漏只能保证把题目求出来，但可能会被时间卡住
3.优化：把多余的操作去掉，减少枚举次数
①选择合适的枚举对象
②选择合适的枚举方向——方便排除非法和不是最优的情况
③选择合适的数据维护方法——方便转化问题

最大正方形 --题目和图片来自https://blog.csdn.net/qq_46009744/article/details/106142716
题目描述：
在一个N*N(N<=100)矩阵中求一个最大的正方形使得该正方形的四个顶点都是有字符“#”构成。

暴力枚举四个点的话，是个4重循环，n^4 , 如果矩阵中每个点都是#, 就是 1e16, 肯定超时。

为了优化枚举，可以优化枚举对象，思考几个点可以确定一个正方形？
–正方形可以由两个点唯一确定
–长方形可以由三个点唯一确定

（B点和D点都可以通过A,B的坐标所表示）

我们枚举A,B这两个点的坐标，都是#，然后直接算出B,D的坐标，如果B,D的点都是#,则是正方形，如果不是#,则说明A,C这对对角线不行。

代码的实现参考了：https://blog.csdn.net/qq_46009744/article/details/106142716

pair存点，set来找点，枚举 的想法和步骤都很值得学习。值得注意的通过A,C点找到B,D点的位置是需要讨论的。

#include<bits/stdc++.h>
using namespace std;
const int N=110;
char mp[110][110];
int x[N*N];
int y[N*N];
typedef pair<int,int> Point;
set<Point > pset;
int main()
{
   
	int n,k=0;
	while(cin >> n) {
   
		for(int i=0; i<n; i++) {
   
			scanf("%s",mp[i]);
			for(int j=0; j<n; j++) {
   
				if(mp[i][j]=='#') {
   
					x[k]=i+1;
					y[k]=j+1;
					pset.insert(make_pair(x[k],y[k]));
					k++;
				}
			}
		}
		int ans=0;
		for(int i=0; i<n; i++) 
			for(int j=i+1; j<n; j++) {
   
				int mx=(x[i]+x[j])/2;	int dx=abs(x[i]-x[j]);
				int my=(y[i]+y[j])/2;	int dy=abs(y[i]-y[j]);
				int sg=((x[i]-x[j])*(y[i]-y[j])<0 ? -1 : 1);
				if(pset.count(make_pair(mx+dy*sg,my-dx))!=0 && pset.count(make_pair(mx-dy*sg,my+dx))!=0) {
   
					int dis=(x[i]-x[j])*(x[i]-x[j])-(y[i]-y[j])*(y[i]-y[j]);
					dis/=2;
					ans=max(dis,ans);	 
				}
			}
		cout<<sqrt(ans)<<endl;
	}
}