1005-枚举 · 例2-最大正方形_2021秋季算法入门班第一章习题：模拟、枚举、贪心
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
题目描述
对于给定的 n×nn×n 的、仅由 "*""*" 和
构成的矩阵中，找到一个边长最大的正方形，使得正方形的四个顶点均为字符
。
输入描述:
第一行输入一个整数 n(1≦n≦100)n(1≦n≦100) 代表矩阵大小。 此后 nn 行，每行输入一个长度为 nn 的、仅由 "*""*" 和
构成的字符串代表矩阵。
输出描述:
输出四行，每行两个整数，代表正方形四个顶点所在的单元格。我们使用 (i,j)(i,j) 表示网格中从上往下数第 ii 行和从左往右数第 jj 列的单元格，从 11 开始编号。 如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
示例1
输入
复制
8 *####*** *####*** *####*** *####*** *#####** ******** ***#***# ******** *****#**
输出
复制
1 2 4 2 1 5 4 5
说明
该样例如图所示。特别的，橙色正方形的边长为 2222 ，比粉色正方形小。
示例2
输入
复制
8 *#*#**** *****#** ******#* *#****** #******* ****#*** ******** ********
输出
复制
1 2 2 6 5 1 6 5
说明
该样例如图所示。橙色正方形的边长为 1313 ，粉色正方形的边长为 1717 。
暴力找两个点然后找正方形就好了
#include<bits/stdc++.h>
using namespace std;
char s[101][101];
int len = 0;
int o[8] = { 0 };
void fun(int j, int t, char s[101][101], int n) {
for (int q = j; q < n; q++) {
for (int p = t; p < n; p++) {
int a = j - q;
int b = t - p;
int len1 = a * a + b * b;
if (s[q][p] == '#' && a * a + b * b != 0 && j + b >= 0 && t - a >= 0 && j + b < n && t - a < n && s[j + b][t - a] == '#') {
if (j + b - a >= 0 && j + b - a < n && t - a - b >= 0 && t - a - b<n && s[j + b - a][t - a - b] == '#' && len1>len) {
len = len1;
o[0] = j + 1;
o[1] = t + 1;
o[2] = q + 1;
o[3] = p + 1;
o[4] = j + b + 1;
o[5] = t - a + 1;
o[6] = j + b - a + 1;
o[7] = t - a - b + 1;
}
}
}
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
scanf("%s", s[i]);
}
for (int j = 0; j < n; j++) {
for (int t = 0; t < n; t++) {
if (s[j][t] == '#') {
fun(j, t, s, n);
}
}
}
for (int g = 0; g < 8; g += 2) {
printf("%d %d\n", o[g], o[g + 1]);
}
return 0;
}