首页 > 编程语言 >算法学习记录:P1387 最大正方形

算法学习记录:P1387 最大正方形

时间:2023-05-21 10:33:13浏览次数:37  
标签:int P1387 len 正方形 算法 思路 include 代码

题目链接

https://www.luogu.com.cn/problem/P1387

解题思路

固定左上角的点,枚举所有边长即可。

随记:

昨天脑子特乱,下标,越界什么的都没想好就开始写了,因为思路不清晰时写的,写出来的代码,调bug都不知道怎么调,
对自己写的东西不够理解,在哪打印输出也不知道(循环一多自己就乱了),一个bug差不多调了快一天,今天理顺再战,一下子就过了。
很简单的题qwq。
以后写代码思路一定要清晰,尤其是边界,一定要想好。自己的代码每一步做了什么也要理顺!

AC代码

#include <iostream>
#include <math.h>
using namespace std;

const int N = 105;
int n, m, maxn;
int w[N][N];

int main()
{
	cin >> n >> m;
	
	for (int i = 1; i <= n; ++ i)
	    for (int j = 1; j <= m; ++ j)
	        cin >> w[i][j];

	int len = min(n, m);
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= m; ++ j)
			for (int k = 0; k <= len; ++ k)
			{
				if (i + k > len && j + k > len) break;
		
				bool flag = true;
				int cnt = 0;
				for (int r = i; r <= i + k; ++ r)	
				{
					if (!flag) break;
					for (int c = j; c <= j + k; ++ c)
					{
						if (w[r][c]) cnt ++ ;
						else {
							flag = false;
							break;
						}
					}
				}

				if (!flag) cnt = 0;
				maxn = max(cnt, maxn);
			}
	cout << sqrt(maxn);
        return 0;
}

思路2

固定2个点进行枚举,待补

标签:int,P1387,len,正方形,算法,思路,include,代码
From: https://www.cnblogs.com/ClockParadox43/p/17418291.html

相关文章

  • 算法的时间复杂度
    算法的时间复杂度是指在计算机执行该算法时所需要的时间和输入规模之间的关系。常见的时间复杂度有:1.O(1):常数时间复杂度,表示无论输入规模大小是多少,算法都需要相同的时间完成。例如读取数组中某个元素。2.O(logn):对数时间复杂度,表示算法的运行时间随输入规模增长而增长,但增......
  • 拓展欧几里得算法
    1.拓展欧的用处:求解方程\(ax+by==m\)的一组解2.拓展欧的一般性条件:对于方程\(ax+by=m\),当\(gcd(a,b)\)是m的整数倍时必定有解3.求解:设\(d=gcd(a,b)\),则特解为\(\begin{cases}x=x_0+\frac{d}{m}\quad\\y=y_0+\frac{d}{m}\quad\\\end{cases}......
  • 【代码随想录算法训练营第一天】704. 二分查找、27. 移除元素
    Day1-数组Leetcode704二分查找初解已经不记得二分查找了,遍历找O(n)其实也过了,只是借此复习一下二分,确实快很多。二分的前提条件题目里也都明示了:无重复,(从小到大)排序。我没有用到这个条件,自然时间复杂度高于最优解。看完解答我再看了一眼题目的标题,才知道是考BinarySearch嗯......
  • C# 版本 最少金币问题 动态规划 算法
    @[TOC](C#版本最少金币问题动态规划算法)<hrstyle="border:solid;width:100px;height:1px;"color=#000000size=1">题目这是一道经典算法题,题目如下:题目:有面值为2元,5元,7元面值的硬币,买一本27元的书,用最少的硬币组合刚好付清,问题1:需要几枚硬币。问题2:这几枚硬币都是什么?<......
  • 算法学习笔记合集
    字符串哈希:哈希学习笔记KMP:KMP学习笔记图论分层图最短路:分层图最短路LCA:P3379最近公共祖先模板数据结构线段树:线段树学习笔记ST表:P3865ST表树状数组:P3374树状数组1DP树上背包:P2014选课(树上背包)杂项搜索:搜索学习笔记离散化:离散化学习笔记......
  • 最短路径算法
    最短路径问题这是一类最基本的图论问题,给定一个图,求从某一个源节点到某一个目的节点的最短路径。比较常见的算法有dijkstra,floyd,SPFA。在开始之前我们先说一说“松弛”这个词。在描述最短路径算法的时候,我们经常可以看到松弛(relaxtion)一词,通常来说,所有的最短路径算法都......
  • 算法学习day25回溯part02-216、17
    packageLeetCode.backtrackpart02;importjava.util.ArrayList;importjava.util.LinkedList;importjava.util.List;/***216.组合总和III*找出所有相加之和为n的k个数的组合,且满足下列条件:*只使用数字1到9*每个数字最多使用一次*返回所有可能的有效......
  • 《数据结构与算法》之十大基础排序算法
    一.冒泡排序什么是冒泡排序?冒泡排序是一种交换排序,它的思路就是在待排序的数据中,两两比较相邻元素的大小,看是否满足大小顺序的要求,如果满足则不动,如果不满足则让它们互换。然后继续与下一个相邻元素的比较,一直到一次遍历完成。一次遍历的过程就被成为一次冒泡,一次冒泡的结束至......
  • 代码随想录算法训练营第十一天|20. 有效的括号、1047. 删除字符串中的所有相邻重复项
    【参考链接】20.有效的括号【注意】1.括号匹配是使用栈解决的经典问题。2.这个命令最后进入a目录,系统是如何知道进入了a目录呢,这就是栈的应用(其实可以出一道相应的面试题了)。3.有三种不匹配的情况,第一种情况,字符串里左方向的括号多余了;第二种情况,括号没有多余,但是括号的......
  • 基于Graph-Cut算法的彩色图像深度信息提取matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下:2.算法涉及理论知识概要Graphcuts是一种十分有用和流行的能量优化算法,在图像处理领域普遍应用于前后背景分割(Imagesegmentation)、立体视觉(stereovision)、抠图(Imagematting)等,目前在医学图像领域应用较多。GraphCut(图形切割)应用于......