我要招人

去企业版

首页 > 试题广场 >

最大正方形

[编程题]最大正方形

热度指数：214 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的 $n \times n$ 的、仅由 $\texttt{$ 和 $\texttt{$ 构成的矩阵中，找到一个边长最大的正方形，使得正方形的四个顶点均为字符 $\texttt{$ 。

输入描述:

第一行输入一个整数  代表矩阵大小。
此后  行，每行输入一个长度为  的、仅由  和  构成的字符串代表矩阵。保证输入数据中至少存在一个满足条件的正方形。

输出描述:

输出四行，每行两个整数，代表正方形四个顶点所在的单元格。我们使用  表示网格中从上往下数第  行和从左往右数第  列的单元格，从  开始编号。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

8
*####***
*####***
*####***
*#####**
********
***#***#
********
*****#**

输出

说明

该样例如图所示。特别的，橙色正方形的边长为  ，比粉色正方形小。

示例2

输入

8
*#*#****
*****#**
******#*
*#******
#*******
****#***
********
********

输出

说明

该样例如图所示。橙色正方形的边长为  ，粉色正方形的边长为  。

算法知识视频讲解

C++

有趣的大米

#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> Point; typedef vector<Point> Points; // 检查点是否为'#'（直接查矩阵，比查坐标列表更快） bool isHash(const vector<string>& map, int x, int y) { return (x >= 1 && x < map.size() && y >= 1 && y <= map[x].size() && map[x][y-1] == '#'); } // 计算两点距离的平方（避免浮点数） int distSq(const Point& a, const Point& b) { int dx = a.first - b.first; int dy = a.second - b.second; return dx*dx + dy*dy; } // 验证四个点是否构成正方形 bool isSquare(const Point& a, const Point& b, const Point& c, const Point& d) { int d1 = distSq(a, b); // 边1 int d2 = distSq(a, c); // 边2 int d3 = distSq(a, d); // 边3 int d4 = distSq(b, c); // 边4 int d5 = distSq(b, d); // 对角线1 int d6 = distSq(c, d); // 边6 // 正方形条件：4条边相等，2条对角线相等且为边长的√2倍（平方为2倍） vector<int> dists = {d1, d2, d3, d4, d5, d6}; sort(dists.begin(), dists.end()); // 前4个是边长平方，后2个是对角线平方（对角线平方=2*边长平方） return (dists[0] > 0) && // 边长不为0 (dists[0] == dists[1] && dists[1] == dists[2] && dists[2] == dists[3]) && // 4边相等 (dists[4] == dists[5]) && // 对角线相等 (dists[4] == 2 * dists[0]); // 对角线平方=2*边长平方 } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<string> map(n + 1); // map[1..n] Points allpots; // 收集所有'#'的坐标 for (int i = 1; i <= n; ++i) { cin >> map[i]; for (int j = 1; j <= n; ++j) { if (map[i][j-1] == '#') { allpots.emplace_back(i, j); } } } int maxSideSq = 0; Points bestSquare(4); // 1. 先检查轴对齐正方形（确保顶点都是'#'） for (int d = n - 1; d >= 1; --d) { // d是边长 for (int x = 1; x + d <= n; ++x) { for (int y = 1; y + d <= n; ++y) { // 四个顶点坐标 Point a(x, y); Point b(x + d, y); Point c(x, y + d); Point d4(x + d, y + d); // 验证四个顶点都是'#'且构成正方形 if (isHash(map, a.first, a.second) && isHash(map, b.first, b.second) && isHash(map, c.first, c.second) && isHash(map, d4.first, d4.second) && isSquare(a, b, c, d4)) { int sideSq = d * d; // 轴对齐边长平方是d² if (sideSq > maxSideSq) { maxSideSq = sideSq; bestSquare = {a, b, c, d4}; // 找到最大轴对齐的，直接更新最佳 } } } } // 找到当前d的正方形后，因d从大到小，可直接退出轴对齐检查 if (maxSideSq > 0) break; } // 2. 检查斜正方形（对角线枚举） sort(allpots.begin(), allpots.end()); int m = allpots.size(); for (int i = 0; i < m; ++i) { Point A = allpots[i]; int x1 = A.first, y1 = A.second; for (int j = i + 1; j < m; ++j) { Point C = allpots[j]; int x3 = C.first, y3 = C.second; // 计算另外两个顶点B和D（公式修正，基于向量垂直） int dx = x3 - x1; int dy = y3 - y1; int x2 = x1 - dy; int y2 = y1 + dx; int x4 = x3 - dy; int y4 = y3 + dx; // 检查B和D是否在网格内且为'#' if (!isHash(map, x2, y2) || !isHash(map, x4, y4)) continue; Point B(x2, y2), D(x4, y4); // 验证是否构成正方形 if (!isSquare(A, B, C, D)) continue; // 计算边长平方（AB的距离） int sideSq = distSq(A, B); if (sideSq > maxSideSq) { maxSideSq = sideSq; bestSquare = {A, B, C, D}; } } } // 输出四个顶点（顺序不影响，按排序后输出） sort(bestSquare.begin(), bestSquare.end()); for (const auto& p : bestSquare) { cout << p.first << " " << p.second << "\n"; } return 0; }

发表于 2025-11-28 21:18:51 回复(0)

提交观点

问题信息

难度：

1条回答 4收藏 6浏览

最大正方形

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题