每日一题7.13

发布于:2025-07-17 ⋅ 阅读:(16) ⋅ 点赞:(0)

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;
}

 

 


网站公告

今日签到

点亮在社区的每一天
去签到